笔试时间：2025年5月17日

第一题

小苯有一个长度为n的01串x（下标从1到n），格格有一个长度恰好为n - 1的01串y（下标从1到n - 1）。格格的字符串y是用来匹配小苯的字符串x的，具体规则如下： 如果yi = 1（1 ≤ i ≤ n - 1），则意味着必须有：xi ≠ xi+1。 如果yi = 0（1 ≤ i ≤ n - 1），则意味着必须有：xi = xi+1。而现在小苯的串x并不一定满足y串的匹配要求，格格希望小苯修改尽可能少的字符，使得匹配成立。修改操作：选择i（1 ≤ i ≤ n），执行：xi = xi ⊕ 1（其中⊕ 表示按位异或运算 ）。请你帮小苯算一算至少需要修改多少个字符。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T（1 ≤ T ≤ 100）代表数据组数，每组测试数据描述如下： 第一行输入一个正整数n（2 ≤ n ≤ 10^9）代表x串的长度。 第二行输入一个长度为n，仅由字符‘0’和‘1’构成的字符串x。 第三行输入一个长度为n - 1，仅由字符‘0’和‘1’构成的字符串y。 除此之外，保证单个测试文件的n之和不超过10^9。

输出描述

对于每组测试数据，在单独的一行输出一个整数，表示最少的修改次数。

样例输入

2

8

11001011

1000111

6

101010

11111

样例输出

4

0

解释：对于第一组测试数据，我们修改x串为: "10000101" 即可，需要至少4次修改操作。 对于第二组测试数据，我们不需要修改x，因此输出0即可。

参考题解

枚举 x′[1] 为 0 或 1 两种可能，根据 y 串的异或关系递推唯一确定整个 x′，分别计算与原串 x 的翻转代价，取最小值即为答案。

C++：

// 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 x, y;
        cin >> n >> x >> y;

        long long cost0 = 0, cost1 = 0;
        int prev0 = 0, prev1 = 1;

        // 处理第一个字符
        if (x[0] != '0') cost0++;
        if (x[0] != '1') cost1++;

        // 逐位计算
        for (int i = 1; i < n; i++) {
            int yi = y[i-1] - '0';
            int curr0 = prev0 ^ yi;
            int curr1 = prev1 ^ yi;
            if (x[i] != char('0' + curr0)) cost0++;
            if (x[i] != char('0' + curr1)) cost1++;
            prev0 = curr0;
            prev1 = curr1;
        }

        cout << min(cost0, cost1) << '\n';
    }
    return 0;
}

Java：

// Java 版本
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            String x = br.readLine().trim();
            String y = br.readLine().trim();

            long cost0 = 0, cost1 = 0;
            int prev0 = 0, prev1 = 1;

            // 处理第一个字符
            if (x.charAt(0) != '0') cost0++;
            if (x.charAt(0) != '1') cost1++;

            // 逐位计算
            for (int i = 1; i < n; i++) {
                int yi = y.charAt(i - 1) - '0';
                int curr0 = prev0 ^ yi;
                int curr1 = prev1 ^ yi;
                if (x.charAt(i) != ('0' + curr0)) cost0++;
                if (x.charAt(i) != ('0' + curr1)) cost1++;
                prev0 = curr0;
                prev1 = curr1;
            }

            System.out.println(Math.min(cost0, cost1));
        }
    }
}

Python：

import sys
import threading

def main():
    input = sys.stdin.readline
    t = int(input())
    for _ in range(t):
        n = int(input())
        x = input().strip()
        y = input().strip()
        cost0 = 0
        cost1 = 0
        prev0 = 0
        prev1 = 1
        if x[0] != '0': cost0 += 1
        if x[0] != '1': cost1 += 1
        for i in range(1, n):
            yi = int(y[i-1])
            curr0 = prev0 ^ yi
            curr1 = prev1 ^ yi
            if x[i] != str(curr0): cost0 += 1
            if x[i] != str(curr1): cost1 += 1
            prev0 = curr0
            prev1 = curr1
        print(min(cost0, cost1))

if __name__ == "__main__":
    threading.Thread(target=main).start()

第二题

小红现在有每种小写字母若干个，她想把这些字母组成一个字符串s，使得字符串s任意两个相邻字母都不一样， 请你帮助她求出最长字符串的长度。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T（1 ≤ T ≤ 1000）代表数据组数，每组测试数据描述如下： 对于每一组测试数据，每行26个整数，依次表示a - z的字母数量xi（0 ≤ xi ≤ 10^9）。

输出描述

每组数据输出一个整数，表示满足条件的最长字符串的长度。

样例输入

3

00000000000000000000000011

00000000000000000000000111

11111111111111111111111115

样例输出

2

3

30

参考题解

先统计所有字母的总数 total 和出现次数最多的字母数 mx； 如果 mx 不超过剩下字母数加一（也就是 mx ≤ total - mx + 1），说明可以把所有字母都两两不同地插排进去，最长长度就是 total； 否则说明最常见的字母太多，只能在其他字母间插入，最长长度就是把这些“多余”部分两两交替：2*(total - mx) + 1。

C++：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line;
    if (!getline(cin, line)) return 0;
    int t = stoi(line);
    for (int tc = 0; tc < t; tc++) {
        if (!getline(cin, line)) break;
        istringstream iss(line);
        vector<string> parts;
        string tok;
        while (iss >> tok) {
            parts.push_back(tok);
        }
        vector<long long> cnts;
        if (parts.size() == 1 && parts[0].size() == 26) {
            for (char c : parts[0]) {
                cnts.push_back(c - '0');
            }
        } else {
            for (auto &p : parts) {
                cnts.push_back(stoll(p));
            }
        }
        long long total = accumulate(cnts.begin(), cnts.end(), 0LL);
        long long mx = *max_element(cnts.begin(), cnts.end());
        long long res = min(total, 2 * (total - mx) + 1);
        c