经验总结

  1. 首页 > 生活 > >

题解 2021 CCPC 威海站 VP记录

生活百科

2021 CCPC 威海站 VP记录(题解)题目顺序为vp时开题顺序:
A - Goodbye, Ziyin!签到，连边数小于等于2的可以作为二叉树根，若有大于4的直接输出0 。code:
void solve(){ int n; cin >> n; map<int,int> cnt; for (int i = 0;i < n - 1;i ++) {int x,y;cin >> x >> y;cnt[x]++;cnt[y]++; } int ans = 0; for (auto [u,v] : cnt) {if(v >= 4) {cout << 0 << endl;return ;}else if(v <= 2) ans++; } cout << ans << endl;}J - Circular Billiard Table分析:每次碰撞圆心角不会改变，根据这个性质，可以推出回到原点时一定走过了\(360^{\circ}\)的倍数，可以推出公式(代码来自队友)code:
void car(){a*=2;ll c=360*b;ll d=c/__gcd(c,a)*a;cout<<d/a-1<<endl;}signed main(){ios::sync_with_stdio(false);cin>>t;while(t--){cin>>a>>b;car();}cerr<<endl<<"carnation13"<<endl;return 0;}M 810975【题解 2021 CCPC 威海站 VP记录】题意:n局游戏，赢了m场，连胜最多为k场，求最后方案数分析:典型隔板法，如果没有连胜最多为k场这个条件，就是经典公式了\(ans = \binom{n - m}{n + m - 1}\)(发现离散学的这个公式蛮方便的) 。解释下这个公式，其实就是隔板放球的模型，把赢得局想成球，输的局想成板，那就是\(n + m -1\)个地方放\(n - m\)个板（可重复组合问题) 。然后为了满足最多连胜为k场，在vp的时候和队友推了下感觉正推不好做，于是可以想到用容斥去算出来不合法的方案数，最后用总方案数减去不合法的方案数即可 。考虑不合法的方案数，我们可以这么考虑，有\(n - m + 1\)段是连胜的区间，那我们可以类似于devu和鲜花那题，把每一段恰好为\(k + 1\)的情况给算出来容斥掉，就是最后的答案了 。所以公式为:
\[ans = \binom{n + m - 1}{n - m} + \sum_{i = 1}^{n - m + 1}((-1)^{i+1}*\binom{n - m + 1}{i}*\binom{n - i * (k + 1)}{n - m})\]稍微解释一下，这里的\(i\)表示\(n + + m - 1\)段连胜段里选取\(i\)段，且这\(i\)段正好为连胜\(k + 1\)场的情况 。然后这个公式对应的是连胜最多场数小于等于\(k\)场的情况，减去小于等于\(k-1\)的方案数就是最后答案啦
int cal(int n,int m,int k) { int res = 0; res = C(n + m - 1,n - m); int neg = 1; for (int i = 0;i <= n - m + 1;i ++) {// if(i * (k + 1) >= m) break;res = (res + neg * C(n - m + 1 , i) % mod * C(n - i * (k + 1),n - m) % mod) % mod;res = (res + mod) % mod;neg = -neg; } return res;}void solve(){ int n,m,k; cin >> n >> m >> k; int ans = 0; if(n < m || k > m) {cout << 0 << endl;return ; } ans = cal(n,m,k) - cal(n,m,k - 1); ans = (ans % mod + mod) % mod; cout << ans << endl;}G - Shinyruo and KFC分析：非常明显的暴力题，题目限定了数据范围是所有数总和小于等于2e5,所以他肯定是两种情况，要么最大的数特别大，前面的都不用算，要么是最大的数不太大，会变成有点类似于分块的处理方法 。在同一块内的组合数一起算掉就可以了(这其实是我赛场口胡的，队友听完后打了一个桶思想的代码顺利ac，可能直接看大佬队友的代码就可以了)code:
signed main(){ init(); ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); cin>>q>>w; for(i=1;i<=q;i++) {cin>>f[i];ton[f[i]]++; } sort(f+1,f+1+q); for(i=1;i<=q;i++) {if(f[i]!=f[i-1])cnt++;g[cnt]=f[i]; } maxn=min(g[cnt],w); for(i=1;i<maxn;i++) cout<<0<<endl; for(i=maxn;i<=w;i++) {ans=1;for(int j=1;j<=cnt;j++){//cout<<i<<" "<<f[j]<<" "<<C(i,f[j])<<endl;ans=ans*qmi(C(i,g[j]),ton[g[j]])%mod;}cout<<ans<<endl; }}D - Period分析：哈希暴力水题，我队因为一直在想kmp做法一直wa（字符串确实不太会)，后来发现暴力hash即可，没啥好说的看代码(来自队友)吧qwq(过的人第三多的签到题了)code:

经验总结扩展阅读


上一篇：2023年农历八月廿七穿丧服吉日 2023年10月11日是穿丧服的黄道吉日吗

下一篇：2023年2月11日是收养孩子吉日吗 2023年2月11日收养孩子好不好