Stack
#include<iostream> #include<cstdio> #define mod 7 using namespace std; int f[1010][1010],n; int main(){ freopen("stack.in","r",stdin);freopen("stack.out","w",stdout); scanf("%d",&n); for(int i=0;i<=n;i++) for(int j=0;j<=i;j++){ if(j)f[i][j]=f[i-1][j]+f[i][j-1]; else f[i][j]=1; while(f[i][j]>=mod)f[i][j]-=mod; } printf("%d",f[n][n]); return 0; }
Cube
/* 记录每个点下面有多少元素top[i]，他所在并查集的大小，每次移动操作就把移动后在上面的那部分中所有的点的top加上它移动到的病茶几的大小，修改复杂度很高，查询是O(1)的 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 30010 using namespace std; int p,fa[maxn],sz[maxn],top[maxn]; char ch[5]; int find(int x){ if(fa[x]==x)return fa[x]; return fa[x]=find(fa[x]); } int main(){ //freopen("Cola.txt","r",stdin); freopen("cube.in","r",stdin);freopen("cube.out","w",stdout); scanf("%d",&p); int n=0; for(int i=1;i<=30000;i++)fa[i]=i,sz[i]=1; while(p--){ scanf("%s",ch); int x,y; if(ch[0]=='M'){ scanf("%d%d",&x,&y); n=max(n,max(x,y)); int f1=find(x),f2=find(y); if(f1!=f2){ for(int i=1;i<=n;i++){ if(find(i)==f1){ top[i]+=sz[f2]; } } fa[f1]=f2; sz[f2]+=sz[f1]; sz[f1]=0; } } else{ scanf("%d",&x); n=max(n,x); printf("%d\n",top[x]); } } }
#include<iostream> #include<cstdio> #define maxn 30010 using namespace std; int p,cnt[maxn],sum[maxn],fa[maxn]; char s[4]; int find(int x){ if(x==fa[x])return fa[x]; int f=fa[x]; fa[x]=find(fa[x]); cnt[x]+=cnt[f]; return fa[x]; } void merge(int x,int y){ fa[y]=x; cnt[y]+=sum[x]; sum[x]+=sum[y]; sum[y]=0; } int main(){ freopen("cube.in","r",stdin);freopen("cube.out","w",stdout); for(int i=1;i<=30000;i++)fa[i]=i,sum[i]=1; scanf("%d",&p); while(p--){ scanf("%s",s); int x,y; if(s[0]=='M'){ scanf("%d%d",&x,&y); merge(find(x),find(y)); } else { scanf("%d",&x); printf("%d\n",sum[find(x)]-cnt[x]-1); } } }
Zuma
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> using namespace std; map<string,bool>vis; string s,snow; struct node{ string s; int step; }cur,nxt; queue<node>q; void down(){ string pre=snow; snow=""; for(int i=0;i<pre.length();){ while(pre[i]=='2'&&i<pre.length())i++; snow=snow+pre[i];i++; } } void updata(){ string pre=snow; bool flag=0; for(int i=0;i<pre.length();i++){ if(pre[i]==pre[i-1]&&pre[i]==pre[i+1])flag=1,snow[i]=snow[i-1]=snow[i+1]='2'; } if(flag){ down(); updata(); } } int main(){ //freopen("Cola.txt","r",stdin); freopen("zuma.in","r",stdin);freopen("zuma.out","w",stdout); cin>>s; vis[s]=1; cur.s=s;cur.step=0; //cout<<s<<endl; bool flag=0; int n1=0,n0=0; for(int i=1;i<s.length();i++){ if(s[i]==s[i-1]){ flag=1;break; } if(s[i]=='0')n0++; if(s[i]=='1')n1++; } if(flag==0){ int ans=0; if(s[0]=='0')n0++; if(s[0]=='1')n1++; if(n1%2==0&&n0%2==0&&n1==n0){ ans=2+(n1/2)+((n0-2)/2)+2; printf("%d",ans); return 0; } if(n1%2==1&&n0%2==1&&n1==n0){ ans=4+((n1-1)/2)+((n0-1)/2); printf("%d",ans); return 0; } if(n1<n0)swap(n1,n0); if(n1%2==1&&n0==n1-1){ ans=2+((n1-1)/2)+(n0/2); printf("%d",ans); return 0; } if(n1%2==0&&n0==n1-1){ ans=2+(n1/2)+((n0-1)/2); printf("%d",ans); return 0; } } q.push(cur); while(!q.empty()){ cur=q.front();q.pop(); int len=cur.s.length(); //cout<<cur.s<<endl; if(len==0){printf("%d",cur.step);return 0;} for(int i=0;i<=len;i++){//在第i个前面插 snow=""; snow=snow+cur.s.substr(0,max(0,i)); snow=snow+"0"; snow=snow+cur.s.substr(i,len-i); string now=snow; updata(); if(!vis[snow]){ vis[snow]=1; nxt.s=snow;nxt.step=cur.step+1; q.push(nxt); if(nxt.s.length()==1&&nxt.s[0]!='0'&&nxt.s[0]!='1'){printf("%d",nxt.step);return 0;} } //cout<<snow<<endl; snow=now; snow[i]='1'; updata(); if(!vis[snow]){ vis[snow]=1; nxt.s=snow;nxt.step=cur.step+1; q.push(nxt); if(nxt.s.length()==1&&nxt.s[0]!='0'&&nxt.s[0]!='1'){printf("%d",nxt.step);return 0;} } //cout<<snow<<endl; } } fclose(stdin);fclose(stdout); return 0; }
/* 区间dp，情况有些多需要讨论 首先连续相同的颜色为了方便要合并，记录每个块的颜色，就可以dp了 dp[l][r]表示合并这段区间的最小步数，分几种情况 这段区间是奇数(为了避免区间长度为2的情况) 1. color[l]==color[r] && tot[l]+tot[r]==2 --> dp[l][r] 可从 dp[l+1][r-1]+1 转移过来。 2. color[l]==color[r] && tot[l]+tot[r]>2 --> dp[l][r] 可从 dp[l+1][r-1] 转移过来。 3. color[l]==color[k]==color[r](k∈(l,r) && [l,k],[k,r] 为奇数) -->可从dp[l+1][k-1]+dp[k+1][r-1]转移过来。 这段区间是偶数 普通的转移 dp[l][r] =min(dp[l][r] , dp[l][k]+dp[k+1][r]); */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 257 using namespace std; int dp[maxn][maxn],col[maxn],a[maxn]; char s[maxn]; int n,m,ans; int main(){ freopen("zuma.in","r",stdin);freopen("zuma.out","w",stdout); scanf("%s",s);n=strlen(s); a[1]=1;m=1; for(int i=1;i<n;i++){ if(s[i]==s[i-1]){ col[m]=s[i]-'0'; a[m]++; } else { a[++m]=1; col[m]=s[i]-'0'; } } for(int len=0;len<=m;len++){ for(int i=1;i<=m;i++){ int j=i+len; if(j>=1&&j<=m){ dp[i][j]=2*n; if(len==0)dp[i][j]=3-a[i]; else { for(int k=i;k<j;k++) dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]); if((j-i)%2==0){ if(a[i]+a[j]==2){ if(col[i]==col[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]+1); } else if(col[i]==col[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]); if(a[i]+a[j]<4) for(int k=i+2;k<j;k+=2) if(a[k]==1)dp[i][j]=min(dp[i+1][k-1]+dp[k+1][j-1],dp[i][j]); } } } } } printf("%d\n",dp[1][m]); return 0; }