CCPC2021威海站部分题解 A D E G J M

比赛传送门：Dashboard - The 2021 CCPC Weihai Onsite - Codeforces

A. Goodbye, Ziyin!（签到 + 树）

签到题。

给定一颗无根树（没有指定根的，意味着任何一点都可以为根），问有多少个点作为根可以使得整棵树为一颗二叉树。

对于签到的树题，一般都不需要建树，只需要记录度数。我们想一下二叉树的特征：根的度数\(\le 2\)，其余点的度数\(\le 3\)。

那么就预先判断一下是否存在度数\(>3\)的点，如果存在则答案一定为0。

如果不存在，说明答案非0，那么答案就是度数\(le 2\)的点的个数咯，遍历一下就好了。

#include 
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int d[maxn];

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N;cin >> N;
	
	bool tag = true;//答案不为0 
	for(int i = 2;i <= N; ++ i)
	{
		int x, y;cin >> x >> y;
		d[x] ++, d[y] ++;
		if(d[x] > 3 || d[y] > 3)tag = false;//存在度数>3的，答案为0 
	}
	int ans = 0;
	for(int i = 1;i <= N; ++ i)if(d[i] < 3)ans ++;
	cout << (tag ? ans : 0) << '\n';
	
	return 0;
}

D. Period（DP + 字符串Hash）

这道题也接近签到，给定一个只包含小写字母的字符串s，然后有q次询问，每次询问将第i个字符改为‘#’后，这个字符串的相同前后缀的个数为多少？

首先肯定这个答案不会超过N / 2（N是字符串长度），因为'#'会将字符串从中间截断。如果询问的位置是大于N / 2的只需要镜像地翻转x下标就好了。

看到“相同前后缀”容易让人想到kmp，但是kmp在竞赛中的作用基本能被string hash完全代替，而且string hash还好理解，为啥不用hash呢？

我们用dp[i]表示到第i位为止（第i + 1位是'#'）的情况下的相同前后缀的最大个数，这个可以通过hash用O(1)算出来。转移也很好写，就是判断是否相等+1就行了（和前缀和类似）。

复杂度O(max(N, M))。

#include 
#define int long long
using namespace std;
const int maxn = 1e6 + 9, base = 1331;
typedef unsigned long long ULL;
ULL h[maxn], b[maxn];
char s[maxn];
int dp[maxn];

int getHash(int l, int r){return h[r] - h[l - 1] * b[r - l + 1];}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> s + 1;
	int N = strlen(s + 1);
	b[0] = 1;
	for(int i = 1;i <= N; ++ i)
	{
		h[i] = h[i - 1] * base + s[i] - '0' + 17;
		b[i] = b[i - 1] * base;
	}
	for(int i = 1;i <= N / 2; ++ i)
	{
		//dp[i]表示从[1, i]有多少各前缀是和后缀相等的 
		dp[i] = dp[i - 1] + (int)(getHash(1, i) == getHash(N + 1 - i, N));
	}
	
	int M;cin >> M;
	while(M --)
	{
		int x;cin >> x;
		if(x > N / 2)x = N + 1 - x;//镜像反转x的下标 
		//第x位是#，那么应该输出dp[x - 1] 
		cout << dp[x - 1] << '\n';
	}
	return 0;
}

G. Shinyruo and KFC（组合计数）

给了n种食物，每种食物有\(a_{i}\)个（\(0\le a_{i} \le 10^5\)），将其分为k组(k = 1, 2, 3, ... , m)，一组中的同种食物不能超过一个，问有多少种分法？

首先算一下食物个数的最大值mx，若\(k

当\(k \ge mx\)时，对于每一种食物，都有\(C_{k}^{a_{i}}\)种分法，相当于说是在k组中选出\(a_{i}\)组每组给一个，剩下的就不给。计算出每一个ai的组合数再加入到答案。

现在就可以计算了，k从1到M，每一次计算如果要遍历整个a数组，那肯定超时，复杂度是O(N * M)，但是注意到有一个条件：ai之和不超过1e5，现在N又有5e4这么大，那么ai的种类数一定不会多，最多是1e2.5的级别。

如果可以把{ai，个数cnt}作为一个pair存下来，后面计算的时候直接将ai方案数求cnt次幂加到答案里就好了。

这里的处理可以考虑用map，然后用vector >存下来加速遍历过程，在求组合数的时候需要预处理阶乘和阶乘的逆元。

最后直接计算就好了，复杂度O(M * sqrt(1e5))。

#include 
#include 
#define int long long
using namespace std;
const int maxn = 1e5 + 9, p = 998244353;
int fac[maxn], invfac[maxn];
//下面这个数据类型换成unordered_map或者map都行，不过pbds会快一些。
__gnu_pbds::gp_hash_table mp;

int qmi(int a,int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)res = res * a % p;
		a = a * a % p, b >>= 1;
	}
	return res;
}

