A.怪盜-1412

$$\begin{array}{c}111\dots 1\\ ?\frac{n}{2}?\end{array}\begin{array}{c}444\dots 4\\ m\end{array}\begin{array}{c}111\dots 1\\ ?\frac{n}{2}?\end{array}\begin{array}{c}222\dots 2\\ k\end{array}$$
上述排列方式最優，由此根據組合數即可求解。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int main() {IO;int T=1;cin>>T;while(T--){ll n,m,k;cin>>n>>m>>k;cout<<n/2*((n+1)/2)*m*k<<'\n';}return 0; }

Dis2

與某個點距離為2的點有三種①父親的父親②兒子的兒子③兄弟節點
跑dfs統計以下即可
sz[u]表示u節點兒子的數量

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=200010,M=2*N; int h[N],e[M],ne[M],idx; int ans[N],sz[N]; void add(int a,int b) {e[idx]=b;ne[idx]=h[a];h[a]=idx++; } int n; void dfs(int u,int fa) {for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;if(fa) {ans[fa]++;ans[j]++;}sz[u]++;dfs(j,u);}for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;ans[j]+=sz[u]-1;} } int main() {IO;int T=1;//cin>>T;while(T--){memset(h,-1,sizeof h);cin>>n;for(int i=1;i<n;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1,0);for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';}return 0; }

C.序列卷積之和

一步一步推式子，預處理各種前綴和。真的無腦暴力

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=200010： const ll mod=1e9+7; ll a[N],b[N],c[N],d[N],e[N],f[N]; int n; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) b[i]=(b[i-1]+a[i])%mod;for(int i=1;i<=n;i++) c[i]=(c[i-1]+a[i]*b[i-1]%mod)%mod;for(int i=1;i<=n;i++) d[i]=(d[i-1]+b[i]*b[i]%mod)%mod;for(int i=1;i<=n;i++) e[i]=(e[i-1]+b[i])%mod;for(int i=1;i<=n;i++) f[i]=(f[i-1]+c[i])%mod;ll res=0;for(int i=1;i<=n;i++) res=(res+d[n]-d[i-1]-b[i-1]*(e[n]-e[i-1])%mod-f[n]+f[i-1]+(n-i+1)*c[i-1]%mod)%mod;cout<<(res+mod)%mod<<'\n';}return 0; }

D.寶石裝箱

學習自大佬題解

首先先說一下錯排，雖然我沒做過錯排，看到這個題首先想到如果每個箱子只對應一個不能放的寶石，那么直接可以容斥原理解決了，不過此題沒有那么簡單。看了上述文章學到錯排還可以用遞推方式解決這里記錄一下。
狀態表示：$f_i$錯排規模為$i$時的方案數
狀態計算：對于規模為$i$的錯排，考慮第$i$個小球，不妨讓第$i$個小球放在了第$j(1\le j<i)$個箱子里（第$i$禁止放在第$i$個箱子里），那么考慮第$k$個小球是否放在了第$i$個箱子，如果放在了第$i$個箱子那么很容易發現現在規模是$i?2$的錯排方案，如果沒有放在第$i$個箱子里那么現在規模是$i?1$的錯排方案，又因為$k$有$i?1$種選擇那么可以得到遞推式$f_i=(i?1)\times (f_{i?1}+f_{i?2})$
經過一頓操作計算可得$$f_n=n![\frac{1}{2!}?\frac{1}{3!}+?+(?1{)}^n\frac{1}{n!}]$$
不難看出上式和容斥原理得出的答案相同。

容斥原理后現在需要求得至少$\{1,2,3,\dots ,n\}$個盒子不合法的情況，直接上上述大佬題解結論：
狀態表示：$f_{(i,j)}$對于只考慮前$i$種盒子，$j$個盒子不合法的方案數
狀態轉移：考慮最后一步第$i$個盒子是否合法易得出$$f_{(i,j)}=f_{(i?1,j)}+f_{(i?1,j?1)}\times cn{t}_i$$$cn{t}_i$是第$i$個箱子不能放的小球數量

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<queue> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=8010; const ll mod=998244353; ll f[2][N],fact[N]; int cnt[N],n; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++){int a;cin>>a;cnt[a]++;}fact[0]=1;for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;f[0][0]=f[1][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)f[i&1][j]=(f[i-1&1][j]+f[i-1&1][j-1]*cnt[i]%mod)%mod;ll res=fact[n];for(int i=1,k=-1;i<=n;i++,k*=-1) res=(res+k*fact[n-i]*f[n&1][i])%mod;cout<<(res+mod)%mod<<'\n';}return 0; }

這個dp太妙了吧，遞推太精髓了。

E.紅色的櫻花

待補——2020/9/23補
大佬題解
擴展歐幾里得可以求出正整數$a,b$滿足$ax+by=gcd(a,b)$一組特解$\{\begin{array}{l}x=x_0\\ y=y_0\end{array}$，通解是$\{\begin{array}{l}x=x_0+\frac{kb}{gcd(a,b)}\\ y=y_0?\frac{ka}{gcd(a,b)}\end{array}$

本人在看上述題解的時候不明白如何判斷兩點是否在同一個循環中于時自己推了一下：$$\{\begin{array}{l}{s}_x+?=k_{1}n+e_x\\ s_y+?=k_{2}m+e_y\end{array}$$兩式子作差可得$$s_x?s_y?(e_x?e_y)=k_{1}n+(?k_2)m=kgcd(n,m)$$
由此推出$$s_x?s_y?(e_x?e_y)\equiv 0(gcd(n,m))$$
因此只要滿足上述式子，就能保證兩點在同一循環中。

那么如何通過操作二使得不在同一個循環的兩點處在同一循環?
$$\{\begin{array}{l}{s}_x+xd=k_{1}n+e_x\\ s_y=k_{2}m+e_y\end{array}$$兩式子作差可得$$s_x?s_y?(e_x?e_y)+xd=k_{1}n+(?k_2)m=ygcd(n,m)$$進一步化簡可得
$$xd+ygcd(n,m)=e_x?e_y?(s_x?s_y)$$由此用擴展歐幾里得求出最小正整數$x$即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; const ll INF=1e18; ll n,m,d,sx,sy,ex,ey,a,b,c; ll exgcd(ll a,ll b,ll &x,ll &y) {if(!b){x=1,y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d; } ll x,y; ll calc(ll a,ll b,ll c,ll cost) {ll gcd=exgcd(a,b,x,y);if(c%gcd) return INF;b/=gcd;if(b<0) b=-b;x=(c/gcd*x%b+b)%b;return x*cost; } int main() {IO;int T=1;cin>>T;while(T--){cin>>n>>m>>d>>sx>>sy>>ex>>ey>>a>>b>>c;ll gcd=exgcd(n,m,x,y);if(sx==ex&&sy==ey) cout<<"0\n";else {ll res=calc(d,n,ex-sx+n,b)+calc(d,m,ey-sy,c);res=min(res,INF);ll gcd=exgcd(n,m,x,y);res=min(res,calc(d,gcd,ex-ey+sy-sx,b)+a);res=min(res,calc(d,gcd,ey-ex+sx-sy,c)+a);if(res==INF) cout<<-1<<'\n';else cout<<res<<'\n';}}return 0; }

要加油哦~

總結

以上是生活随笔為你收集整理的牛客练习赛 64——错排的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。