AtCoder Grand Contest 017

A - Biscuits

有\(n\)個數，問有多少個集合的數的和模\(2\)余\(P\)。

隨便\(dp\)一下就好了。

#include<iostream> #include<cstdio> using namespace std; #define ll long long inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; } int n,P;ll f[55][2]; int main() {n=read();P=read();f[0][0]=1;for(int i=1;i<=n;++i){int x=read()&1;f[i][0]=f[i-1][0];f[i][1]=f[i-1][1];f[i][0^x]+=f[i-1][0];f[i][1^x]+=f[i-1][1];}printf("%lld\n",f[n][P]);return 0; }

B - Moderate Differences

有\(n\)個數排成一行，第一個數是\(A\)，最后一個數是\(B\)，已知相鄰的兩個數的差的絕對值都在\([C,D]\)之間，問是否存在一個合法的情況。

顯然每個數要么貢獻為正要么貢獻為負，那么枚舉有多少個貢獻為正，這樣子就能夠算出一個合法區間，判斷\(B-A\)是否在這個區間內就行了。

#include<iostream> #include<cstdio> using namespace std; #define ll long long inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; } int n,A,B,C,D; ll L,R; void chk(){if(L<=B&&B<=R)puts("YES"),exit(0);} int main() {n=read();A=read();B=read()-A;C=read();D=read();for(int i=0;i<n;++i){L=1ll*C*i-1ll*(n-1-i)*D;R=1ll*D*i-1ll*(n-1-i)*C;chk();}puts("NO");return 0; }

C - Snuke and Spells

你有\(n\)個球，假設當前剩下的球的個數是\(k\)個，那么就把所有球上寫的數字為\(k\)的球給丟掉。

現在你可以改變一些球上的數字，問最少改變多少次可以讓所有球都被刪掉。

有若干次修改，你要對于每次修改之后都求出答案。

我怎么覺得這題做過啊。。。。

大概就是把數字個數用類似柱狀圖給表示出來，然后把柱子給向左推倒，那么\([1,n]\)中未被覆蓋的位置的個數的就是答案。

那么拿線段樹模擬一下就行了嗷。

#include<iostream> #include<cstdio> using namespace std; #define MAX 200200 inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; } int n,Q; int a[MAX],b[MAX],c[MAX]; #define lson (now<<1) #define rson (now<<1|1) int t[MAX<<2],mn[MAX<<2]; void pushup(int now){mn[now]=mn[lson]+mn[rson];} void Build(int now,int l,int r) {if(l==r){t[now]=c[l];mn[now]=c[l]==0;return;}int mid=(l+r)>>1;Build(lson,l,mid);Build(rson,mid+1,r);pushup(now); } void Modify(int now,int l,int r,int p,int w) {if(l==r){t[now]+=w;mn[now]=t[now]==0;return;}int mid=(l+r)>>1;if(p<=mid)Modify(lson,l,mid,p,w);else Modify(rson,mid+1,r,p,w);pushup(now); } int main() {n=read();Q=read();for(int i=1;i<=n;++i)b[a[i]=read()]++;for(int i=1;i<=n;++i)if(b[i])c[max(1,i-b[i]+1)]+=1,c[i+1]-=1;for(int i=1;i<=n;++i)c[i]+=c[i-1];Build(1,1,n);while(Q--){int x=read(),v=read();b[a[x]]--;if(a[x]-b[a[x]]>0)Modify(1,1,n,a[x]-b[a[x]],-1);a[x]=v;if(a[x]-b[a[x]]>0)Modify(1,1,n,a[x]-b[a[x]],1);b[a[x]]++;printf("%d\n",mn[1]);}return 0; }

D - Game on Tree

兩個人在一棵\(n\)個節點的樹上玩游戲，每次可以選擇一條邊，把這條邊刪掉，然后把不包含\(1\)的那個連通塊給刪掉，不能操作者輸。

問誰會贏。

