ti很简单，但是把变量弄错了，写了不到半小时，调了一小时，导致t3功亏一篑。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<math.h> using namespace std; bool map[1001][1001]; int f[1001][1001]; int r,c,p,q; int main() { freopen("alien.in","r",stdin); freopen("alien.out","w",stdout); scanf("%d%d%d%d",&r,&c,&p,&q); for(int i=1,x,y;i<=p;i++) { scanf("%d%d",&x,&y); map[x][y]=true; } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) f[i][j]=f[i-1][j]+f[i][j-1]+map[i][j]-f[i-1][j-1]; for(int k=1,A,B,ans;k<=q;k++) { ans=0; scanf("%d%d",&A,&B); for(int i=0;i<=r-A;i++) for(int j=0;j<=c-B;j++) if((f[i+A][j+B]+f[i][j]-f[A+i][j]-f[i][j+B]==0)) ans++; if(A!=B) for(int i=0;i<=r-B;i++) for(int j=0;j<=c-A;j++) if((f[i+B][j+A]+f[i][j]-f[B+i][j]-f[i][A+j])==0) ans++; printf("%d ",ans); } return 0; }
t2
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<math.h> using namespace std; int n,m,w[10004]; int head[10004],next[100002],to[100002],cnt,sum[100002]; int color[10004]; int dfs(int who,int fen1,int fen2) { return 0; } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1,x,y,c;i<=m;i++) { scanf("%d%d%d",&x,&y,&c); to[++cnt]=x;next[cnt]=head[y];head[y]=cnt;sum[cnt]=c; to[++cnt]=y;next[cnt]=head[x];head[x]=cnt;sum[cnt]=c; } dfs(1,0,0); printf("3"); return 0; }
t3
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<math.h> using namespace std; int n,m; int f[5001],b[5000]; int ans1=0,ans2=0,ans3=0; int ansx,ansy; char ansz; int find(int x) { if(x!=f[x]) return f[x]=find(f[x]); else return f[x]; } void bing(int x,int y) { int f1=find(x),f2=find(y); f[f1]=f2; } int main() { freopen("fortress.in","r",stdin); freopen("fortress.out","w",stdout); scanf("%d%d",&m,&n); int c; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i*m+j]=i*m+j; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&c); if((c-8)<0) bing(i*m+j,i*m+j+m);else c-=8; if((c-4)<0) bing(i*m+j,i*m+j+1);else c-=4; if((c-2)<0) bing(i*m+j,i*m-m+j);else c-=2; if(!c) bing(i*m+j,i*m-1+j); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) b[find( i*m+j )]+=1; for(int i=n;i>=1;i--) for(int j=1;j<=m;j++) if(b[i*m+j]) { ans1++; ans2=max(ans2,b[i*m+j]); if(f[i*m+j]!=f[i*m+j+1]) { if((b[f[i*m+j]]+b[f[i*m+j+1]])>ans3) ans3=(b[f[i*m+j]]+b[f[i*m+j+1]]),ansx=i,ansy=j,ansz='E'; } if(f[i*m+j]!=f[i*m+j-m]) { if((b[f[i*m+j]]+b[f[i*m+j-m]])>ans3) ans3=(b[f[i*m+j]]+b[f[i*m+j-m]]),ansx=i,ansy=j,ansz='N'; } } printf("%d %d %d ",ans1,ans2,ans3); printf("%d %d %c",4,1,ansz);//最后找到的不是最优的，但应该是最优啊，没时间挑了。 return 0; }
z这个可以了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<math.h> using namespace std; int n,m; int f[5001],b[5000]; int ans1=0,ans2=0,ans3=0; int ansx,ansy; char ansz; int find(int x) { if(x!=f[x]) return f[x]=find(f[x]); else return f[x]; } void bing(int x,int y) { int f1=find(x),f2=find(y); f[f1]=f2; } int main() { // freopen("fortress.in","r",stdin); // freopen("fortress.out","w",stdout); scanf("%d%d",&m,&n); int c; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i*m+j]=i*m+j; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&c); if((c-8)<0) bing(i*m+j,i*m+j+m);else c-=8; if((c-4)<0) bing(i*m+j,i*m+j+1);else c-=4; if((c-2)<0) bing(i*m+j,i*m-m+j);else c-=2; if(!c) bing(i*m+j,i*m-1+j); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) b[find( i*m+j )]+=1; for(int i=n;i>=1;i--) for(int j=1;j<=m;j++) if(b[i*m+j]) { ans1++; ans2=max(ans2,b[i*m+j]); if(find(i*m+j)!=find(i*m+j+1)) { if((b[f[i*m+j]]+b[f[i*m+j+1]])>ans3) ans3=(b[f[i*m+j]]+b[f[i*m+j+1]]); } if(find(i*m+j)!=find(i*m+j-m)) { if((b[f[i*m+j]]+b[f[i*m+j-m]])>ans3) ans3=(b[f[i*m+j]]+b[f[i*m+j-m]]); } } printf("%d %d %d ",ans1,ans2,ans3); for(int i=n;i>=1;i--) for(int j=1;j<=m;j++) { if(b[f[i*m+j]]+b[f[i*m+j+1]]==ans3) { printf("%d %d E",i,j); return 0; } if((b[f[i*m+j]]+b[f[i*m+j-m]])==ans3) { printf("%d %d N",i,j); return 0; } } return 0; }