Codeforces Round 853 (Div. 2)

Codeforces Round 853 (Div. 2)

C. Serval and Toxel's Arrays

思路：

求任意两个组合的元素个数。

1. 注意到，其实每个元素都是独立的。他在任意组合的出现情况组成的贡献是可以分开讨论的。
2. 我们讨论元素x。假设x在m+1个数组中出现了cnt次（一个数组最多只有一个x）。
3. 那么对于任意两个数组可能出现的情况有：
   1. 同时有x，这样的组合是C（2，cnt)，贡献1
   2. 只有一个有x，这样的组合是cnt*(m+1-cnt)，贡献1
   3. 都没有x，不用讨论，贡献0
4. 我们把每个数都分别这样讨论，就是答案。

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 4e5 + 10;int a[N];
int cnt[N];
int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--){int n, m;cin >> n >> m;for (int i = 0; i <= n + m; ++i)cnt[i] = 0;for (int i = 1; i <= n; ++i){cin >> a[i];cnt[a[i]] = m + 1; //如果一个数没被修改，他会一直出现，共m+1次}int p, v;for (int i = 1; i <= m; ++i){cin >> p >> v;cnt[a[p]] -= m - i + 1; //被修改的数后面都不会再出现了（除非再给一次）cnt[v] += m - i + 1; //新的数后面都会出现（直到被修改没）a[p] = v;}ll ans = 0;for (int i = 1; i <= n + m; ++i)ans += (ll)cnt[i] * (cnt[i] - 1) / 2 + (ll)cnt[i] * (m + 1 - cnt[i]);cout << ans << endl;}return 0;
}

D. Serval and Shift-Shift-Shift

思路：

1. 看数据，1e3，说明我们可以进行复杂度为O（N^2)的操作
2. 首先，只要a至少存在一个1，我可以用1产生任何值（按位一位一位操作，可以把他们变成想要的1或者0），除了0（因为要求位移至少为1，所以不能消去自己）
3. 当我们a的最高位1右区间需要1或者0时，我们可以把最高位移动到那里修改他，这个操作遍历右区间，我们每次操作，因为最高位1左边都是0，所以不会对操作位左边产生影响。而操作位右边有影响没事，我会一位一位向右过去修改。
4. 修改左区间同理，找最小位1，不断左移修改左区间（不能还是从高位修改到低位），我们这次是利用不影响右区间，左区间等下会修改。两者相反。
5. 最后，注意到a，b要么同时为0，要么同时不为0（a为0，无法变成非0，a不为0，无法变成0）

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 2e3 + 10;bool a[N], b[N], c[N];
int ans[N];void mysolve()
{int n;string a1, b1;cin >> n >> a1 >> b1;if (a1 == b1){cout << 0 << endl;return;}int cnta = 0, cntb = 0; //记录啊a与b1的个数int cnt = 0; //操作数for (int i = 0; i < n; ++i){a[i] = a1[i] - '0', b[i] = b1[i] - '0';if (a[i])cnta++;if (b[i])cntb++;}//同时非0if (cnta && cntb){int ha = n, hb = n; //记录a与b的最高位1for (int i = 0; i < n; ++i)if (a[i]){ha = i;break;}for (int i = 0; i < n; ++i)if (b[i]){hb = i;break;}//修改b最高位1及往右的区间for (int i = hb; i < n; ++i){if (a[i] != b[i]){int tmp = i - ha; //表示位移ans[++cnt] = ha - i;//先记录，后面ha可能更新memcpy(c, a, sizeof(a)); //不能直接a数组间去异或，途中会修改a的for (int j = i; j < n; ++j){if (j - tmp >= n)break; //越界后面都是异或0了a[j] ^= c[j - tmp];if (a[j])ha = min(ha, j); //hb大于ha时，可能更新ha}}}if (ha < hb) //如果ha小于（注意，越高位越小，不是大于），那么需要把hb前面的1去掉{int la = 0; //a的最低位1for (int i = n - 1; i >= 0; --i)if (a[i]){la = i;break;}for (int i = hb - 1; i >= 0; --i) //往左更新{if (a[i]) //是1就删{int tmp = i - la;ans[++cnt] = la - i;memcpy(c, a, sizeof(a));for (int j = i; j >= 0; --j){if (j - tmp < 0)break;a[j] ^= c[j - tmp];}}}}cout << cnt << endl;for (int i = 1; i <= cnt; ++i)cout << ans[i] << ' ';cout << endl;}else cout << -1 << endl;
}int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--){mysolve();}return 0;
}