题目链接：https://codeforces.com/contest/1323/
A - Even Subset Sum Problem
送分题。
B - Count Subrectangles
题意：给一个长度为n的01向量A，一个长度为m的01向量B，规定矩阵C_{ij}=A_i*B_j。再给一个整数k，求矩阵C中有多少个大小恰好为k的子矩阵，其中全都是1。
题解：先dp转移出以某个位置为结尾的最长的连续全1区间的长度。排序。枚举k的因子作为子矩阵的行数，算出需要的列数，再在两个dp数组里面二分得到有多少个区间是比需要的长和宽要长的。
int dpn[40005];
int dpm[40005];
void test_case() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = 1, a; i <= n; ++i) {
scanf("%d", &a);
dpn[i] = (a == 1) ? dpn[i - 1] + 1 : 0;
}
for(int j = 1, b; j <= m; ++j) {
scanf("%d", &b);
dpm[j] = (b == 1) ? dpm[j - 1] + 1 : 0;
}
sort(dpn + 1, dpn + 1 + n);
sort(dpm + 1, dpm + 1 + m);
ll sum = 0;
for(int d = 1; d <= n; ++d) {
if(k % d == 0 && k / d <= m) {
int pos1 = lower_bound(dpn + 1, dpn + 1 + n, d) - dpn;
int pos2 = lower_bound(dpm + 1, dpm + 1 + m, k / d) - dpm;
sum += (n - pos1 + 1) * (m - pos2 + 1);
}
}
printf("%lld
", sum);
}
C - Unusual Competitions
题意：给一个括号串，用最小的代价重排这个括号串，使得它变成合法的括号串。每次操作可以选择一个长度为x的区间，然后把这个区间中的字符排成想要的顺序，代价为x。
题解：贪心，把整个括号串划分为尽可能多的左右括号数量相等的子区间。然后若某个区间不是合法括号串（也就是说，这个区间必定以')'开头，因为以'('开头的串都是合法的括号串），就必定需要重排。
D - Present
题意：给一个n(<=4e5)个元素的数组，数据范围在1e7，对所有的数对(i,j)(i<j)，统计xor(a_i+a_j)，也就是：
(a_1+a_2)xor(a_1+a_3)xor...xor(a_1+a_n)
xor(a_2+a_3)xor(a_2+a_4)xor...xor(a_2+a_n)
xor(a_{n-1}+a_n)
题解：看见是异或，一个很自然的想法就是把各位分开统计，但是统计高位的时候有可能会受到低位进位的影响。想了很多种办法去掉这个影响，最简单的办法是按低位排序，然后upper_bound找到进位的第一个数的pos，这个数及其后面的都会进位，而这个数前面的都不会进位。注意一个数对只能统计一次，所以假如当前枚举到第i个数，那么upper_bound的起始位置就是i+1。复杂度O(logMAXAInlogn)。时间：1000ms。
int a[400005];
pii p[400005];
int l[400005];
int suffix0[400005];
int suffix1[400005];
void test_case() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
int ans = 0;
for(int BIT = 0; BIT <= 26; ++BIT) {
int BITMASK = (1 << BIT) - 1;
for(int i = 1; i <= n; ++i) {
p[i].first = a[i] & BITMASK;
p[i].second = (a[i] >> BIT) & 1;
}
sort(p + 1, p + 1 + n);
suffix0[n + 1] = 0;
suffix1[n + 1] = 0;
for(int i = n; i >= 1; --i) {
suffix0[i] = suffix0[i + 1] + (p[i].second == 0);
suffix1[i] = suffix1[i + 1] + (p[i].second == 1);
l[i] = p[i].first;
}
ll sum = 0;
for(int i = 1; i <= n; ++i) {
int pos = upper_bound(l + i + 1, l + n + 1, BITMASK - l[i]) - l;
if(p[i].second == 0)
sum += suffix0[pos] + suffix1[i + 1] - suffix1[pos];
else
sum += suffix1[pos] + suffix0[i + 1] - suffix0[pos];
}
if(sum % 2 == 1)
ans |= (1 << BIT);
continue;
}
printf("%d
", ans);
}
但是其实upper_bound可以换成一个均摊O(1)的方法，也就是双指针。注意每次都已经按低位排好序，实际上排序可以用归并排序来代替（基数排序）。复杂度O(logMAXAIn)。时间：250ms。
pii p[400005], p0[400005], p1[400005];
int p0top, p1top;
int suffix0[400005], suffix1[400005];
void test_case() {
int n;
scanf("%d", &n);
for(int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
p[i].first = 0;
p[i].second = x << 1;
}
int ans = 0;
for(int BIT = 0; BIT <= 26; ++BIT) {
p0top = 0, p1top = 0;
for(int i = 1; i <= n; ++i) {
if(p[i].second & 1) {
++p1top;
p1[p1top].first = p[i].first | (1 << BIT);
p1[p1top].second = p[i].second >> 1;
} else {
++p0top;
p0[p0top].first = p[i].first;
p0[p0top].second = p[i].second >> 1;
}
}
merge(p0 + 1, p0 + 1 + p0top, p1 + 1, p1 + 1 + p1top, p + 1);
suffix0[n + 1] = 0;
suffix1[n + 1] = 0;
for(int i = n; i >= 1; --i) {
suffix0[i] = suffix0[i + 1] + ((p[i].second & 1) == 0);
suffix1[i] = suffix1[i + 1] + ((p[i].second & 1) == 1);
}
ll sum = 0;
for(int i = 1, pos = n + 1; i <= n; ++i) {
if(pos <= i)
pos = i + 1;
while(pos - 1 >= i + 1 && p[i].first + p[pos - 1].first >= (1 << (BIT + 1)))
--pos;
if((p[i].second & 1) == 0)
sum += suffix0[pos] + suffix1[i + 1] - suffix1[pos];
else
sum += suffix1[pos] + suffix0[i + 1] - suffix0[pos];
}
if(sum % 2 == 1)
ans |= (1 << BIT);
continue;
}
printf("%d
", ans);
}
启示：
1、异或运算和加法运算确实不满足分配律。
2、加法运算和位运算混在一起的时候，有可能要排序之后使得进位的区间连续，然后可以二分找这个区间，也可以用双指针转移，注意在这道题里面右指针不能超过左指针。
3、既然本身sort就是O(nlogn)的，再弄个二分问题不大。时间给3000ms，带两个log明明就可以过，能不优化就不优化。
*E - Instant Noodles
题意：给一个左部n个点，右部n个点，总共m条无向边的二分图，其中右部的点都分别有一个权值ci。对于左部点的某个集合S，定义N(S)就是S的所有邻居的并集，再定义f(S)为N(S)中的点的权值之和。求所有左部点的集合的所有子集的f(S)的gcd。
题解：所有邻居相同的右部点，都是同时出现或者同时不出现的，他们可以缩成一个新的右部点，包含这个右部点集的所有点的权值之和。答案就是这样缩点之和的新点的权值的gcd。大概是类似gcd((a+b),a,b)=gcd(gcd(a+b,a),b)=gcd(a,b)，这样归纳。三个数就是gcd(a,b,c,(a+b),(a+c),(b+c),(a+b+c))=gcd(a,b,c)，感觉正确性是非常显然的。
那么问题变成了怎么快速把邻居相同的右部点合并在一起。一个看起来很可行的思路，就是把每个右部点的邻居左部点排序（因为题目保证没有重边，所以不需要去重），然后计算哈希值。确定性的做法，应该就是排序，然后插进字典树Tire。
最后考虑空集的影响，空集并不会被选到，直接把空集删除。由于至少有一条边，所以至少有一个非空集，就把非空集的gcd都取出来。
ll c[500005];
vector<int> G[500005];
map<ull, ll> M;
void test_case() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%lld", &c[i]);
for(int i = 1; i <= n; ++i)
G[i].clear();
while(m--) {
int u, v;
scanf("%d%d", &u, &v);
G[v].push_back(u);
}
M.clear();
for(int i = 1; i <= n; ++i) {
if(G[i].empty())
continue;
sort(G[i].begin(), G[i].end());
ull id = 0;
for(auto &v : G[i])
id = id * 2333333 + v;
M[id] += c[i];
}
ll ans = 0;
for(auto &it : M)
ans = __gcd(ans, it.second);
printf("%lld
", ans);
}
F - Reality Show
不可做题。