int inv(int x){return qmi(x, p - 2);}

int C(int n, int m)
{
	return fac[n] * invfac[n - m] % p * invfac[m] % p;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, M;cin >> N >> M;
	
	fac[0] = 1, invfac[0] = 1;
	for(int i = 1;i <= 1e5 + 3; ++ i)fac[i] = fac[i - 1] * i % p;
	for(int i = 1;i <= 1e5 + 3; ++ i)invfac[i] = inv(fac[i]);
	
	int mx = 0;
	for(int i = 1;i <= N; ++ i)
	{
		int x;cin >> x;
		if(x)mp[x] ++;//x = 0不用加入 
		mx = max(mx, x);
	}
	vector > vp;
	for(auto &i : mp)vp.push_back({i.first, i.second});
	
	for(int i = 1;i <= M; ++ i)
	{
		if(i < mx)
		{
			cout << 0 << '\n';
			continue;
		}
		
		int ans = 1;
		for(auto &j : vp)ans = ans * qmi(C(i, j.first), j.second) % p;
		cout << ans << '\n';
	}
	
	return 0;
}

J. Circular Billiard Table（几何 + 数论）

首先我们初中就学过：正圆中一条弦的弦切角等于圆心角的一半，也很容易推出来。

设角度为\(q = a / b\)。

那么现在问题就来了，如果要使得这个台球能回到原来的位置，就需要满足\(k_{1} * 2q = 360k_{2}\)，这个是必然满足的，因为k1和k2都是自由的，无论q取什么我都可以让k2 = 2 * q，k1 = 360使得等式成立，所以现在问题变为找k1的最小正整数解。

我们将q写成a / b的形式，得到等式\(k1 = 180bk_{2}/a\)，为了使得\(k_{1}\)是整数且最小，只需要让\(180b/a\)化为最简分数，此时分子分母互质，然后\(k_{2}\)等于分母即可使得\(k_{1}\)取得最小正整数解。

用gcd搞一下就好啦，复杂度O(T * log(max(a, b)))。

#include 
#define int long long
using namespace std;
const int maxn = 1e6 + 9;

int gcd(int a,int b)
{
	return b == 0 ? a : gcd(b, a % b);
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _;cin >> _;
	while(_ --)
	{
		int a, b;cin >> a >> b;
		int d = gcd(180 * b, a);
		cout << 180 * b / d - 1 << '\n';
	}
	return 0;
}

E. CHASE!（概率 + 双指针 + 前缀和）

感觉前面四题都比较简单，这题开始上难度了。

给了N个数字，每次选两个数字相加得到一个得分（score），每次选数字都是等概率的，有k次机会可以选择“重开”，即重新选择两个数字，问有k次重开机会的情况下，得分的期望是多少？

并且还有q次询问，每次询问是当选择了第x和第y个数字且还有最多c次重开机会的情况下要不要选择重开？或或者都可？

我们先考虑没有重开的情况下的期望，应该是所有二元组的和除以二元组的数量，每一个a[i]会出现在N - 1个二元组中，所以\(e_{0} = \sum_{i = 1}^{N}a_{i} * (N - 1) / M\)其中\(M = N * (N - 1) / 2\)。

现在考虑有一次重开机会的情况下的期望，如果有一次重开机会，对于每个二元组，当二元组的和>=e[i - 1]时我们不重开，如果重开的话这个二元组的期望就变为e[i - 1]而非现在的和了，当然不值得。

如果一个二元组的和<=e[i - 1]，那么就用e[i - 1]将这个和替换掉，这个二元组的期望就变为e[i - 1]了，不难发现e是随着重开机会增加而不断增大的，最终会逼近最大的二元组之和（可以理解为只要不是最大就一直换，直到拿到最大的二元组）。

这里有一个问题就是如何计算哪些二元组是可以替换的而哪些不行，容易想到排序后二分，这个确实好理解，但是这题可以用双指针来完成，不必用二分了。l逐步向右走，当a[l] + a[r] < e[i - 1]时说明二元组(a[l], a[l + 1 ~ r])都可以用e[i - 1]替换掉。我们以e[0]为基础进行替换计算，预先处理一下前缀和，就ok了。

至于后面的q次询问，只要判断a[x] + a[y]和e[c - 1]的大小关系就好了，注意特判 c = 0的情况，只能accept。

解释一下，这里比较e[c - 1]的含义是：现在剩下c次机会可以重开，已知期望随着重开次数增大而增大，为了使得期望最大，肯定会重开c次，那么第c次重开的期望 = 已经重开了c - 1次之后再重开一次的期望。

