首页 > 代码库 > ZOJ Monthly, August 2014

ZOJ Monthly, August 2014

H Machine http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5337

树的深搜。邻接表快一些

 1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 #define mt(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 const int M=10010; 8 struct G{ 9     struct E{10         int v,next;11     }e[M<<1];12     int le,head[M];13     void init(){14         le=0;15         mt(head,-1);16     }17     void add(int u,int v){18         e[le].v=v;19         e[le].next=head[u];20         head[u]=le++;21     }22 }g;23 vector<int> son[M];24 int dfs(int u,int fa){25     son[u].clear();26     for(int i=g.head[u];~i;i=g.e[i].next){27         int v=g.e[i].v;28         if(v!=fa){29             son[u].push_back(dfs(v,u));30         }31     }32     sort(son[u].begin(),son[u].end());33     int res=1,ls=son[u].size();34     for(int i=0;i<ls;i++){35         res=max(res,son[u][i]+ls-i-1);36     }37     return res;38 }39 int main(){40     int n;41     while(~scanf("%d",&n)){42         g.init();43         for(int v=2,u;v<=n;v++){44             scanf("%d",&u);45             g.add(u,v);46             g.add(v,u);47         }48         printf("%d\n",dfs(1,-1));49     }50     return 0;51 }
View Code

 vector慢一些

 1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 const int M=10010; 6 vector<int> g[M],son[M]; 7 int dfs(int u,int fa){ 8     son[u].clear(); 9     int lu=g[u].size();10     for(int i=0;i<lu;i++){11         int v=g[u][i];12         if(v!=fa){13             son[u].push_back(dfs(v,u));14         }15     }16     sort(son[u].begin(),son[u].end());17     int res=1,ls=son[u].size();18     for(int i=0;i<ls;i++){19         res=max(res,son[u][i]+ls-i-1);20     }21     return res;22 }23 int main(){24     int n;25     while(~scanf("%d",&n)){26         for(int i=1;i<=n;i++){27             g[i].clear();28         }29         for(int v=2,u;v<=n;v++){30             scanf("%d",&u);31             g[u].push_back(v);32             g[v].push_back(u);33         }34         printf("%d\n",dfs(1,-1));35     }36     return 0;37 }
View Code

 G YY‘s Minions http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5336

模拟题,怎么说怎么做。

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int M=64; 5 char op[M]; 6 int mat[2][M][M],n,m,f,k,t; 7 struct G{ 8     int t,x,y; 9     friend bool operator <(G a,G b){10         return a.t<b.t;11     }12 }g[M*M];13 int dx[]={-1,-1,-1,0,0,1,1,1};14 int dy[]={-1,0,1,-1,1,-1,0,1};15 int sum(int x,int y,int pre){16     int res=0;17     for(int i=0,tx,ty;i<8;i++){18         tx=x+dx[i];19         ty=y+dy[i];20         if(tx>=1&&tx<=n&&ty>=1&&ty<=m){21             if(mat[pre][tx][ty]&1){22                 res++;23             }24         }25     }26     return res;27 }28 int change(int pre,int num){29     if(pre==0){30         if(num==3) return 1;31         return 0;32     }33     if(num==2||num==3) return 1;34     return 0;35 }36 char tochar(int x){37     if(x==2) return X;38     return x+0;39 }40 int main(){41     while(~scanf("%d",&t)){42         while(t--){43             scanf("%d%d%d%d",&n,&m,&f,&k);44             int pre=0,now=1;45             for(int i=1;i<=n;i++){46                 scanf("%s",op);47                 for(int j=0;j<m;j++){48                     mat[pre][i][j+1]=op[j]-0;49                 }50             }51             for(int i=0;i<k;i++){52                 scanf("%d%d%d",&g[i].t,&g[i].x,&g[i].y);53             }54             sort(g,g+k);55             for(int u=1,head=0;u<=f;u++,pre^=1,now^=1){56                 for(int i=1;i<=n;i++){57                     for(int j=1;j<=m;j++){58                         if(mat[pre][i][j]==2){59                             mat[now][i][j]=2;60                             continue;61                         }62                         int num=sum(i,j,pre);63                         mat[now][i][j]=change(mat[pre][i][j],num);64                     }65                 }66                 while(head<k&&g[head].t==u){67                     mat[now][g[head].x][g[head].y]=2;68                     head++;69                 }70             }71             for(int i=1;i<=n;i++){72                 for(int j=1;j<=m;j++){73                     putchar(tochar(mat[pre][i][j]));74                 }75                 putchar(\n);76             }77         }78     }79     return 0;80 }
View Code

 

 

end

ZOJ Monthly, August 2014