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

发布于 2022-10-09  341 次阅读


比赛传送门: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场的方案数有多少,不难算出是:

$$C_{N}^{M} = C_{N}^{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...个球)。

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

$$ans = f(n, m, k) - f(n, m, k + 1)$$

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

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

$$C_{n - k}^{n - m} * C_{n - m + 1}^{1}$$

上面这个组合数解释一下:先把板子也看作球,开始有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个区域的减去....。最终是下面的表达式:

$$f(n, m, k) = \sum_{i = 1}^{i*k \le m} -1^{i - 1} * C_{n - i * k}^{n - m} * C_{n - m + 1}^{i} $$

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

代码如下

#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;
}