AGC030 解题记录

### A Poisonous Cookies

没什么写头，纯贪心，随便贪贪心就行了。

### B Tree Burning

题意：在一个长为L的环上，你一开始在0处。给定一些关键点的坐标。你可以重复做如下事情：选择一个方向，走到方向上第一个关键点停下并标记。当所有关键点都被标记时停止。问你最长能走多远。点数$2\times 10^5$

题解：直接考虑每一段被经过多少次不好考虑。可以把到一个关键点再回到0的过程看成一次操作。这样每一条路径都是先进行很多次操作，最后从0到某个点。因为每一次肯定是左一个右一个，考虑枚举最后一个点，那么左右肯定是从大到小抵消并且一边要取完，分开始方向和结束方向讨论就只有4种情况，复杂度$O(n)$。

code
```
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 2e5 + 5;
int n, a[maxn], b[maxn], L, num;
LL suma[maxn], sumb[maxn], ans;
 
int main() {
	scanf("%d%d", &L, &n);
	for(register int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		b[i] = L - a[i];
	}
	for(register int i = 1; i <= n; ++i) {
		suma[i] = suma[i - 1] + a[i];
		sumb[i] = sumb[i - 1] + b[i];
	}
	sumb[n + 1] = sumb[n];
	for(register int i = 1; i <= n; ++i) {
		num = min(n - i, i);
		ans = max(ans, a[i] + (suma[i - 1] - suma[i - num] + sumb[i + num] - sumb[i]) * 2);
		if(i < n) ans = max(ans, b[i + 1] + (suma[i] - suma[i - num] + sumb[i + num] - sumb[i + 1]) * 2);
	}
	ans = max(ans, (LL)b[1]);
	for(register int i = 1; i <= n; ++i) {
		num = min(n - i, i - 1);
		ans = max(ans, (suma[i - 1] - suma[i - 1 - num] + sumb[i + num] - sumb[i]) * 2 + max(a[i], b[i]));
	}
	printf("%lld\n", ans);
	return 0;
}
```

### C Coloring Torus

题意：在$n\times n$的网格里填上$K\le 1000$种颜色，$n$自己定且$1\le n\le 500$。
要求构造一种方法使得对于任意颜色$i,j\in[1,K](i,j可以相等)$满足对于每一个$i$的方块，相邻的$j$的方块个数都一样。这里认为上边界和下边界相邻，左边界和右边界相邻。

题解：构造妙妙题，看了题解。$K$是偶数的时候是很好做的，考虑一行全部填$1\to K$，下一行接着填$K+1\to 2K$。交替填就可以了。
$K$是奇数的时候需要一个神构造。
我们发现一行的灵活性是很高的。
考虑这样构造，首先复制$1 - n/2$做轮转：
```
12345
23451
34512
45123
51234
```
然后我们把偶数行全部加$K$
```
12345
789X6
34512
9X678
51234
```
此时矩阵仍然符合条件，但有了更好的性质：
将任意$i$颜色全部替换为$i+K$颜色后都是合法方案。

Code
```
#include<cstdio>
using namespace std;
int mp[505][505], n, N;
 
int main() {
	scanf("%d", &n);
	if(n == 1) {
		printf("1\n1");
		return 0;
	}
	N = ((n + 3) / 4) * 2;
	printf("%d\n", N);
	for(register int i = 0; i < N; ++i) {
		for(register int j = 0; j < N; ++j) {
			mp[i][j] = ((i) & 1) * N + ((i + j) % N);
			if(mp[i][j] >= n) mp[i][j] = mp[i][j] % N;
			printf("%d ", mp[i][j] + 1);
		}
		putchar('\n');
	}
	return 0;
}
```

### D Inversion Sum

题意：一个长为$n$的序列，依次有$q$个操作，每个操作是交换两个位置上的数，每个操作可能出现或者不出现。求每种情况下的逆序对数之和。$n\le 5000$

题解：跟雅礼集训的一道题很像，考虑倒推，$f(i,j,k)$表示从第$i$个操作一直进行到最后$j$在$k$前面的情况有多少种。但是发现因为操作只交换两个数转移很有限，其它的都是在原来的基础上乘个$2$，那么我们直接维护偏移值，每次处理$f(i,l[x]),f(i,r[x]),f(l[x],i),f(r[x],i)$就可以了。
看完题解发现实际上本质是概率，可以直接$DP$概率，省区维护偏移值的步骤。

