得物笔试得物秋招得物笔试题 1025

笔试时间：2025年10月25日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：归零

小A最近学习到一种新的运算，叫异或，运算符记为xor。这是对两个相同长度的二进制串（仅含有0或1的字符串）进行的运算，相同位上对应的数字如果不同则该位运算结果为1，否则为0。例如：

00011100
xor 11101101
  -----------
  11110001

现在小A手上有一个二进制串s，他想让这个二进制串异或上若干个长度相同且所有的1连续的二进制串（如000111、1100、010、1等，但01010、101等不合法），使得s所有位都为0。小A想知道最少需要进行多少次异或运算？

输入描述

第一行一个正整数T，表示有T组数据；接下来每一组数据对应一行，首先输入x，表示该二进制串长度；之后输入一个长度为x的二进制串。

数据范围：(1 ≤ x ≤ 5 × 10^4), (1 ≤ T ≤ 100)

输出描述

输出T行，每一行一个整数，表示该数据下的最小异或次数。

样例输入

2

8 00011101

1 0

样例输出

2

0

样例说明

第一组数据：一种方法是异或上00000110和00011111即可。第二组数据：原串已经为0，不需要进行异或操作。

参考题解

解题思路：

遍历字符串，每遇到新的1段（即当前为1，且前一个不是1）时，计数+1，输出计数结果。核心思想是统计连续1的段数。

C++：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        
        int count = 0;
        bool inOne = false;
        
        for (char c : s) {
            if (c == '1') {
                if (!inOne) {
                    count++; // 新的一段1
                    inOne = true;
                }
            } else {
                inOne = false;
            }
        }
        
        cout << count << "\n";
    }
    
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        while (T-- > 0) {
            int n = sc.nextInt();
            String s = sc.next();
            
            int count = 0;
            boolean inOne = false;
            
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '1') {
                    if (!inOne) {
                        count++; // 新的一段1
                        inOne = true;
                    }
                } else {
                    inOne = false;
                }
            }
            
            System.out.println(count);
        }
        
        sc.close();
    }
}

Python：

T = int(input())

for _ in range(T):
    line = input().split()
    n = int(line[0])
    s = line[1]
    
    count = 0
    in_one = False
    
    for c in s:
        if c == '1':
            if not in_one:
                count += 1  # 新的一段1
                in_one = True
        else:
            in_one = False
    
    print(count)

第二题：糖果促销

小明开了一家糖果店，店里有不同种类的糖果并且无限供应，所有种类的糖果都是2元一个。为了提高销量，小明进行了一场促销活动。对于种类(i)的糖果，小明制定了一个打折策略，只要在其店里已经购买过任意种类的糖果(b_i)个，那么再购买该种类(i)的糖果，可以享受1元一个的促销。现在一个客户需要购买一些糖果，其中(i)种类的糖果购买(a_i)个，根据小明制定的打折策略，你可以帮助客户通过最少的钱买到这些糖果么？