A.牛妹的游戲

Ramsey定理：人話解釋任意六個(gè)人中要么至少三個(gè)人認(rèn)識(shí)，要么至少三個(gè)不認(rèn)識(shí)。

結(jié)論簡要證明:

假設(shè) $6$ 個(gè)據(jù)點(diǎn)分別為 $A,B,C,D,E,F$那么在 A 連向其它據(jù)點(diǎn)的控制鏈中，必然至少有 $3$條鏈被同一方控制，不妨假設(shè)它們?yōu)?$AB,AC,AD$。如此一來只要 $BC,BD,CD$ 中有任意一條鏈也被這一方控制，則可以形成控制區(qū)域；如果這三條鏈都沒有被這一方控制，也就意味著它們都被對方控制了，則它們同樣可以形成控制區(qū)域。

#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; typedef pair<int,int> pii; typedef long long ll; const int N=500010; int n,m; int e[10][10]; int main() {IO;int T=1;cin>>T;while(T--){cin>>n>>m;memset(e,0,sizeof e);if(n>5){for(int i=1;i<=m;i++){int a,b;cin>>a>>b;}cout<<"yes\n";continue;}for(int i=1;i<=m;i++){int a,b;cin>>a>>b;e[a][b]=e[b][a]=1;}bool ok=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)for(int k=j+1;k<=n;k++)if(e[i][j]&&e[j][k]&&e[k][i]||!e[i][j]&&!e[j][k]&&!e[k][i])ok=1;if(ok) cout<<"yes\n";else cout<<"no\n";}return 0; }

B.病毒擴(kuò)散

打表找規(guī)律，楊輝三角。
第四秒后擴(kuò)張現(xiàn)象如下圖

$?\begin{array}{ccccc}1\times 1& 4\times 1& 6\times 1& 4\times 1& 1\times 1\\ 4\times 1& 6\times 2& 4\times 3& 1\times 4& \\ 6\times 1& 4\times 3& 1\times 6& & \\ 4\times 1& 1\times 4& & & \\ 1\times 1& & & & \end{array}?$
好像不是那么明顯，我們把乘號左邊和右邊的數(shù)分別拿出來
$左邊:?\begin{array}{ccccc}1& 4& 6& 4& 1\\ 4& 6& 4& 1& \\ 6& 4& 1& & \\ 4& 1& & & \\ 1& & & & \end{array}?$

$右邊:?\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 2& 3& 4& \\ 1& 3& 6& & \\ 1& 4& & & \\ 1& & & & \end{array}?$
不難發(fā)現(xiàn)這兩個(gè)矩陣的這些數(shù)和組合數(shù)（楊輝三角）有關(guān)
考慮位置為$(x,y)$時(shí)間是$t$的情況下：
左邊的數(shù)$C_t^{x+y}$，右邊的數(shù)$C_{x+y}^x$那么最終答案就是$$C_t^{x+y}\times C_{x+y}^x$$
預(yù)處理階乘和逆元即可$O(1)$得到每個(gè)位置的答案
我看不懂的官方證明轉(zhuǎn)化

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef pair<int,int> pii; typedef long long ll; const int N=5010; const ll mod=998244353; ll fact[N],infact[N]; ll qmi(ll a,ll b,ll p) {ll res=1;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res; } void init() {fact[0]=infact[0]=1;for(int i=1;i<N;i++){fact[i]=fact[i-1]*i%mod;infact[i]=qmi(fact[i],mod-2,mod);} } int n; int main() {IO;int T=1;//cin>>T;init();while(T--){cin>>n;while(n--){int x,y,t;cin>>x>>y>>t;if(x+y>t) cout<<0<<'\n';else{ll res=1;res=res*fact[t]*infact[x+y]%mod*infact[t-x-y]%mod;res=res*fact[x+y]%mod*infact[x]%mod*infact[y]%mod;cout<<res<<'\n';}}}return 0; }

C.牛牛染顏色

樹形dp
狀態(tài)表示：$f_{(i,0/1)}$表示選擇/不選擇$u$ 這個(gè)節(jié)點(diǎn)后以 $u$ 為根的子樹的合法方案數(shù)。
狀態(tài)轉(zhuǎn)移：
若選擇 $u$ 這個(gè)節(jié)點(diǎn)，則子樹內(nèi)可以隨便選點(diǎn)，每個(gè)子樹獨(dú)立乘法原理可得轉(zhuǎn)移$f_{(i,1)}={\prod }_{j\in son}{f}_{(j,0)}+f_{(j,1)}$
若不選擇$u$ 這個(gè)節(jié)點(diǎn)，則最多選擇某一個(gè)子樹，由加法原理可得轉(zhuǎn)移$f_{(i,0)}=1+{\sum }_{j\in son}(f_{(j,0)}+f_{(j,1)}?1)$（? $f_{(i,0)}$包含空集的方案，所以在枚舉子樹統(tǒng)計(jì)的時(shí)候每顆子樹貢獻(xiàn)的答案要減 $1$，但最后也要把空集的情況算上，還要加個(gè)$1$）

#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; typedef long long ll; const int N=1000010,mod=1e9+7; int h[N],e[2*N],ne[2*N],idx; ll f[N][2]; int n; void add(int a,int b) {e[idx]=b;ne[idx]=h[a];h[a]=idx++; } void dfs(int u,int fa) {f[u][0]=f[u][1]=1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dfs(j,u);f[u][1]=(f[u][1]*(f[j][0]+f[j][1]))%mod;f[u][0]=(f[u][0]+f[j][1]+f[j][0]-1)%mod;} } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;memset(h,-1,sizeof h);for(int i=1;i<n;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1,-1);cout<<(f[1][0]+f[1][1])%mod<<'\n';}return 0; }

D. 牛牛的呱數(shù)

對于大數(shù)，基本上都是取模達(dá)到我們想要的目的。
由此可以把原串取模后的答案記錄下來，并且記錄它的長度（邊權(quán)），和別的串相接的過程就類似從一個(gè)狀態(tài)到另一個(gè)狀態(tài)，只需要預(yù)處理$10^k\%p$的結(jié)果跑最短路即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<queue> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef pair<int,int> pii; const int N=210; int ten[1000010]; struct node {int val,len; }a[N]; int dist[N],n,p; bool st[N]; void dijkstra() {memset(dist,0x3f,sizeof dist);priority_queue<pii,vector<pii>,greater<pii> >q;for(int i=1;i<=n;i++) {dist[a[i].val]=min(dist[a[i].val],a[i].len);q.push({a[i].len,a[i].val});}while(q.size()){int t=q.top().second;q.pop();if(st[t]) continue;st[t]=1;for(int i=1;i<=n;i++){int now=(t*ten[a[i].len]%p+a[i].val)%p;if(dist[now]>dist[t]+a[i].len){dist[now]=dist[t]+a[i].len;q.push({dist[now],now});}}} } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>p;ten[0]=1;for(int i=1;i<=1000000;i++) ten[i]=ten[i-1]*10%p;for(int i=1;i<=n;i++){string s;cin>>s;a[i].len=s.size();reverse(s.begin(),s.end());ll base=1;ll now=0;for(auto t:s){now=(now+base*(t-'0')%p)%p;base=base*10%p;}a[i].val=now%p;}dijkstra();if(dist[0]==0x3f3f3f3f) cout<<"-1\n";else cout<<dist[0]<<'\n';}return 0; }

要加油哦~~

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛 62的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。