```
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 3e3 + 5;
const int mod = 1e9 + 7;
int f[maxn][maxn], n, a[maxn], p2c[maxn][maxn], q;
int l[maxn], r[maxn], tmp[maxn], ptmp[maxn];
int pow2[maxn], ans, tmpl, tmpr;
inline int mul(const int &a, const int &b) {
	return 1ll * a * b % mod;
}
inline void Add(int &a, const int &b) {
	a = a + b >= mod ? a + b - mod : a + b;
}
inline int Minus(const int &a, const int &b) {
	return a - b < 0 ? a - b + mod : a - b;
}
int main() {
	scanf("%d%d", &n, &q), pow2[0] = 1;
	for(register int i = 1; i <= q; ++i)
		pow2[i] = pow2[i - 1] * 2 % mod;
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(register int i = 1; i <= q; ++i) {
		scanf("%d%d", &l[i], &r[i]);
		if(l[i] > r[i]) swap(l[i], r[i]);
	}
	for(register int i = 1; i <= n; ++i)
		for(register int j = i + 1; j <= n; ++j)
			f[i][j] = 1;
	reverse(l + 1, l + q + 1);
	reverse(r + 1, r + q + 1);
	for(register int i = 1; i <= q; ++i) {
		for(register int j = 1; j <= n; ++j)
			tmp[j] = f[j][r[i]], ptmp[j] = p2c[j][r[i]];
		for(register int j = 1; j <= n; ++j) {
			if(j == l[i] || j == r[i]) continue;
			f[j][r[i]] = mul(f[j][r[i]], pow2[i + p2c[j][r[i]] - 1]);
			f[j][l[i]] = mul(f[j][l[i]], pow2[i + p2c[j][l[i]] - 1]);
			tmpl = f[j][l[i]], tmpr = f[j][r[i]];
			Add(f[j][r[i]], tmpl);
			Add(f[j][l[i]], tmpr);
			f[r[i]][j] = Minus(pow2[i], f[j][r[i]]);
			f[l[i]][j] = Minus(pow2[i], f[j][l[i]]);
			p2c[j][l[i]] = p2c[j][r[i]] = -i;
			p2c[l[i]][j] = p2c[r[i]][j] = -i;
		}
		p2c[l[i]][r[i]] = -i;
		f[l[i]][r[i]] = pow2[i - 1];
		p2c[r[i]][l[i]] = -i;
		f[r[i]][l[i]] = pow2[i - 1];
		/*for(register int j = 1; j <= n; ++j) {
			for(register int k = 1; k <= n; ++k) {
				//f[i][j] = mul(f[i][j], pow2[q + p2c[i][j]]);
				printf("%d ", mul(f[j][k], pow2[i + p2c[j][k]]));
			}
			putchar('\n');
		}*/
	}
	for(register int i = 1; i <= n; ++i) {
		for(register int j = i + 1; j <= n; ++j) {
			f[i][j] = mul(f[i][j], pow2[q + p2c[i][j]]);
			if(a[i] > a[j]) Add(ans, f[i][j]);
			else if(a[i] < a[j]) Add(ans, Minus(pow2[q], f[i][j]));
		}
	}
	printf("%d", ans);
	return 0;
}
```

### E Less than 3

题意：给你$0/1$初始串$S$目标串$T$，你每次可以选择翻转一个位置的$0/1$，但是全程不能有连续的$3$个相同的$0/1$。

很神的题，根本想不到，一步神奇转化后就很简单了，题解写的很清楚：
https://img.atcoder.jp/agc030/editorial.pdf

code
```
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2e4 + 5;
char s[maxn], t[maxn];
int n, ps[maxn], pt[maxn], cs, ct, ans = 1 << 30, nans;
int tmps[maxn], tmpt[maxn];

int GetAns(int x) {
	int r = max(x + cs, ct), ts = 0;
	int l = min(x, 0), tt = 0, nans = 0;
	for(register int i = l; i < r; ++i) {
		if(i >= x && i < x + cs) tmps[++ts] = ps[i - x];
		if(i < x) tmps[++ts] = -1;
		if(i >= x + cs) tmps[++ts] = n - 1;
		if(i >= 0 && i < ct) tmpt[++tt] = pt[i];
		if(i < 0) tmpt[++tt] = -1;
		if(i >= ct) tmpt[++tt] = n - 1;
	}
	for(register int i = 1; i <= ts; ++i) {
		nans += abs(tmps[i] - tmpt[i]);
	}
	return nans;
}

int main() {
	scanf("%d", &n);
	scanf("%s%s", s, t);
	if(s[0] == '0') ps[cs++] = -1;
	if(t[0] == '0') pt[ct++] = -1;
	for(register int i = 0; i < n - 1; ++i) {
		if(s[i] != s[i + 1]) ps[cs++] = i;
		if(t[i] != t[i + 1]) pt[ct++] = i;
	}
	for(register int i = -cs; i <= ct; ++i) {
		if(abs(i) & 1) continue;
		ans = min(ans, GetAns(i));
	}
	printf("%d", ans);
	return 0;
}
```

### F Permutation and Minimum

雅礼的原题，题意就不写了，题解大概是转化成括号序列，用一个$DP$加卡特兰数。同样可以看官方题解。

Rockdu's Blog

导航

最近发表

大佬们的友链