笔试时间：2024年05月12日

历史笔试传送门：2023秋招笔试合集

第一题

题目

小红定义一个数组是好数组，当且仅当所有奇数出现了奇数次，所有偶数出现了偶数次。现在小红拿到了一个数组，她希望取一个该数组的非空子序列(可以不连续)，使得子序列是好数组。你能帮小红求出子序列的方案数吗?由于答案过大，请对1e9+ 7取模。

输入描述

第一行输入一个正整数n，代表数组的大小

第二行输入n个正整数a[i]，代表数组的元素

1<=n<=1e5，1<=a[i]<=1e9

输出描述

一个整数，代表是“好数组”的子序列数量，对1e9+7取模的值。

样例输入

4

1 2 3 2

样例输出

7

参考题解

对于每个数字，如果该数字为奇数，且该数字一共出现了x次，则出现奇数次的方案数为c(x,1)+c(x,3)+c(x,5)+...+c(x,x).其中c表示组合数，这个大小就是2^(x-1)，但是该数字也可以不出现，所以还要加一，一共就是2^(x-1)+1种方案，而偶数就是c(x,0)+c(x,2)+...c(x,x),这个也是2^(x-1),然后乘起来，再减去全部都不出现的一次，即减去空串的情况，就是最后答案。

C++：[此代码未进行大量数据的测试，仅供参考]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int a[100010],pow2[100100];
map<int,int>mp;
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    pow2[0]=1;
    int ans=1;
    for(int i=1;i<=n;i++)pow2[i]=pow2[i-1]*2%mod;
    for(auto i:mp){
        if(i.first&1)
        ans=ans*(pow2[i.second-1]+1)%mod;
        else ans=ans*pow2[i.second-1]%mod;
    }
    cout<<ans-1;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] a = new long[100010];
        long[] pow2 = new long[100100];
        Map<Long, Long> mp = new HashMap<>();
        
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextLong();
            mp.put(a[i], mp.getOrDefault(a[i], 0L) + 1);
        }
        
        pow2[0] = 1;
        long ans = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = (pow2[i-1] * 2) % MOD;
        }
        
        for (Map.Entry<Long, Long> entry : mp.entrySet()) {
            if ((entry.getKey() & 1) == 1) {
                ans = (ans * (pow2[entry.getValue().intValue() - 1] + 1)) % MOD;
            } else {
                ans = (ans * pow2[entry.getValue().intValue() - 1]) % MOD;
            }
        }
        
        System.out.println(ans - 1);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

MOD = 1000000007

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    a = list(map(int, data[1:n+1]))
    
    pow2 = [1] * (n + 1)
    for i in range(1, n + 1):
        pow2[i] = pow2[i-1] * 2 % MOD
    
    mp = {}
    for num in a:
        if num in mp:
            mp[num] += 1
        else:
            mp[num] = 1
    
    ans = 1
    for key, value in mp.items():
        if key % 2 == 1:
            ans = ans * (pow2[value - 1] + 1) % MOD
        else:
            ans = ans * pow2[value - 1] % MOD
    
    print(ans - 1)

if __name__ == "__main__":
    main()

第二题

题目

定义一个01串为“交错串”，当且仅当任意两个相邻的字符都是不同的。例如，"10101"是交错串. 现在小红拿到了一个01串，她有若干次询问，每次询问一个区间，你需要回答将该区间代表的连续子串修改为“交错串”的最小修改次数。每次修改可以修改任意一个字符。

输入描述

第一行输入两个正整数n,q，代表字符串长度和询问次数。

第二行输入一个长度为n的、仅由'0'和'1'组成的字符串。

接下来的q行，每行输入两个正整数l,r，代表询问的是第l个字符到第r个字符组成的子串。

1≤n,q≤1e5

1<=l,r<=n

输出描述

输出q行，每行输出一个整数代表询问的答案。

样例输入

6 3

101101

1 3

3 5

1 6

样例输出

0

1

3

参考题解

前缀和记录，然后查询的时候通过前缀和快速判断这两种较小一种的即可。

C++：[此代码未进行大量数据的测试，仅供参考]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int sum1[100010],sum2[100010];
signed main(){
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    s=" "+s;
    for(int i=1;i<s