Jouier 普及组十连测 R4

反思

        本次比赛到时没有什么细节错误，不过代码思路不好所以分数也不是很高。

T1

代码思路

        看题意，发现数据范围不大，直接动用码力暴力即可。

代码

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

vector<vector<int> > a(110);
int v[100];
char ch[110];
long long ans = 0;
int n,m,k; 

bool check(){
	int p = 0;
	for(int i = 1; i <= m; i++){
		p = 0;
		for(int d : a[i]) p += v[d];
		if(p >= k && ch[i] == 'x') return 0;
		if(p < k && ch[i] == 'o') return 0;
	}
	return 1;
}

void dfs(int t){
	if(t >= n+1){
		if(check()) ans++;
		return ;
	}
	v[t] = 1;
	dfs(t+1);
	v[t] = 0;
	dfs(t+1);
}

int main(){
	freopen("key.in","r",stdin);
	freopen("key.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++){
		int c; cin >> c;
		for(int j = 1; j <= c; j++){
			int x; cin >> x;
			a[i].push_back(x);
		}
		cin >> ch[i];
	}
	dfs(1);
	cout << ans << endl;
	return 0;
} 

T2

代码思路

        这道题本人拿了40pts，就是暴力加上特殊点的分，也是尽我所能了。

        接下来讲解一下正确思路：

                在子字符串中，如果每个数字出现次数为偶数那么他就是快乐的，我们可以类似于状态压缩dp一样，把每个数出现的次数奇偶性存在一个二进制数，比如第0位存0出现次数的奇偶性，如果存现次数为偶数当前位为1反之为0。类似于前缀和思想，如果两个数奇偶性一致（就是这个二进制数一致）那么这个区间就是合法的也就是统计之前这个二进制数出现几次累加即可。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
	freopen("fly.in","r",stdin); 
	freopen("fly.out","w",stdout); 
    string S;
    cin >> S;
    int n = S.length();
    unordered_map<int, int> mask_count;
    mask_count[0] = 1;  // 初始掩码为0，表示所有数字出现0次（偶数次）
    int current_mask = 0;
    long long result = 0;

    for (char c : S) {
        int digit = c - '0';
        current_mask ^= (1 << digit);  // 翻转对应数字的奇偶位
        result += mask_count[current_mask];  // 累加之前相同掩码的出现次数
        mask_count[current_mask]++;  // 更新当前掩码的出现次数
    }

    cout << result << endl;
    return 0;
}