emmmm，這是個博弈題，所以如果不是神仙結論的話就往\(SG\)函數上靠。

顯然根節點的每個兒子都可以拆下來變成一個子游戲，所以根節點的\(sg\)值就是所有兒子\(sg\)值的異或和。

因為所有兒子拆下來變成子游戲之后，還需要花\(1\)步把這個兒子刪掉，所以每個點的\(sg\)值是所有兒子\(sg\)值\(+1\)的異或和。

#include<iostream> #include<cstdio> using namespace std; #define MAX 100100 inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; } struct Line{int v,next;}e[MAX<<1]; int h[MAX],cnt=1; inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;} int n,sg[MAX],vis[MAX]; void dfs(int u,int ff) {for(int i=h[u];i;i=e[i].next)if(e[i].v!=ff)dfs(e[i].v,u),sg[u]^=sg[e[i].v]+1; } int main() {n=read();for(int i=1;i<n;++i){int u=read(),v=read();Add(u,v);Add(v,u);}dfs(1,0);puts(sg[1]?"Alice":"Bob");return 0; }

E - Jigsaw

有若干個高度為\(H\)的積木，每個都長成這樣：

且\(A_i,B_i,C_i,D_i\)都會告訴你，并且左中右三個部分的寬度也相等。

現在給你\(n\)個積木，你要讓中間那部分的下面挨著地面，然后拼出來的東西要滿足不存在地面上面的存在一段空，且這段空的上方還有積木。寫成坐標的形式就是不存在\((x,y1)\)未被積木覆蓋，但是\((x,y_2),y_1<y_2\)被積木覆蓋了。

顯然是考慮把一個積木左邊給卡進另一個積木的右側里，那么我們把能夠卡的積木之間連邊，把接地的和起點終點連邊，于是就是問所有積木是否能分成若干條路徑。然而這樣子復雜度很假，因為邊數可以達到\(O(n^2)\)級別。

考慮把積木看成邊，于是我們可以把左側\(C_i=0\)看成點\(-A_i\)，\(C_i\neq 0\)看成點\(C_i\)，右側\(D_i=0\)看成點\(B_i\)，\(D_i\neq 0\)看成\(-D_i\)。這樣轉化完之后一個積木就是一條邊，于是問題變成了我們有\([-H,H]\)這些點，之間有一些邊，我們要把每一條邊都劃分進一個路徑中，使得路徑以負數為起點，以正數為終點。

那么我們統計入度和出度，顯然負數的入度不能多于出度，正數出度不能多于入度。同時這個東西不能成環，所以一個連通塊中至少存在一個點入度不等于出度。

#include<iostream> #include<cstdio> using namespace std; #define MAX 450 inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; } int n,H,f[MAX],In[MAX],Ot[MAX];bool vis[MAX]; int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);} int main() {n=read();H=read();for(int i=1;i<=H+H;++i)f[i]=i,vis[i]=false;for(int i=1;i<=n;++i){int a=read(),b=read(),c=read(),d=read();int l=(c>0?c:-a)+H,r=(d>0?-d:b)+H;if(getf(l)!=getf(r))f[getf(l)]=getf(r);In[r]+=1;Ot[l]+=1;}for(int i=-H;i<0;++i)if(In[i+H]>Ot[i+H]){puts("NO");return 0;}for(int i=1;i<=H;++i)if(In[i+H]<Ot[i+H]){puts("NO");return 0;}for(int i=0;i<=H+H;++i)if(In[i]!=Ot[i])vis[getf(i)]=true;for(int i=0;i<=H+H;++i)if(In[i]&&Ot[i]&&!vis[getf(i)]){puts("NO");return 0;}puts("YES");return 0; }

F - Zigzag

有\(n*(n+1)/2\)個點，第\(i\)行有\(i\)個點，用\((i,j),j\le i\)表示這些點。

