【NOI2013】小Q的修炼

题目链接：http://uoj.ac/problem/123

又开提答坑啦，要不是一定要讲题谁他妈要这样伤害自己

CASE 1,2

　　首先可以打一个通用暴力,用于模拟操作过程，对于每一个操作随机一个选择，然后跑多次记录答案。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 #include<string>
  9 #include<ctime>
 10 using namespace std;
 11 #define maxn 1000010
 12 #define llg long long 
 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 14 llg n,m,dl[maxn],tail,anst,ans[maxn],val[maxn],maxl,cs;
 15 llg T=1;
 16 char ch,s[maxn];
 17 
 18 llg next_x(llg x){x++; while (s[x]==' ')  x++; return x;}
 19 
 20 struct node
 21 {
 22     llg type;
 23     llg t1,v1,t2,v2,fu,to1,to2;
 24 }a[maxn];
 25 
 26 llg make_number(llg &x)
 27 {
 28     llg val=0,p=1;
 29     if (s[x]=='-') x++,p=-1;
 30     while (s[x]>='0' && s[x]<='9')
 31     {
 32         val*=10;
 33         val+=s[x]-'0';
 34         x++;
 35     }
 36     return val*p;
 37 }
 38 
 39 void Decompression_(llg i)
 40 {
 41 
 42     llg x=1;
 43     if (s[x]=='v')
 44     {
 45         a[i].type=1;
 46         x=next_x(x);
 47         a[i].v1=make_number(x);
 48         x=next_x(x);
 49         if (s[x]=='+') a[i].fu=1;else a[i].fu=-1;
 50         x=next_x(x);
 51         if (s[x]=='c') a[i].t2=0; else a[i].t2=1;
 52         x=next_x(x);
 53         a[i].v2=make_number(x);
 54     }
 55     if (s[x]=='s')
 56     {
 57         a[i].type=2;
 58         x=next_x(x);
 59         a[i].to1=make_number(x);
 60         x=next_x(x);
 61         a[i].to2=make_number(x);
 62     }
 63     if (s[x]=='i')
 64     {
 65         a[i].type=3;
 66         x=next_x(x);
 67         if (s[x]=='c') a[i].t1=0; else a[i].t1=1;
 68         x=next_x(x);
 69         a[i].v1=make_number(x);
 70         x=next_x(x);
 71         if (s[x]=='c') a[i].t2=0; else a[i].t2=1;
 72         x=next_x(x);
 73         a[i].v2=make_number(x);
 74         x=next_x(x);
 75         a[i].to1=make_number(x);
 76         x=next_x(x);
 77         a[i].to2=make_number(x);
 78     }
 79 }
 80 
 81 bool pd(char ch)
 82 {
 83     if (ch>='0' && ch<='9') return 1;
 84     if (ch=='v' || ch=='i' || ch=='+' || ch=='-' || ch=='s' || ch=='c' || ch==' ') return 1;
 85     return 0;
 86 }
 87 
 88 void init()
 89 {
 90     cin>>n>>m;
 91     ch=getchar(); 
 92     for (llg i=1;i<=n;i++)
 93     {
 94         llg len=0;
 95         ch=getchar();
 96         while (pd(ch)) {s[++len]=ch; ch=getchar();}
 97         Decompression_(i);
 98         for (llg i=0;i<=len+1;i++) s[i]='';
 99     }
100 }
101 
102 void work()
103 {
104     cs=0;
105     llg x=1,cho;
106     tail=0;
107     for (llg i=1;i<=m;i++) val[i]=0;
108     while (x>=1 && x<=n)
109     {
110         if (a[x].type==1)
111         {
112             if (a[x].t2) val[a[x].v1]+=val[a[x].v2]*a[x].fu;
113             else val[a[x].v1]+=a[x].v2*a[x].fu;
114             x++;
115         }
116         if (a[x].type==2)
117         {
118             cs++;
119             if (cs>1000000) {return ;}
120             cho=rand()%2+1;
121             if (cho==1) x=a[x].to1; else x=a[x].to2;
122             dl[++tail]=cho;
123         }
124         if (a[x].type==3)
125         {
126             llg val1,val2;
127             if (a[x].t1) val1=val[a[x].v1];else val1=a[x].v1;
128             if (a[x].t2) val2=val[a[x].v2];else val2=a[x].v2;
129             if (val1<val2) x=a[x].to1; else x=a[x].to2;
130         }
131     }
132 }
133 
134 int main()
135 {
136     yyj("train7");
137     init();
138     srand(time(NULL));
139     fclose(stdin);
140 //    freopen("make.in","r",stdin);
141     maxl=(llg)1e16*-1;
142     T=300000000;
143     while (T--)
144     {
145 //        system("make.exe");
146         work();
147         if (val[1]>maxl && cs<=1000000)
148         {
149             maxl=val[1];
150             anst=tail;
151             for (llg i=1;i<=anst;i++) ans[i]=dl[i];
152         }
153     }
154 //    cout<<maxl<<endl;
155     for (llg i=1;i<=anst;i++) cout<<ans[i]<<endl;
156     return 0;
157 }

