普及组第六场题解
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" 子序列。
那么区间 中 "hhw" 子序列数量为:
首先, ,完整的子序列相减。
其次,再减去 , "hh" 在前, "w" 在后的情况。
再次,减去 , "h" 在前, "hw" 在后的情况;
其中 ,和上述情况类似。
并且若是 满足条件,
必然也满足条件,因此满足双指针的性质。
时间复杂度为 。
#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; }