普及组第六场题解

happy

枚举

使用一个桶存储每个数字是否出现过，并记录桶大小即可。

比较暴力的办法是使用set。

#include<bits/stdc++.h>

using namespace std;

int main(){
	int n;
	cin >> n;
	set<int> st;
	int ans = 0;
	for(int i = 1; i <= n * 2; i++){
		int x;
		cin >> x;
		if(st.count(x)) st.erase(x);
		else st.insert(x);
		ans = max(ans, (int)st.size());
	}
	cout << ans << endl;
}

lucky

模拟、异或

实际上二进制下的不进位加法就是异或运算。

我们可以先将每一位对应的两个字符转化成数字，然后直接异或得到新的数字。

需要注意的是不能有前导零。

#include<bits/stdc++.h>

using namespace std;

int main(){
	string s, t;
	cin >> s >> t;
	if(s.size() < t.size()) swap(s, t);
	auto get = [&](auto x, auto y){
		if(x >= 'A') x -= 'A' - 10;
		else x -= '0';
		if(y >= 'A') y -= 'A' - 10;
		else y -= '0';
		auto t = x ^ y;
		if(t >= 10) t += 'A' - 10;
		else t += '0';
		return t;
	};
	for(int i = s.size() - 1, j = t.size() - 1; j >= 0; i--, j--){
		s[i] = get(s[i], t[j]);
	}
	reverse(s.begin(), s.end());
	while(s.size() > 1 && s.back() == '0') s.pop_back();
	reverse(s.begin(), s.end());
	cout << s << endl;
}

smile

01背包

由于1和2的分配是固定的，因此1和2不需要参与分配。

而0可以分配给双方，因此可以用0跑01背包，然后枚举背包中的每一个值去计算答案。

#include<bits/stdc++.h>

using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> sum(3);
	vector<int> dp(n * 500 + 1);
	dp[0] = 1;
	for(int i = 1; i <= n; i++){
		int x, y;
		cin >> x >> y;
		sum[y] += x;
		if(!y){
			for(int j = n * 500; j >= x; j--){
				dp[j] |= dp[j - x];
			}
		}
	}
	int ans = 1e9;
	for(int i = 0; i <= n * 500; i++){
		if(dp[i]) ans = min(ans, abs((sum[1] + i) - (sum[2] + sum[0] - i)));
	}
	cout << ans << endl;
}

yeah

前缀和、双指针

用5个前缀和数组分别记录前缀有多少个 "h" 、 "w" 、 "hh" 、 "hw" 、 "hhw" 子序列。

那么区间 $[l,r]$ 中 "hhw" 子序列数量为：

首先， $hhw[r] - hhw[l - 1]$ ，完整的子序列相减。

其次，再减去 $hh[l-1] \times (w[r]-w[l-1])$ ， "hh" 在前， "w" 在后的情况。

再次，减去 $h[l-1] \times cnt\_hw(l,r)$ ， "h" 在前， "hw" 在后的情况；

其中 $cnt\_hw(l,r)=hw[r]-hw[l-1]-h[l-1] \times (w[r]-w[l-1])$ ，和上述情况类似。

并且若是 $[l,r]$ 满足条件， $[l,r+1]$ 必然也满足条件，因此满足双指针的性质。

时间复杂度为 $O(n)$ 。

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	s = " " + s;
	vector<LL> h(n + 1), w = h, hh = h, hw = h, hhw = h;
	for(int i = 1; i <= n; i++){
		h[i] = h[i - 1];
		w[i] = w[i - 1];
		hh[i] = hh[i - 1];
		hw[i] = hw[i - 1];
		hhw[i] = hhw[i - 1];
		if(s[i] == 'h'){
			h[i]++;
			hh[i] += h[i - 1];
		}
		if(s[i] == 'w'){
			w[i]++;
			hw[i] += h[i - 1];
			hhw[i] += hh[i - 1];
		}
	}
	auto get = [&](auto l, auto r){
		LL ans = hhw[r] - hhw[l - 1];
		ans -= hh[l - 1] * (w[r] - w[l - 1]);
		LL t = hw[r] - hw[l - 1];
		t -= h[l - 1] * (w[r] - w[l - 1]);
		ans -= h[l - 1] * t;
		return ans;
	};
	LL ans = 0;
	for(int i = 1, j = 1; i <= n; i++){
		j = max(j, i);
		while(j <= n && get(i, j) < k){
			j++;
		}
		ans += n - j + 1;
	}
	cout << ans << endl;
}