View Code

　　　这样可以过第一,二个点，然后一共有31分。。。。

Ans1:

View Code

Ans2:

View Code

CASE 3

　　　可以发现有很多块，但是每一个块会根据在这个块中的所有变量的变化来修改变量1的值，每一个块中又分为10+个小块，小块中是对于变量2-m的修改，小块首有选择语句，可以选择是否跳过这个小块。

　　　块与块之间又互不影响，因为块尾会把除了变量1的所有变量全部清空。

　　　所以说，我们可以爆搜每一个块中的小块的决策，然后统计答案即可。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 #include<string>
  9 #include<ctime>
 10 using namespace std;
 11 #define maxn 1000010
 12 #define llg long long 
 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 14 llg n,m,dl[maxn],tail,anst,ans[maxn],val[maxn],maxl,cs;
 15 llg T=1;
 16 char ch,s[maxn];
 17 
 18 llg next_x(llg x){x++; while (s[x]==' ')  x++; return x;}
 19 
 20 struct node
 21 {
 22     llg type;
 23     llg t1,v1,t2,v2,fu,to1,to2;
 24 }a[maxn];
 25 
 26 llg make_number(llg &x)
 27 {
 28     llg val=0,p=1;
 29     if (s[x]=='-') x++,p=-1;
 30     while (s[x]>='0' && s[x]<='9')
 31     {
 32         val*=10;
 33         val+=s[x]-'0';
 34         x++;
 35     }
 36     return val*p;
 37 }
 38 
 39 void Decompression_(llg i)
 40 {
 41 
 42     llg x=1;
 43     if (s[x]=='v')
 44     {
 45         a[i].type=1;
 46         x=next_x(x);
 47         a[i].v1=make_number(x);
 48         x=next_x(x);
 49         if (s[x]=='+') a[i].fu=1;else a[i].fu=-1;
 50         x=next_x(x);
 51         if (s[x]=='c') a[i].t2=0; else a[i].t2=1;
 52         x=next_x(x);
 53         a[i].v2=make_number(x);
 54     }
 55     if (s[x]=='s')
 56     {
 57         a[i].type=2;
 58         x=next_x(x);
 59         a[i].to1=make_number(x);
 60         x=next_x(x);
 61         a[i].to2=make_number(x);
 62     }
 63     if (s[x]=='i')
 64     {
 65         a[i].type=3;
 66         x=next_x(x);
 67         if (s[x]=='c') a[i].t1=0; else a[i].t1=1;
 68         x=next_x(x);
 69         a[i].v1=make_number(x);
 70         x=next_x(x);
 71         if (s[x]=='c') a[i].t2=0; else a[i].t2=1;
 72         x=next_x(x);
 73         a[i].v2=make_number(x);
 74         x=next_x(x);
 75         a[i].to1=make_number(x);
 76         x=next_x(x);
 77         a[i].to2=make_number(x);
 78     }
 79 }
 80 
 81 bool pd(char ch)
 82 {
 83     if (ch>='0' && ch<='9') return 1;
 84     if (ch=='v' || ch=='i' || ch=='+' || ch=='-' || ch=='s' || ch=='c' || ch==' ') return 1;
 85     return 0;
 86 }
 87 
 88 void init()
 89 {
 90     cin>>n>>m;
 91     ch=getchar(); 
 92     for (llg i=1;i<=n;i++)
 93     {
 94         llg len=0;
 95         ch=getchar();
 96         while (pd(ch)) {s[++len]=ch; ch=getchar();}
 97         Decompression_(i);
 98         for (llg i=0;i<=len+1;i++) s[i]='';
 99     }
100 }
101 
102 void work(llg x,llg up)
103 {
104     cs=0;
105     llg cho;
106     tail=0;
107     for (llg i=1;i<=m;i++) val[i]=0;
108     while (x>=1 && x<=up)
109     {
110         if (a[x].type==1)
111         {
112             if (a[x].t2) val[a[x].v1]+=val[a[x].v2]*a[x].fu;
113             else val[a[x].v1]+=a[x].v2*a[x].fu;
114             x++;
115             continue;
116         }
117         if (a[x].type==2)
118         {
119             cs++;
120             if (cs>1000000) {return ;}
121             cho=rand()%2+1;
122             if (cho==1) x=a[x].to1; else x=a[x].to2;
123             dl[++tail]=cho;
124             continue;
125         }
126         if (a[x].type==3)
127         {
128             llg val1,val2;
129             if (a[x].t1) val1=val[a[x].v1];else val1=a[x].v1;
130             if (a[x].t2) val2=val[a[x].v2];else val2=a[x].v2;
131             if (val1<val2) x=a[x].to1; else x=a[x].to2;
132             continue;
133         }
134     }
135 }
136 
137 int main()
138 {
139     yyj("train3");
140     init();
141     srand(time(NULL));
142     fclose(stdin);
143     for (llg i=1;i<=n;i+=170)
144     {
145         maxl=(llg)1e16*-1;
146         T=10000;
147         anst=0;
148         while (T--)
149         {
150             work(i,i+169);
151             if (val[1]>maxl && cs<=1000000)
152             {
153                 maxl=val[1];
154                 anst=tail;
155                 for (llg i=1;i<=anst;i++) ans[i]=dl[i];
156             }
157         }
158             for (llg i=1;i<=anst;i++) cout<<ans[i]<<endl;
159     }
160     return 0;
161 }

