AGC024 解题记录

### A Fairness
题意：三个人做游戏，每个人开始有一个数$A,B,C$。每一次一个人会用其它两个人的数的和替换自己的数，做$k$次操作，问最后$A$的减去$B$的是多少。如果答案绝对值超过$10^{18}$输出"Unfair"。 $A,B,C\le 10^9\ k\le 10^{18}$

题解：printf("%d",(k&1)?B-A:A-B)，即可$AC$。
我们归纳证明：
$A,B,C\to\\ B+C,A+C,A+B\to\\ 2A+B+C,A+2B+C,A+B+2C$
设$A+B+C=S$那么$A+S,B+S,C+S$
$S$的存在不影响答案，等价于$A,B,C$。
得证

### B Backfront
题意：给你一个$N$的排列，每一次可以任意选一个数放到前面或者后面。问至少多少次操作把它排成升序。
$N\le 2\times 10^5$

题解：水题，考虑最后剩在最中间的一段，一定是最长的值域连续且上升的子序列。开一个$dp$数组表示到当前位置以$i$为结尾的最长值域连续上升子序列，每次转移只有一个会被影响。
$O(N)$

### C Sequence Growing Easy

题意：给你长度为$N$的序列$A$，问你可不可以把长度为$N$的全$0$序列通过以下操作操作成$A$。$N\le 10^5$

题解：考虑什么时候不合法。发现要合法一定是从$0$开始的山丘形，并且每一个上升段必须连续。构造最小的答案我们可以贪心，考虑对连续一段相等的$A_i$怎么构造出。最优的解法肯定是找到前面第一个$A_i-1$，然后一路铺到最后一个，再一路铺回去。时间复杂度$O(N)$

### D Isomorphism Freak

题意：一棵有颜色的树对于两个$u,v$如果同色则有：$u$做根形成的树与$v$做根形成的树相同。你现在可以给这棵树加一些点，问加完点后树最少能有多少种颜色。

题解：发现树一定是以一个点/一条边为根，然后以这个根向下，深度相同的点度数相同——实际上等价于子树全部同构。可以对于每一层的点单独处理，不难发现每一层点最小的度数就是原树度数最大点的度数。直接乘出答案就行了。最无脑的做法枚举这一个点/一条边即可。复杂度$O(n^2)$。但是实际上发现答案跟直径密切相关，因为直径上的点颜色最优一定是对称分布的，是一个下界。这样可以简化为$O(n)$。

### E Sequence Growing Hard

题意：你需要统计有多少大小为$n$，元素范围在$[1,K]$的序列组$A$满足
1、$A_i$长度为$i$
2、$A_i$是$A_{i+1}$的子序列
3、$A_i$的字典序严格小于$A_{i + 1}$

题解：当时暑假集训的题。
网上很多什么树形$dp$的做法，不是很懂。
每一次字典序要严格变大，那么新的数一定大于等于原来的。
考虑从小到大来增量，发现放等于原来的会算重，那么强行规定不能放在连通块中靠后的位置，如$4,4,4,5\to 4,4,4,4,5$中$4$只能放在第一个位置。
设$f(i,j,k)$表示长度为$i$，放到第$j$大的数，有$k$个能放的位置就可以了。
当前位置放：$f(i,j,k)\times (k+1)\to f(i+1,j,k)$
当前位置不放：$f(i,j,k)\to f(i,j,k-1)$
当前数放完：$f(i,j,k)\to f(i,j+1,i)$
```
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 3e2 + 5;
 
int mod, n, k;
LL dp[maxn][maxn][maxn], ans;
 
int main() {
	scanf("%d%d%d", &n, &k, &mod);
	dp[0][1][0] = 1;
	for(register int i = 0; i <= n; ++i)
		for(register int j = 1; j <= k; ++j)
			for(register int p = i; p >= 0; --p) {
				if(p) (dp[i][j][p - 1] += dp[i][j][p]) %= mod;
				else (dp[i][j + 1][i] += dp[i][j][p]) %= mod;
				(dp[i + 1][j][p] += dp[i][j][p] * (p + 1)) %= mod;
			}
	printf("%lld", dp[n][k + 1][n]);
	return 0;
}
```

### F Simple Subsequence Problem
做不起，告辞了。

Rockdu's Blog

导航

最近发表

大佬们的友链