首页 > 代码库 > 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 }
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 }
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 }
end
ZOJ Monthly, August 2014
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。