View Code

Ans3:

View Code

CASE 4,5,6

　　这些点的特点是只有两个变量，每一次跳转都和变量2有关，而且变量二的变化量并不大，每一个跳转操作并不会往回跳(没有后效性)，考虑做一次dp即可。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 #include<string>
  9 #include<ctime>
 10 #include<queue>
 11 using namespace std;
 12 #define maxn 1000010
 13 #define llg long long 
 14 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 15 llg n,m,tail,anst,ans[maxn],val[maxn],maxl,cs;
 16 llg T=1;
 17 char ch,s[maxn];
 18 
 19 llg next_x(llg x){x++; while (s[x]==' ')  x++; return x;}
 20 
 21 struct node
 22 {
 23     llg type;
 24     llg t1,v1,t2,v2,fu,to1,to2;
 25 }a[maxn];
 26 
 27 llg make_number(llg &x)
 28 {
 29     llg val=0,p=1;
 30     if (s[x]=='-') x++,p=-1;
 31     while (s[x]>='0' && s[x]<='9')
 32     {
 33         val*=10;
 34         val+=s[x]-'0';
 35         x++;
 36     }
 37     return val*p;
 38 }
 39 
 40 void Decompression_(llg i)
 41 {
 42 
 43     llg x=1;
 44     if (s[x]=='v')
 45     {
 46         a[i].type=1;
 47         x=next_x(x);
 48         a[i].v1=make_number(x);
 49         x=next_x(x);
 50         if (s[x]=='+') a[i].fu=1;else a[i].fu=-1;
 51         x=next_x(x);
 52         if (s[x]=='c') a[i].t2=0; else a[i].t2=1;
 53         x=next_x(x);
 54         a[i].v2=make_number(x);
 55     }
 56     if (s[x]=='s')
 57     {
 58         a[i].type=2;
 59         x=next_x(x);
 60         a[i].to1=make_number(x);
 61         x=next_x(x);
 62         a[i].to2=make_number(x);
 63     }
 64     if (s[x]=='i')
 65     {
 66         a[i].type=3;
 67         x=next_x(x);
 68         if (s[x]=='c') a[i].t1=0; else a[i].t1=1;
 69         x=next_x(x);
 70         a[i].v1=make_number(x);
 71         x=next_x(x);
 72         if (s[x]=='c') a[i].t2=0; else a[i].t2=1;
 73         x=next_x(x);
 74         a[i].v2=make_number(x);
 75         x=next_x(x);
 76         a[i].to1=make_number(x);
 77         x=next_x(x);
 78         a[i].to2=make_number(x);
 79     }
 80 }
 81 
 82 bool pd(char ch)
 83 {
 84     if (ch>='0' && ch<='9') return 1;
 85     if (ch=='v' || ch=='i' || ch=='+' || ch=='-' || ch=='s' || ch=='c' || ch==' ') return 1;
 86     return 0;
 87 }
 88 
 89 void init()
 90 {
 91     cin>>n>>m;
 92     ch=getchar(); 
 93     for (llg i=1;i<=n;i++)
 94     {
 95         llg len=0;
 96         ch=getchar();
 97         while (pd(ch)) {s[++len]=ch; ch=getchar();}
 98         Decompression_(i);
 99         for (llg i=0;i<=len+1;i++) s[i]='';
100     }
101 }
102 
103 struct data
104 {
105     llg val,k,from;
106 }dl[maxn];
107 
108 vector<data>f[maxn];
109 
110 void in(llg x,data w)
111 {
112     llg E=f[x].size();
113     for (llg i=0;i<E;i++)
114     {
115         if (f[x][i].k==w.k)
116         {
117             if (w.val>f[x][i].val) f[x][i]=w;
118             return ;
119         }
120     }
121     f[x].push_back(w);
122 }
123 
124 void work(data w,llg x)
125 {
126     llg nx; data nw=w;
127     nw.from=x;
128     if (a[x].type==1)
129     {
130         nx=x+1;
131         if (a[x].v1==1)
132         {
133             if (a[x].t2)
134             {
135                 if (a[x].v2==1) nw.val+=nw.val;else nw.val+=nw.k;
136             }
137             else nw.val+=a[x].v2;
138         }
139         else
140         {
141             if (a[x].t2)
142             {
143                 if(a[x].v2==1) nw.k+=nw.val; else nw.k+=nw.k;
144             }
145             else nw.k+=a[x].v2;
146         }
147         in(nx,nw);
148         return ;
149     }
150     if (a[x].type==2)
151     {
152         nx=a[x].to1;
153         if (nx>n || n<1) nx=0;
154         in(nx,nw);
155         nx=a[x].to2;
156         if (nx>n || n<1) nx=0;
157         in(nx,nw);
158         return ;
159     }
160     if (a[x].type==3)
161     {
162         llg v1,v2;
163         if (a[x].t1) {if (a[x].v1==1) v1=nw.val;else v1=nw.k;}else v1=a[x].v1;
164         if (a[x].t2) {if (a[x].v2==1) v2=nw.val;else v2=nw.k;}else v2=a[x].v2;
165         if (v1<v2) nx=a[x].to1;else nx=a[x].to2;
166         if (nx>n || n<1) nx=0;
167         in(nx,nw);
168         return ;
169     }
170 
171 }
172 
173 void dg(data x)
174 {
175 }
176 
177 int main()
178 {
179     yyj("train4");
180     init();
181     srand(time(NULL));
182     fclose(stdin);
183     data S; S.val=0,S.k=0,S.from=-1; 
184     f[1].push_back(S);
185     for (llg i=1;i<=n;i++)
186     {
187         data w;
188         llg W=f[i].size();
189 //        printf("%lld--->%lld
",i,W);
190         for (llg k=0;k<W;k++)
191         {
192             w=f[i][k]; 
193             work(w,i);
194         }
195     }
196     llg W=f[0].size();
197     for (llg i=0;i<W;i++)
198     {
199         if (f[0][i].val>maxl)
200         {
201             maxl=f[0][i].val;
202             S=f[0][i];
203         }
204     }
205     dg(f[0][i]);
206     return 0;
207 }

View Code

Ans4:

View Code

Ans5:

View Code

Ans6:

View Code

本文作者：xrdog 作者博客：http://www.cnblogs.com/Dragon-Light/ 转载请注明出处，侵权必究，保留最终解释权！