題目順序為vp時開題順序:
簽到，連邊數小於等於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;
}
分析:每次碰撞圓心角不會改變，根據這個性質，可以推出回到原點時一定走過了\(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;
}
題意:n局遊戲，贏了m場，連勝最多為k場，求最後方案數
分析:典型隔板法，如果沒有連勝最多為k場這個條件，就是經典公式了\(ans = \binom{n - m}{n + m - 1}\)(發現離散學的這個公式蠻方便的)。解釋下這個公式，其實就是隔板放球的模型，把贏得局想成球，輸的局想成板，那就是\(n + m -1\)個地方放\(n - m\)個板（可重複組合問題)。
然後為了滿足最多連勝為k場，在vp的時候和隊友推了下感覺正推不好做，於是可以想到用容斥去算出來不合法的方案數，最後用總方案數減去不合法的方案數即可。
考慮不合法的方案數，我們可以這麼考慮，有\(n - m + 1\)段是連勝的區間，那我們可以類似於devu和鮮花那題，把每一段恰好為\(k + 1\)的情況給算出來容斥掉，就是最後的答案了。
所以公式為:
稍微解釋一下，這裡的\(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;
}
分析：非常明顯的暴力題，題目限定了資料範圍是所有數總和小於等於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;
}
}
分析：雜湊暴力水題，我隊因為一直在想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不會寫的情況要好一點，五題其實是在三個小時多點的時候完成的，如果是實際比賽可能能出更多的題（可能吧），這個賽季加油了。