https://codeforces.com/contest/1425

E. Excitation of Atoms

 

题意：有n个原子，可以选任意个激活，每个原子有激活后得到的能量与激活需要花费的能量，还有这个原子指向的另一个原子的编号，初始时所有原子指向它后一个，最后一个原子不能指向。如果一个原子处于激活状态，它所指向的原子也会自动处于激活状态，如此链式反应。要求改变K个原子的指向，问最大能净获得的能量。(4≤N≤105,0≤K<N)(4 \le N \le 10^5, 0 \le K < N)

贪心+模拟

很恶心的细节题，对着数据改程序才勉强过0.o

如果K=0，就是选一个最大的后缀。

如果K=2，激活任一点，都可以遍历所有点，设激活x，则x->1，x-1->x+1。所以只要枚举所有点作为手动激活的那个点。

如果K>2，总可以浪费掉多出的几次机会，变为K=2，如K=3时，可以x->2,x->1,x-1>x+1。

如果K=1，分两种情况：从1进入，由于K=1，所以必须跳过后面某个点，直接枚举。从后面某点进入，前面的某个前缀所有点形成一个环，环中某点作为另一个进入点。

最终结果挺短的，因为后来删掉了很多发现没用的东西。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, k;
int a[N], d[N], mn[N];
ll sum[N], mx[N], mx2[N];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
	for (int i = 1; i <= n; i++)scanf("%d", &d[i]);
	ll ans = max(0, a[n] - d[n]);
	if (k == 0) {
		for (int i = 1; i < n; i++) {
			ans = max(ans, sum[n] - sum[i - 1] - d[i]);
		}
		printf("%lld\n", ans);
		return 0;
	}
	if (k > 1) {
		for (int i = 1; i < n; i++)ans = max(ans, sum[n] - d[i]);
		printf("%lld\n", ans);
		return 0;
	}
	for (int i = 2; i <= n; i++)ans = max(ans, sum[n] - d[1] - a[i]);	//从1进入，跳过1个点
	for (int i = n; i >= 1; i--)mx2[i] = max(mx2[i + 1], sum[n] - sum[i - 1] - d[i]);	//激活i，并向后传播，后缀最大值
	mn[0] = INF;
	for (int i = 1; i <= n; i++)mn[i] = min(mn[i - 1], d[i]);
	for (int i = 1; i < n; i++) {
		ans = max(ans, max(0ll, sum[i] - mn[i]) + mx2[i + 1]);	//环是某个前缀，枚举环中编号最大的点
	}
	printf("%lld\n", ans);
	return 0;
}

 

D. Danger of Mad Snakes

 

题意：1000*1000的网格上有n条蛇，每条还有b值，要选m条攻击，每次攻击会使得这条蛇周围边长2r+1的正方形区域内所有蛇去世。一种方案的价值等于这次方案中去世的蛇的b值和的平方，问所有方案的价值之和。

二维前缀和

挺有意思的一道题

要统计所有方案的和，显然不能枚举方案，那么就只能算贡献了。

之前做的这类题都是算每个点的贡献，这里不一样，这里要算每一对点的贡献。

因为这里每个方案的价值是所有蛇的和的平方。

假设一个方案中去世的蛇为 x1,x2,⋯ ,xkx_1,x_2,\cdots,x_k

把平方拆开 (x1+x2+⋯+xk)2=x1x1+x1x2+⋯x1xk+x2x1+x2x2+⋯+x2xk+⋯+xkxk(x_1+x_2+\cdots+x_k)^2=x_1x_1+x_1x_2+\cdots x_1x_k+x_2x_1+x_2x_2+\cdots+x_2x_k+\cdots+x_kx_k。

在这个方案中，xi≠xjx_i\neq x_j 都去世了，它们对这个方案的贡献为 xixj+xjxix_ix_j+x_jx_i。

以此类推，只需要枚举两个点 xi,xjx_i,x_j，统计在几个方案中它们都去世了，则它们产生贡献。

如果是和的三次方？那么就是统计每个三元组都去世的方案数。四次方？

都去世的方案数不好直接求，可以反面求，i 没去世或 j 没去世的方案数，简单容斥，只要统计出 i，j 所在正方形中的蛇数，选中这些中任一个都会使得它去世。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e3 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m, r;
int x[N], y[N], b[N];
int c[1020][1020];
int get(int x1, int y1, int x2, int y2) {
	if (x1 > x2 || y1 > y2 || x1 < 1 || x1>1000 || y1 < 1 || y1>1000 || x2 < 1 || x2>1000 || y2 < 1 || y2>1000)return 0;
	return c[x2][y2] - c[x1 - 1][y2] - c[x2][y1 - 1] + c[x1 - 1][y1 - 1];
}
int cnt[N], lx[N], rx[N], ly[N], ry[N];
ll ans, all;
ll Co[N][N];
ll C(int n, int k) {
	if (k < 0 || n < 0 || n < k)return 0;
	return Co[n][k];
}
int main() {
	scanf("%d%d%d", &n, &m, &r);
	for (int i = 0; i <= n; i++)Co[i][i] = Co[i][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			Co[i][j] = (Co[i - 1][j - 1] + Co[i - 1][j]) % mod;
	}
	all = Co[n][m];
	for (int i = 1; i <= n; i++)scanf("%d%d%d", &x[i], &y[i], &b[i]);
	for (int i = 1; i <= n; i++) {
		c[x[i]][y[i]]++;
	}
	for (int i = 1; i <= 1000; i++) {
		for (int j = 1; j <= 1000; j++) {
			c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		lx[i] = max(1, x[i] - r); rx[i] = min(1000, x[i] + r);
		ly[i] = max(1, y[i] - r); ry[i] = min(1000, y[i] + r);
		cnt[i] = get(lx[i], ly[i], rx[i], ry[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ll A = C(n - cnt[i], m), B = C(n - cnt[j], m);
			int tmp = cnt[i] + cnt[j] - get(max(lx[i], lx[j]), max(ly[i], ly[j]), min(rx[i], rx[j]), min(ry[i], ry[j]));
			ll CC = C(n - tmp, m);
			ans = (ans + (all - A - B + CC + 2 * mod)*b[i] % mod*b[j] % mod) % mod;
		}
	}
	printf("%lld\n", ans);
	return 0;
}