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題意:n局游戲，贏了m??，连胜最掇\猭場，求最后方案數分析:典型隔板法，如果沒有連勝最多為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})\]【題解 2021 CCPC 威海站 VP記錄】稍微解釋一下，這里的\(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:
#include<bits/stdc++.h>using namespace std;typedef long long unsigned ll;#define rep(i,a,b) for(ll i=a;i<=b;++i)#define per(i,a,b) for(ll i=a;i>=b;--i)const ll N=1000005,base=131,mod=212370440130137957ll;ll n,m,k,q,now=0,c[N];char s[N];signed main(){//ios::sync_with_stdio(false);scanf("%s",s+1);n=strlen(s+1);ll a=0,b=0,w=1;for(ll i=1;i<=n;++i){a=(a*base+s[i]);//cout<<a<<" ";b=((w*s[n-i+1])+b);w=(w*base);//cout<<b<<endl;if(a==b)c[i]=++now;else c[i]=now;}//for(ll i=1;i<=n;++i)cout<<c[i]<<" ";cout<<endl;scanf("%lld",&q);for(ll i=1;i<=q;++i){ll x;scanf("%lld",&x);ll mi=min(x,n-x+1)-1;printf("%lld\n",c[mi]);}//cerr<<endl<<"carnation13"<<endl;return 0;}總結:新隊伍的第二場vp，比上一場簽完到就各種痛苦wa不會寫的情況要好一點，五題其實是在三個小時多點的時候完成的 ， 如果是實際比賽可能能出更多的題（可能吧），這個賽季加油了 。

推薦閱讀