这里不能看作已经重开K-c次，因为现在是已经知道我选啥了，应该看作一个重新进行的游戏。

#include 
#define int long long
using namespace std;
//CHASE!
const int maxn = 1e5 + 9;
const double eps = 1e-4;
int N, K, Q;
int a[maxn], b[maxn], prefix[maxn];
double e[maxn];


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> K >> Q;
	for(int i = 1;i <= N; ++ i)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	sort(a + 1,a + 1 + N);
	for(int i = 1;i <= N; ++ i)prefix[i] = prefix[i - 1] + a[i];
	e[0] = prefix[N] * 2.0 / N;
	for(int i = 1;i <= K; ++ i)
	{
		int l = 1, r = N;
		double sum = 0;
		while(l <= r)
		{
			if(a[l] + a[r] <= e[i - 1])sum += (r - l) * e[i - 1], l ++;
			else sum += (r - l) * a[r] + prefix[r - 1] - prefix[l - 1], r --;
		}
		e[i] = sum * 2.0 / (N * (N - 1));
	}
	cout << fixed << setprecision(10) << e[K] << '\n';
	
	while(Q --)
	{
		int x, y, c;cin >> x >> y >> c;
		int s = b[x] + b[y];
		if(c == 0)cout << "accept" << '\n';
		else if(s < e[c - 1] - eps)cout << "reselect" << '\n';
		else if(s > e[c - 1] + eps)cout << "accept" << '\n';
		else cout << "both" << '\n'; 
	}
	
	
	return 0;
}

M. 810975（组合计数）

题目大意是进行N场比赛，赢了M场，其中最长连胜为K场（至少有一个K连胜，不允许出现K + 1连胜）的方案数有多少种。

首先考虑在N场比赛中赢了M场的方案数有多少，不难算出是：

模型转化：可以理解为用败场去分割所有比赛，现在就相当于有N个球，N-M个板子将整个空间划分为N - M + 1个区域，每个区域可能有0~K个球，后面的分析都基于这个模型。

我们可以写一个这样的函数f(n, m, k)：当进行n场比赛，赢了m场，且至少有一个连胜大于等于k的方案数。相当于是说在上面这个板子和球的模型中，有至少一个区域的球个数大于等于k（可能有1、2、3、4...个区域，可能有k、k+1、k+2...个球）。

那么答案就可以通过一个容斥算出：

现在的问题就是如何来写这个f函数。

回到上面的模型，现在我们要求至少有一个区域的球数量大于等于k，那么我们先拿k个球到手上，把剩下的n - k个球按照之前的方法排好，再往n - m + 1个区域中选择一个区域将这K个球放入即可。

上面这个组合数解释一下：先把板子也看作球，开始有N - K个球，然后选择N - M个变为板子（注意后面也要用到这个性质，板子的数量是不变的），自然就剩下M - K个球了，再乘上我们手上的K个球可以放入的区域数。

但是这样会出现重复，假如我们把区域划分为A,B,C其中球的个数一开始为1,2,3，然后我们把3个球放入A区域得到4,2,3，还有可能是一开始区域划分得到4,2,0，在把3个球放入C区域得到4,2,3他们其实是同一种方案却被算作了两种方案，显然会出问题，我们就需要将有2个区域已经>=K的情况删除掉，但是这样又删多了，再把有3个区域的加上，又加多了，再把有4个区域的减去....。最终是下面的表达式：

当然，上面的代码也可以通过生成函数导出，再配合奇加偶减的容斥原理。

代码如下

#include 
#define int long long
using namespace std;
const int maxn = 1e5 + 9, p = 998244353;
int fac[maxn], invfac[maxn];

int qmi(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)res = res * a % p;
		a = a * a % p, b >>= 1;
	}
	return res;
}

int C(int n,int m)
{
	if(n < m)return 0;
	return fac[n] * invfac[n - m] % p * invfac[m] % p;
}

int f(int n, int m, int k)//至少一个 >= k 
{
	int res = 0;
	for(int i = 1;i <= n; ++ i)//人为设置i个 >= k 
	{
		res += ((i & 1) ? 1 : -1) * C(n - m + 1, i) * C(n - i * k, n - m);
		res = (res % p + p) % p;
	}
	return res;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int n, m, k;cin >> n >> m >> k;
	fac[0] = 1, invfac[0] = 1;
	for(int i = 1;i <= n; ++ i)fac[i] = fac[i - 1] * i % p, invfac[i] = qmi(fac[i], p - 2);
	
	if(k == 0)cout << (int)(m == 0) << '\n';
	else cout << ((f(n, m, k) - f(n, m, k + 1)) % p + p) % p << '\n';
	
	return 0;
}