ZOJ Monthly, August 2014

A Abs Problem http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5330

找规律题，构造出解。copyright@ts

 1 #include<cstdio>
 2 int main() {
 3     int n,big,sma,id;
 4     while(~scanf("%d",&n)) {
 5         if(n==1) {
 6             puts("1 1");
 7             puts("1");
 8             puts("1");
 9             continue;
10         }
11         if(n==2) {
12             puts("1 1");
13             puts("1 2");
14             puts("2 1");
15             continue;
16         }
17         if(!((n-3)%4)||!(n%4)) {
18             sma=0;
19         }
20         else {
21             sma=1;
22         }
23         if(sma) {
24             if(n&1) {
25                 big=n;
26                 id=3;
27             }
28             else {
29                 big=n-1;
30                 id=4;
31             }
32         }
33         else {
34             if(n&1) {
35                 big=n-1;
36                 id=1;
37             }
38             else {
39                 big=n;
40                 id=2;
41             }
42         }
43         printf("%d %d
",sma,big);
44         printf("%d",n);
45         for(int i=n-1;i>=1;i--) {
46             printf(" %d",i);
47         }
48         puts("");
49         if(id==1||id==4) {
50             for(int i=n-3;i>=1;i--) {
51                 printf("%d ",i);
52             }
53             printf("%d %d %d
",n-2,n-1,n);
54         }
55         else {
56             for(int i=n-1; i>=1; i--) {
57                 printf("%d ",i);
58             }
59             printf("%d
",n);
60         }
61     }
62     return 0;
63 }

View Code

E Easy 2048 Again http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5334

状态压缩dp，只需要存递减的状态。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 const int M=512;
 7 const int all=1<<12;
 8 int a[M],dp[2][all];
 9 int main(){
10     int t,n;
11     int to[32];///将输入变成2的x次方
12     int p2[32];///存2的i次方
13     p2[0]=1;
14     for(int i=1;i<=13;i++){
15         p2[i]=p2[i-1]*2;
16     }
17     to[2]=1;
18     to[4]=2;
19     to[8]=3;
20     to[16]=4;
21     while(~scanf("%d",&t)){
22         while(t--){
23             scanf("%d",&n);
24             for(int i=1;i<=n;i++){
25                 scanf("%d",&a[i]);
26                 a[i]=to[a[i]];
27             }
28             mt(dp,-1);
29             int pre=0,now=1;
30             dp[pre][0]=0;
31             for(int i=1;i<=n;i++,now^=1,pre^=1){
32                 for(int j=0;j<all;j++){
33                     if(~dp[pre][j]){
34                         dp[now][j]=max(dp[now][j],dp[pre][j]);///不选
35                         ///下面是选
36                         int t=j;///下一个状态
37                         int k=a[i]-1;
38                         ///dp中第二维0001表示有个2,0011表示有4,2,0111表示8,4,2
39                         int q=(1<<k)-1;///q为( 比k低一位的位数全是1 )的数
40                         int sum=p2[a[i]];///新得分
41                         if(!(t&q)){///如果比k低的位全是0，才能合并
42                             while((t&(1<<k))){
43                                 sum+=p2[k+2];
44                                 k++;
45                             }
46                             q=(1<<k)-1;
47                             t&=~q;///把比k低的位数全变成0
48                             t|=1<<k;
49                         }
50                         else{
51                             t=1<<k;///不能合并，产生新递减序列，只有k位是1
52                         }
53                         dp[now][t]=max(dp[now][t],dp[pre][j]+sum);
54                     }
55                 }
56             }
57             int ans=0;
58             for(int i=0;i<all;i++){
59                 ans=max(ans,dp[pre][i]);
60             }
61             printf("%d
",ans);
62         }
63     }
64     return 0;
65 }

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('
');
76             }
77         }
78     }
79     return 0;
80 }

View Code

用vector就不用排序了。

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

View Code

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
",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
",dfs(1,-1));
35     }
36     return 0;
37 }

View Code

I Incircle and Circumcircle http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5338

机智的用不对的三分过了。定义圆都在y轴，定义三角形一个点在圆心，定义三角形是等腰的。

 1 #include<cstdio>
 2 #include<cmath>
 3 const double eps=1e-10;
 4 double r,R;
 5 double f(double y) {
 6     double Y=2*R*(1-(r*r)/(y*y));
 7     return fabs(Y-y-r);
 8 }
 9 double TernarySearch(double L,double R) { // 三分查找
10     while(R-L>eps) {
11         double LL=(L*2+R)/3;
12         double RR=(L+R*2)/3;
13         if(f(LL)<f(RR))  //f为对应的值  这里求最小值
14             R=RR;
15         else
16             L=LL;
17     }
18     return L;
19 }
20 int main(){
21     int t1,t2;
22     while(~scanf("%d%d",&t1,&t2)){
23         if(t1*2>t2){
24             puts("NO Solution!");
25             continue;
26         }
27         r=t1;
28         R=t2;
29         double ansy=TernarySearch(r,R+R-r);
30         ansy+=r;
31         double tmp=ansy-r;
32         double sinxita=r/tmp;
33         double cosxita=sqrt(tmp*tmp-r*r)/tmp;
34         double a=ansy*tmp/sqrt(tmp*tmp-r*r);
35         double b=a;
36         double c=2*a*r/tmp;
37         printf("%.18f %.18f %.18f
",a,b,c);
38     }
39     return 0;
40 }

View Code

end