比赛传送门: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))。 首先我们初中就学过:正圆中一条弦的弦切角等于圆心角的一半,也很容易推出来。 设角度为\(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)))。 感觉前面四题都比较简单,这题开始上难度了。 给了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次,因为现在是已经知道我选啥了,应该看作一个重新进行的游戏。 题目大意是进行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
J. Circular Billiard Table(几何 + 数论)
#include
E. CHASE!(概率 + 双指针 + 前缀和)
#include
M. 810975(组合计数)
#include
Comments 1 条评论
D 超时