Day 1

三题暴力搜索。。。 两题题意没看清楚。 以后一定要审清楚题。 T1水叮当的舞步0分 T2Vani和Cl2捉迷藏5分 T3粉刷匠40分 T1 ```cpp #include<iostream> #include<cstring> #include<cstdio> using namespace std; int s,n,mp[9][9],mark[9][9]; int xx[4]={1,-1,0,0},yy[4]={0,0,-1,1},used[6]; bool ans; int get() { int t=0; memset(used,0,sizeof(used)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!used[mp[i][j]]&&mark[i][j]!=1) { used[mp[i][j]]=1; t++; } return t; } void dfs(int a,int b,int x) { mark[a][b]=1; for(int i=0;i<4;i++) { int nowx=a+xx[i],nowy=b+yy[i]; if(nowx<1||nowy<1||nowx>n||nowy>n||mark[nowx][nowy]==1)continue; mark[nowx][nowy]=2; if(mp[nowx][nowy]==x)dfs(nowx,nowy,x); } } int fill(int x) { int t=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mark[i][j]==2&&mp[i][j]==x) { t++; dfs(i,j,x); } return t; } void search(int k) { int v=get(); if(!v)ans=1; if(k+v>s||ans)return; int temp[10][10]; for(int i=0;i<=5;i++) { memcpy(temp,mark,sizeof(mark)); if(fill(i))search(k+1); memcpy(mark,temp,sizeof(mark)); } } int main() { while(1) { memset(mark,0,sizeof(mark)); scanf("%d",&n);ans=0; if(n==0)break; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); dfs(1,1,mp[1][1]); for(s=0;;s++) { search(0); if(ans){printf("%d\n",s);break;} } } return 0; } ``` 100分 T2 ```cpp #include<iostream> #include<cstdio> using namespace std; long long n,m,ans,v[300],x[300][300],w[300][300]; inline int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return f*x; } inline void dfs(int f,int tot) { if(f==n+1){ if(tot>ans)ans=tot; return; } int z=1; for(int i=1;i<=n;i++) { if((x[i][f]||x[f][i])&&v[i])z=0; } if(z){ v[f]=1; dfs(f+1,tot+1); v[f]=0; } dfs(f+1,tot); } int main() { // freopen("a.in","r",stdin); n=read();m=read(); for(int i=1;i<=m;i++) { int a,b; a=read();b=read(); x[a][b]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) if(x[i][j]&&x[j][k])x[i][k]=1; dfs(1,0); printf("%d\n",ans); return 0; } ``` 60分 T3 ```cpp #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,t,a[30],l,f,ans; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return f*x; } inline void search(int x,int last) { if(x==l+1){ ans++; ans%=1000000007; return; } for(int i=1;i<=n;i++) { if(i!=last&&a[i]) { a[i]--; search(x+1,i); a[i]++; } } } int main() { t=read(); while(t--) { n=read(); for(int i=1;i<=n;i++) { a[i]=read(); l+=a[i]; } search(1,0); cout<<ans%1000000007<<endl; ans=0;l=0; memset(a,0,sizeof(a)); } } ``` 40分