ARC137

心都凉了半截（

A 你暴力枚举复杂度就是对的，\([1,10^{18}]\) 内最远质数距离为 \(1000\) 级别。

B - Count 1's

给定一个 \(0/1\) 串，可以选择翻转一个区间，只能翻转一次，求可能的最终 \(1\) 的个数。

复杂的离谱的赛时做法：

设 \(s\) 为前缀和，翻转区间 \([l,r]\) 带来的影响为 \((r-l+1)-2(s_r-s_{l-1})\)。

将贡献拆开：\((r-2s_r)-(l-1+2s_{l-1})\)，发现 \(l-1+2s_{l-1}\) 的变化量 \(\leq 1\)，相当于前缀的它是一个连续区间。

枚举右端点，同时维护区间，每次在树状数组上区间加，最终非 \(0\) 位就是能表示出来的。

const int N = 3e5 + 10;
int n, a[N], s[N], c[N];
 
void Add(int x, int v) {x ++; for(; x <= n + 1; x += x & - x) c[x] += v;}
int Ask(int x) {int s = 0; x ++; for(; x; x -= x & - x) s += c[x]; return s;}
 
int main() {
	n = read();
	rep(i, 1, n) a[i] = read(), s[i] = s[i - 1] + a[i];
	Add(s[n], 1), Add(s[n] + 1, - 1);
	int L = 0, R = 0;
	rep(r, 1, n) {
		Add(s[n] + L + r - 2 * s[r], 1);
		Add(s[n] + R + r - 2 * s[r] + 1, - 1);
		L = min(L, 2 * s[r] - r);
		R = max(R, 2 * s[r] - r);
	}
	int ans = 0;
	rep(i, 0, n) if(Ask(i) > 0) ans ++;
	printf("%d\n", ans);
	return 0;
}

实际上，更进一步，发现 \(r-2s_r\) 的变化量也 \(\leq 1\)，所以最终答案也是一段区间。

那只要求最大/最小即可，把 \(0\) 赋值为 \(1\)，\(1\) 赋值为 \(-1\)，相当于求最大/最小子段和，经典贪心。

C - Distinct Numbers

给定一个严格递增的非负整数序列，每轮要求将最大值减少并重新插回序列。

要求序列元素依然非负且严格递增（不能有重复元素），不能操作者判负，Alice 先手，求谁必胜。

比较人类智慧的博弈题（

若 \(a_n>a_{n-1}+1\)，那么先手是必胜的，因为如果存在将最大值减小的必胜策略，那么先手会执行。

否则先手会将 \(a_n\) 移动到 \(a_{n-1}+1\)，然后将这个必败态给后手，先手依然必胜。

否则，一开始 \(a_n=a_{n-1}+1\)，显然大家都不能让对方取到 \(a_n>a_{n-1}+1\) 的局面，那么每次最大值一定是 \(-1\)，而且慢慢递减的。

最终的胜负就由 \(a_n-(n-1)\) 的奇偶性决定。

const int N = 3e5 + 10;
int n, a[N];

int main() {
	n = read();
	rep(i, 1, n) a[i] = read();
	if(a[n] > a[n - 1] + 1) puts("Alice");
	else puts(((a[n] - (n - 1)) & 1) ? "Alice" : "Bob");
	return 0;
}

D - Prefix XORs

给定长度为 \(n\) 的序列，每次操作进行一次异或前缀和，即 \(i=1\to n,a_i\gets a_i\oplus a_{i-1}\)。

求 \(m\) 轮操作中，每一轮的 \(a_n\)。

降智（

显然，第 \(k\) 轮有贡献的就是 \(\displaystyle \binom{(n-i)+(k-1)}{k-1}\) 为奇数的那些 \(i\)。

根据 Lucas 定理，相当于二进制下，\(k-1\) 是 \((n-i)+(k-1)\) 的子集。

赛时到这就想不动了，实际上，这等价于 \((n-i)\) 和 \((k-1)\) 的二进制无交集，否则一定有进位，无论怎么进位一定会不满足条件。

然后就是高维前缀和的事了。

const int N = 1e6 + 10;
const int M = 1 << 20;
int n, m, o, f[M];

int main() {
	n = read(), m = read();
	rep(i, 1, n) f[n - i] = read();
	int x = max(n, m);
	while(x) x >>= 1, o ++;
	rep(j, 0, o - 1)
		rep(i, 0, (1 << o) - 1)
			if(i >> j & 1) f[i] ^= f[i ^ (1 << j)];
	int s = (1 << o) - 1;
	rep(i, 1, m)
		printf("%d ", f[s - (i - 1)]); puts("");
	return 0;
}

E - Bakery

开面包店，有 \(n\) 天，每次最多能卖出 \(a_i\) 块面包，面包不能过夜，每块卖出的面包得到 \(D\) 元。

有 \(m\) 个人可以雇佣，第 \(i\) 个人会工作从 \(l_i\) 到 \(r_i\) 天，每天生产 \(1\) 块面包，需要 \(c_i\) 元雇佣。

求最大利润。

和人员雇佣很像，不难得到经典的费用流建模：

• 对于 \(i\in[1,n]\)，连边 \((i-1,i,m-a_i,0),(i-1,i,a_i,D)\)。
• 连边 \((s,0,m,0)\).
• 对于 \(i\in[1,m]\)，连边 \((l_i-1,r_i,1,c_i)\)。
• 汇点 \(t=n\)。

求 \(s,t\) 的最小费用最大流，\((D\times \sum a)-\text{cost}\) 就是答案。（AtCoder Library 超好用的）

#include 
using namespace atcoder;

int main() {
	int n = read(), m = read(), D = read();
	int s = n + 1, t = n;
	mcf_graph G(s + 1);
	LL ans = 0;
	rep(i, 1, n) {
		int a = read();
		ans += 1LL * a * D;
		G.add_edge(i - 1, i, a, D);
		G.add_edge(i - 1, i, m - a, 0);
	}
	G.add_edge(s, 0, m, 0);
	rep(i, 1, m) {
		int l = read(), r = read(), c = read();
		G.add_edge(l - 1, r, 1, c);
	}
	printf("%lld\n", ans - G.flow(s, t).second);
	return 0;
}