從\((i,j)\)只能走到\((i+1,j+1)\)或者\((i+1,j)\)。

現在你要找到\(m\)條從\((1,1)\)走到第\(n\)行的路徑，假設第\(a\)條路徑走過的第\(k\)個點是\((k,X[a,k])\)，那么對于任意的\(a\le b\)，不能存在\(i\)使得\(X[a,i]>X[b,i]\)。

同時還有\(k\)個限制，每個限制形如\((a,b,c)\)表示第\(a\)條路徑的第\(b\)個點到第\(b+1\)個點必須朝著\(c\)方向走。

問方案數。

首先一條路徑可以用一個二進制數來表示，那么一個暴力做法就是枚舉上一個二進制數再枚舉這一個，復雜度大概可以做到\(O(2^{2n})\)。

考慮優化這個過程。注意到我們的合法情況是前一個的前綴和在任意時刻都不大于后一個的前綴和。

假設現在正在確定第\(i\)條路徑，且前\(j-1\)位已經確定完畢并且和\(i-1\)的前\(j-1\)位相同，現在正在確定第\(j\)位。

如果這一位相同，過，沒啥事。否則不同，根據前面的要求，只能是\(i-1\)的這一位是\(0\)，\(i\)的這一位是\(1\)。

那么我們找到\(i-1\)的下一個\(1\)的位置，把這個\(1\)推上來，推到\(j\)位置，強行和\(i\)的前\(j\)位相同，不難發現這樣子處理完畢之后對于\(i\)而言，到下一個\(i-1\)存在\(1\)的位置之前，是沒有任何影響的，因為這一位多了一個\(1\)，而后面都是\(0\)，所以怎么填都是合法的。于是我們就把這個狀態的前\(j-1\)位轉移到了\(j\)位了。

如果下一個\(1\)不存在，那么接下來\(i\)就可以任意走了。

那么就這樣子直接\(dp\)就好了。

設\(f[i][j][S]\)表示當前考慮到第\(i\)位，前\(j\)位和\(i-1\)的狀態相同，\(i-1\)的\(01\)狀態是\(S\)的方案數。

轉移的時候枚舉這一位填什么，如果填\(0\)而\(S\)這一位是\(1\)則不合法。如果兩個相等則直接轉移；否則按照前面說的減掉下一個\(1\)再轉移。

#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MOD 1000000007 void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;} inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; } int n,m,K,ans,Lim[22][22]; int f[2][22][1<<20],nxt[1<<20][22]; int main() {n=read()-1;m=read();K=read();memset(Lim,-1,sizeof(Lim));for(int i=1;i<=K;++i){int a=read(),b=read();Lim[a][b-1]=read();}int S=1<<n;for(int i=0;i<S;++i){int v=-1;for(int j=n-1;~j;--j){if(i&(1<<j))v=j;nxt[i][j]=v;}}f[0][n][0]=1;for(int i=1,nw=1,pw=0;i<=m;++i,nw^=1,pw^=1){for(int j=0;j<S;++j)f[nw][0][j]=f[pw][n][j];memset(f[pw],0,sizeof(f[pw]));for(int j=0;j<n;++j)for(int k=0;k<S;++k)if(f[nw][j][k])for(int l=0;l<=1;++l){if((~Lim[i][j])&&l!=Lim[i][j])continue;int t=(k>>j)&1;if(l==0&&t==1)continue;if(l==t)add(f[nw][j+1][k],f[nw][j][k]);else{int p=nxt[k][j];if(p==-1)add(f[nw][j+1][k+(1<<j)],f[nw][j][k]);else add(f[nw][j+1][k+(1<<j)-(1<<p)],f[nw][j][k]);}}}for(int i=0;i<S;++i)add(ans,f[m&1][n][i]);printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/cjyyb/p/11087851.html

總結

以上是生活随笔為你收集整理的AtCoder Grand Contest 017的全部內容，希望文章能夠幫你解決所遇到的問題。

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