T1:
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cctype> #include<cstdlib> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } int A[50][50]; int x[3000],y[3000]; void set(int k,int r,int c) { A[r][c]=k;x[k]=r;y[k]=c; } int main() { int n=read(); set(1,1,n/2+1); rep(k,2,n*n) { if(x[k-1]==1&&y[k-1]!=n) set(k,n,y[k-1]+1); else if(y[k-1]==n&&x[k-1]!=1) set(k,x[k-1]-1,1); else if(x[k-1]==1&&y[k-1]==n) set(k,x[k-1]+1,y[k-1]); else if(!A[x[k-1]-1][y[k-1]+1]) set(k,x[k-1]-1,y[k-1]+1); else set(k,x[k-1]+1,y[k-1]); } rep(i,1,n) { printf("%d",A[i][1]); rep(j,2,n) printf(" %d",A[i][j]); putchar(' '); } return 0; }
T2:
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cctype> #include<cstdlib> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=200010; int n,ans,to[maxn],vis[maxn],dep[maxn]; void dfs(int x) { vis[x]=-1; if(vis[to[x]]<0) ans=min(ans,dep[x]-dep[to[x]]+1); else if(!vis[to[x]]) dep[to[x]]=dep[x]+1,dfs(to[x]); vis[x]=1; } int main() { n=read();ans=n+1; rep(i,1,n) to[i]=read(); rep(i,1,n) if(!vis[i]) dfs(i); printf("%d ",ans); return 0; }
T3:
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cctype> #include<cstdlib> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } int n,A[24],t[18],s[18],f[1<<24],vis[1<<24]; int nowans,cur_clock; int dp(int S,int c,int dep) { if(dep>=nowans) return 1<<20; if(!c) return 0; int& ans=f[S]; if(vis[S]==cur_clock) return ans; ans=c;vis[S]=cur_clock; if(t[14]>=1&&t[15]>=1) { int S2=S^(1<<s[14])^(1<<s[15]); s[14]++;t[14]--;s[15]++;t[15]--; ans=min(ans,dp(S2,c-2,dep+1)+1); s[14]--;t[14]++;s[15]--;t[15]++; } rep(i,1,8) if(t[i]) { int S2=S,j=i; for(;j<=12;j++) if(t[j]<1) break; j--;if(j-i+1>=5) { rep(k,i,j) S2^=1<<s[k],s[k]++,t[k]--; ans=min(ans,dp(S2,c-(j-i+1),dep+1)+1); rep(k,i,j) s[k]--,t[k]++; } } rep(i,1,10) if(t[i]>=2) { int S2=S,j=i; for(;j<=12;j++) if(t[j]<2) break; j--;if(j-i+1>=3) { rep(k,i,j) S2=S2^(1<<s[k])^(1<<s[k]+1),s[k]+=2,t[k]-=2; ans=min(ans,dp(S2,c-(j-i+1)*2,dep+1)+1); rep(k,i,j) s[k]-=2,t[k]+=2; } } rep(i,1,11) if(t[i]>=3) { int S2=S,j=i; for(;j<=12;j++) if(t[j]<3) break; j--;if(j-i+1>=2) { rep(k,i,j) S2=S2^(1<<s[k])^(1<<s[k]+1)^(1<<s[k]+2),s[k]+=3,t[k]-=3; ans=min(ans,dp(S2,c-(j-i+1)*3,dep+1)+1); rep(k,i,j) s[k]-=3,t[k]+=3; } } rep(i,1,15) if(t[i]>=2) { int S2=(S^(1<<s[i])^(1<<s[i]+1)); s[i]+=2;t[i]-=2;ans=min(ans,dp(S2,c-2,dep+1)+1);t[i]+=2;s[i]-=2; if(t[i]>=3) { int S2=(S^(1<<s[i])^(1<<s[i]+1)^(1<<s[i]+2)); s[i]+=3;t[i]-=3;ans=min(ans,dp(S2,c-3,dep+1)+1);t[i]+=3;s[i]-=3; if(t[i]>=4) { S2=(S^(1<<s[i])^(1<<s[i]+1)^(1<<s[i]+2)^(1<<s[i]+3)); s[i]+=4;t[i]-=4;ans=min(ans,dp(S2,c-4,dep+1)+1);t[i]+=4;s[i]-=4; rep(j,1,15) rep(k,1,15) { int nt=t[i]; if(j==i||k==i) t[i]-=4; if(((t[j]>=1&&t[k]>=1)&&j!=k)||(j==k&&t[j]>=2)) { if(j==i||k==i) t[i]+=4; S2=S^(1<<s[i])^(1<<s[i]+1)^(1<<s[i]+2)^(1<<s[i]+3); s[i]+=4;t[i]-=4; S2=S2^(1<<s[j]); s[j]+=1;t[j]-=1; S2=S2^(1<<s[k]); s[k]+=1;t[k]-=1; ans=min(ans,dp(S2,c-6,dep+1)+1); t[i]+=4;s[i]-=4;s[j]-=1;t[j]+=1;s[k]-=1;t[k]+=1; } t[i]=nt; if(j==i||k==i) t[i]-=4; if(((t[j]>=2&&t[k]>=2)&&j!=k)||(j==k&&t[j]>=4)) { if(j==i||k==i) t[i]+=4; S2=S^(1<<s[i])^(1<<s[i]+1)^(1<<s[i]+2)^(1<<s[i]+3); s[i]+=4;t[i]-=4; S2=S2^(1<<s[j])^(1<<s[j]+1); s[j]+=2;t[j]-=2; S2=S2^(1<<s[k])^(1<<s[k]+1); s[k]+=2;t[k]-=2; ans=min(ans,dp(S2,c-8,dep+1)+1); t[i]+=4;s[i]-=4;s[j]-=2;t[j]+=2;s[k]-=2;t[k]+=2; } t[i]=nt; } } rep(j,1,15) { if((t[j]>=1&&j!=i)||(j==i&&t[j]>=4)) { S2=S^(1<<s[i])^(1<<s[i]+1)^(1<<s[i]+2); s[i]+=3;t[i]-=3; S2=S2^(1<<s[j]);s[j]++;t[j]--; ans=min(ans,dp(S2,c-4,dep+1)+1); t[i]+=3;s[i]-=3;s[j]--;t[j]++; } if((t[j]>=2&&j!=i)||(j==i&&t[j]>=5)) { S2=S^(1<<s[i])^(1<<s[i]+1)^(1<<s[i]+2); s[i]+=3;t[i]-=3; S2=S2^(1<<s[j])^(1<<s[j]+1);s[j]+=2;t[j]-=2; ans=min(ans,dp(S2,c-5,dep+1)+1); t[i]+=3;s[i]-=3;s[j]-=2;t[j]+=2; } } } } nowans=min(nowans,dep+ans);return ans; } int main() { int T=read(),N=read(); while(T--) { memset(t,0,sizeof(t)); n=N;nowans=n+1;cur_clock++; rep(i,0,n-1) { A[i]=read();int temp=read(); if(!A[i]) A[i]=13+temp; else if(A[i]==2) A[i]=13; else if(A[i]==1) A[i]=12; else A[i]-=2; t[A[i]]++; } s[1]=0; rep(i,2,15) s[i]=s[i-1]+t[i-1]; dp((1<<n)-1,n,0); printf("%d ",min(dp((1<<n)-1,n,0),nowans)); } return 0; }
T4:
#include<cstdio> #include<cctype> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=50010; int L,n,m,A[maxn],is[maxn]; int check(int x) { int c=0,last=0; rep(i,1,n) { if(A[i]-A[last]<x) is[i]=0; else is[i]=1,last=i; } rep(i,1,n) if(L-A[i]<x) is[i]=0; rep(i,1,n) if(!is[i]) c++; return c<=m; } int main() { L=read();n=read();m=read(); int l=0,r=L+1,mid; rep(i,1,n) A[i]=read(); while(l+1<r) if(check(mid=l+r>>1)) l=mid; else r=mid; printf("%d ",l); return 0; }
T5：
#include<cstdio> #include<cctype> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef unsigned int ll; const int maxn=1010; const int maxm=210; const int mod=1000000007; char A[maxn],B[maxm]; int n,m,k,mx[maxn][maxm]; ll f[2][maxn][maxm],g[2][maxn][maxm]; int match(int x,int y) { int ans=0; while(x>ans&&y>ans&&A[x-ans]==B[y-ans]) ans++; return ans; } void update(ll& ans,ll v) { ans=v;if(ans>mod) ans-=mod; } int main() { n=read();m=read();k=read(); scanf("%s%s",A+1,B+1); rep(i,1,n) rep(j,1,m) mx[i][j]=match(i,j); int cur=0; rep(i,0,n) rep(j,0,n-i) g[0][i+j][j]=1; rep(t,1,k) { cur^=1; memset(g[cur],0,sizeof(g[cur])); rep(gap,0,n) rep(i,gap+t,min(n,m+gap)) { int j=i-gap; if(j-mx[i][j]-1<0) f[cur][i][j]=g[cur^1][i-1][j-1]; else { int temp=j-mx[i][j]-1;if(temp<t-2) temp=t-2; update(f[cur][i][j],g[cur^1][i-1][j-1]-g[cur^1][temp+gap][temp]+mod); } update(f[cur][i][j],f[cur][i][j]+f[cur][i-1][j]); if(j>t) update(g[cur][i][j],f[cur][i][j]+g[cur][i-1][j-1]); else g[cur][i][j]=f[cur][i][j]; } } printf("%u ",f[cur][n][m]); return 0; }