Codeforces Round #832 (Div. 2) A

常务管理员 · 发表于 2022-11-10 19:49:50

最后10分钟才想到D，令人感叹。
进入正题：
A. Two Groups 签到

题意：
给定长度为n的数组，将所有数分到两个背包a,b中，求|sum(a)| - |sum(b)|的最大值。
分析：
因为最终取的是绝对值，因此我们把所有正数和负数分开放，绝对值更大的减去绝对值更小的就是答案。
代码：
void solve()
{
   cin >> n;
   int sum0 = 0, sum1 = 0;
   for(int i = 1 ; i <= n ; i ++ ) {
      cin >> a;
      if(a < 0) sum0 -= a;
      else sum1 += a;
   }
   if(sum0 >= sum1) cout << sum0 - sum1 << endl;
   else cout << sum1 - sum0 << endl;
}
B. BAN BAN 模拟

题意：
给定长度为3n的由n个BAN组成的字符串，求出最少的交换次数使得字符串的任意子串不包含BAN。
分析:
因为BAN三个字符的顺序是固定的，因此想要最小化操作，我们只需要将所有的N放到B前面即可。
将最后一个N和第一个B交换，重复即可。
代码：
void solve()
{
   cin >> n;
   if(n == 1) cout << 1 << endl << 1 << &#39; &#39; << 2 << endl;
   else {
      cout << (n + 1) / 2 << endl;
      for(int i = 1; i <= (n + 1) / 2 ; i ++ ) {
         int p1 = (i - 1) * 3 + 1;
         int p2 = 3 * n - p1 + 1;
         if(p1 > p2) return ;
         cout << p1 << &#34; &#34; << p2 << endl;
      }
   }
}
C. Swap Game 博弈

题意：
给定一个长度为n的数组，Alice和Bob玩博弈游戏。每次每个人选择一个大于1的位置i，先将a[1] = a[1] - 1，然后a[1]与a交换。如果轮到某个人的回合开始时，出现了a[1] = 0 的情况，那么他就输了。请问游戏谁胜谁负。
分析:
首先这道题和奇偶型真的没有关系，显然是诈骗。
假如a[1]刚开始存的是最小值，那么不管先手怎么换后手都可以把刚开始的数换回去，疯狂的恶心她。最后先手会遇到刚开始的a[1]变成0的局面，他就失败了。
相反，如果a[1]不是最小值，namo先手只需要找到一个最小的值换过来，这样就可以像第一种情况那样恶心后手了。
代码：
void solve()
{
   cin >> n;
   int mn = INF;
   for(int i = 1; i <= n ; i ++ ) cin >> a, mn = min(mn, a);
   int sum = 0, cnt = 0;
   for(int i = 1; i <= n ; i ++ ) {
      sum += a - mn;
      if(a == mn) cnt ++ ;
   }
   if(a[1] == mn) {Bob;}
   if(a[1] != mn) {Alice;}
}
D. Yet Another Problem 预处理 + stl

题意：
给定一个长度为n的数组，给定m个独立询问。每个询问包含[l, r]，要求每次在[l, r]范围内选择若干个奇数长度的连续区间使得这段区间内所有值变成区间异或和，求最少操作次数使得[l, r]内所有元素的值变为0.
分析:
异或运算是一种很特殊的运算，也就是不进位加法。
结论1: 如果区间内本身的异或和为不为0，那么答案为-1。
结论2: 如果区间内本身全为0，那么答案为0。
结论3: 如果区间异或和为0且区间长度为奇数，那么答案为1，也就是直接选择整段区间一次完成。
同理，假如区间长度为偶数且异或和为0，如果在区间两端存在任意一个0，那么舍弃一个0之后区间长度变成奇数，那么答案也为1。
最后一种情况，也就是操作数为2的情况。此时的限制条件是：区间长度为偶数，区间异或和为0。那么我们需要找到一个中间值将区间分为两段。对两段进行操作。
预处理
用map存奇数和偶数位置上前缀异或和为x的所有下标。比如对于奇数位置，前缀异或为3的下标有[3, 7, 9]，那么对于一个l的位置，我们可以用lowerbound快速找到第一个距离为奇数位置的区间异或和为0的右端点。查看这个端点是否在[l, r]范围内即可。
具体看代码qwq
代码：
void solve()
{
cin >> n >> m;
map<int, vector<int>> v1, v2;
for(int i = 1; i <= n ; i ++ ) {
      cin >> a;
      s = s[i - 1] ^ a;
      sum = sum[i - 1] + a;
      if(i & 1) v1[s].push_back(i);
      else v2[s].push_back(i);
}
while(m -- ) {
      int l, r;
      cin >> l >> r;
      int len = r - l + 1;
      if(s[l - 1] ^ s[r]) {
         cout << -1 << endl;
         continue;
      }
      if(sum[r] == sum[l - 1]) {
         cout << 0 << endl;
         continue;
      }
      if(len & 1) {
         cout << 1 << endl;
         continue;
      }
      if(!a[l] || !a[r]) {
         cout << 1 << endl;
         continue;
      }
      if(!((l - 1) & 1)) {
         auto it = lower_bound(v1[s[l - 1]].begin(), v1[s[l - 1]].end(), l - 1);
         if(it != v1[s[l - 1]].end() && *it < r) {
            cout << 2 << endl;
            continue;
         }
      } else {
         auto it = lower_bound(v2[s[l - 1]].begin(), v2[s[l - 1]].end(), l - 1);
         if(it != v2[s[l - 1]].end() && *it < r) {
            cout << 2 << endl;
            continue;
         }
      }
      cout << -1 << endl;
}

}