CSPS模拟88-91
感觉自己好菜啊，考得一次不如一次了。。。压力好大，++滚粗感。
模拟88。
T1，sbt，发现离散化后数据范围变为6000，直接跑暴力即可。%%%机房众神斜率优化。
T2，大模拟，考场上只会乱搞骗分。本人菜鸡，只会大力分类讨论。。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const double eps=5e-5; 4 double f[100][100],f1[100][100],f2[100][100]; 5 double dp[110][10][10][10][10]; 6 double ans[6][10]; 7 int a[6][10],tt[10]; 8 int n; 9 char s1[20],s2[20],s3[20]; 10 double gg; 11 inline void prans(int id) 12 { 13 double gg=1.0; 14 memset(ans,0,sizeof(ans)); 15 for(int j=1;j<=8;++j) 16 for(int k=1;k<=8;++k) 17 for(int o=1;o<=8;++o) 18 for(int l=1;l<=8;++l) 19 { 20 gg-=dp[id][j][k][o][l]; 21 ans[1][a[1][j]]+=dp[id][j][k][o][l]; 22 ans[2][a[2][k]]+=dp[id][j][k][o][l]; 23 ans[3][a[3][o]]+=dp[id][j][k][o][l]; 24 ans[4][a[4][l]]+=dp[id][j][k][o][l]; 25 } 26 printf("%.2lf ",gg*100); 27 for(int i=1;i<=4;++i) 28 { 29 for(int j=1;j<=8;++j) 30 { 31 printf("%.2lf ",ans[i][j]*100); 32 } 33 puts(""); 34 } 35 } 36 inline void init() 37 { 38 f[1][0]=f[1][1]=f[1][2]=1.0/3; 39 for(int i=1;i<=80;++i){ 40 for(int j=0;j<=80;++j){ 41 if(j)f1[i][j]=f1[i][j-1]; 42 f1[i][j]+=f[i][j]; 43 f[i+1][j]+=f[i][j]*f[1][0]; 44 f[i+1][j+1]+=f[i][j]*f[1][1]; 45 f[i+1][j+2]+=f[i][j]*f[1][2]; 46 } 47 for(int j=80;~j;--j)f2[i][j]=f2[i][j+1]+f[i][j]; 48 } 49 } 50 void work1(int m,int i,int num,int isw,double g=1.0,int fj=1,int fk=1,int fo=1,int fl=1,int jj=8,int kk=8,int oo=8,int ll=8) 51 { 52 if(m==1) 53 { 54 if(isw) 55 { 56 for(int j=fj;j<=jj;++j) 57 for(int k=fk;k<=kk;++k) 58 for(int o=fo;o<=oo;++o) 59 for(int l=fl;l<=ll;++l) 60 for(int t=0;t<=2*num;++t) 61 dp[i+1][min(j+t,8)][k][o][l]+=dp[i][j][k][o][l]*f[num][t]*g; 62 } 63 else 64 { 65 for(int j=fj;j<=jj;++j) 66 for(int k=fk;k<=kk;++k) 67 for(int o=fo;o<=oo;++o) 68 for(int l=fl;l<=ll;++l) 69 dp[i+1][min(j+num,8)][k][o][l]+=dp[i][j][k][o][l]*g; 70 } 71 } 72 else if(m==2) 73 { 74 if(isw) 75 { 76 for(int j=fj;j<=jj;++j) 77 for(int k=fk;k<=kk;++k) 78 for(int o=fo;o<=oo;++o) 79 for(int l=fl;l<=ll;++l) 80 for(int t=0;t<=2*num;++t) 81 dp[i+1][j][min(k+t,8)][o][l]+=dp[i][j][k][o][l]*f[num][t]*g; 82 } 83 else 84 { 85 for(int j=fj;j<=jj;++j) 86 for(int k=fk;k<=kk;++k) 87 for(int o=fo;o<=oo;++o) 88 for(int l=fl;l<=ll;++l) 89 dp[i+1][j][min(k+num,8)][o][l]+=dp[i][j][k][o][l]*g; 90 } 91 } 92 else if(m==3) 93 { 94 if(isw) 95 { 96 for(int j=fj;j<=jj;++j) 97 for(int k=fk;k<=kk;++k) 98 for(int o=fo;o<=oo;++o) 99 for(int l=fl;l<=ll;++l) 100 for(int t=0;t<=2*num;++t) 101 dp[i+1][j][k][min(o+t,8)][l]+=dp[i][j][k][o][l]*f[num][t]*g; 102 } 103 else 104 { 105 for(int j=fj;j<=jj;++j) 106 for(int k=fk;k<=kk;++k) 107 for(int o=fo;o<=oo;++o) 108 for(int l=fl;l<=ll;++l) 109 dp[i+1][j][k][min(o+num,8)][l]+=dp[i][j][k][o][l]*g; 110 } 111 } 112 else 113 { 114 if(isw) 115 { 116 for(int j=fj;j<=jj;++j) 117 for(int k=fk;k<=kk;++k) 118 for(int o=fo;o<=oo;++o) 119 for(int l=fl;l<=ll;++l) 120 for(int t=0;t<=2*num;++t) 121 dp[i+1][j][k][o][min(l+t,8)]+=dp[i][j][k][o][l]*f[num][t]*g; 122 } 123 else 124 { 125 for(int j=fj;j<=jj;++j) 126 for(int k=fk;k<=kk;++k) 127 for(int o=fo;o<=oo;++o) 128 for(int l=fl;l<=ll;++l) 129 dp[i+1][j][k][o][min(l+num,8)]+=dp[i][j][k][o][l]*g; 130 } 131 } 132 } 133 //////////////////////////////////////////////////分界线work1&2/////////////////////////////////////////////////////////////// 134 void work2(int m,int i,int num,int isw,double g=1.0,int fj=1,int fk=1,int fo=1,int fl=1,int jj=8,int kk=8,int oo=8,int ll=8) 135 { 136 if(m==1) 137 { 138 if(isw) 139 { 140 for(int j=fj;j<=jj;++j) 141 for(int k=fk;k<=kk;++k) 142 for(int o=fo;o<=oo;++o) 143 for(int l=fl;l<=ll;++l) 144 for(int t=0;t<=2*num;++t) 145 dp[i+1][max(j-t,0)][k][o][l]+=dp[i][j][k][o][l]*f[num][t]*g; 146 } 147 else 148 { 149 for(int j=fj;j<=jj;++j) 150 for(int k=fk;k<=kk;++k) 151 for(int o=fo;o<=oo;++o) 152 for(int l=fl;l<=ll;++l) 153 dp[i+1][max(j-num,0)][k][o][l]+=dp[i][j][k][o][l]*g; 154 } 155 } 156 else if(m==2) 157 { 158 if(isw) 159 { 160 for(int j=fj;j<=jj;++j) 161 for(int k=fk;k<=kk;++k) 162 for(int o=fo;o<=oo;++o) 163 for(int l=fl;l<=ll;++l) 164 for(int t=0;t<=2*num;++t) 165 dp[i+1][j][max(k-t,0)][o][l]+=dp[i][j][k][o][l]*f[num][t]*g; 166 } 167 else 168 { 169 for(int j=fj;j<=jj;++j) 170 for(int k=fk;k<=kk;++k) 171 for(int o=fo;o<=oo;++o) 172 for(int l=fl;l<=ll;++l) 173 dp[i+1][j][max(k-num,0)][o][l]+=dp[i][j][k][o][l]*g; 174 } 175 } 176 else if(m==3) 177 { 178 if(isw) 179 { 180 for(int j=fj;j<=jj;++j) 181 for(int k=fk;k<=kk;++k) 182 for(int o=fo;o<=oo;++o) 183 for(int l=fl;l<=ll;++l) 184 for(int t=0;t<=2*num;++t) 185 dp[i+1][j][k][max(o-t,0)][l]+=dp[i][j][k][o][l]*f[num][t]*g; 186 } 187 else 188 { 189 for(int j=fj;j<=jj;++j) 190 for(int k=fk;k<=kk;++k) 191 for(int o=fo;o<=oo;++o) 192 for(int l=fl;l<=ll;++l) 193 dp[i+1][j][k][max(o-num,0)][l]+=dp[i][j][k][o][l]*g; 194 } 195 } 196 else 197 { 198 if(isw) 199 { 200 for(int j=fj;j<=jj;++j) 201 for(int k=fk;k<=kk;++k) 202 for(int o=fo;o<=oo;++o) 203 for(int l=fl;l<=ll;++l) 204 for(int t=0;t<=2*num;++t) 205 dp[i+1][j][k][o][max(l-t,0)]+=dp[i][j][k][o][l]*f[num][t]*g; 206 } 207 else 208 { 209 for(int j=fj;j<=jj;++j) 210 for(int k=fk;k<=kk;++k) 211 for(int o=fo;o<=oo;++o) 212 for(int l=fl;l<=ll;++l) 213 dp[i+1][j][k][o][max(l-num,0)]+=dp[i][j][k][o][l]*g; 214 } 215 } 216 } 217 218 int main() 219 { 220 // freopen("da.in","r",stdin); 221 init(); 222 for(int i=1,x;i<=4;++i){ 223 scanf("%d%d",&a[i][8],&tt[i]); 224 for(int j=8;j;--j){a[i][j-1]=a[i][j]/10;a[i][j]%=10;} 225 } 226 dp[1][tt[1]][tt[2]][tt[3]][tt[4]]=1.0; 227 scanf("%d",&n); 228 /* 229 t1:当前处理点 230 t2:受影响点 231 i:当前处理的操作 232 l2:数字串长度，对？处理 233 tag:标记是否有问号 234 tg2:标记是否有= 235 */ 236 for(int i=1,t1,t2,l2,num,tag,tg2;i<=n;++i)//work2(int m,int i,int num,int isw) 237 { 238 // if(i==5)prans(i); 239 t1=l2=tag=num=tg2=0; 240 scanf("%s%s",s1,s2+1); 241 l2=strlen(s2+1); 242 if(s1[1]=='i')t1=1; 243 else if(s1[1]=='p')t1=2; 244 else if(s1[1]=='a')t1=3; 245 else t1=4; 246 switch(s2[1]) 247 { 248 case '<': 249 { 250 scanf("%d",&tg2); 251 if(l2==2)++tg2; 252 scanf("%s%s",s1,s2+1); 253 if(s1[1]=='i')t2=1; 254 else if(s1[1]=='p')t2=2; 255 else if(s1[1]=='a')t2=3; 256 else t2=4; 257 258 l2=strlen(s2+1); 259 for(int j=2;j<l2;++j)num=num*10+s2[j]-'0'; 260 if(s2[l2]=='?')tag=1; 261 else num=num*10+s2[l2]-'0'; 262 for(int j=1;j<=8;++j) 263 for(int k=1;k<=8;++k) 264 for(int o=1;o<=8;++o) 265 for(int l=1;l<=8;++l){ 266 if(t1==1) 267 { 268 for(int tmd=0;tmd<=2*a[1][j];++tmd) 269 { 270 if(tmd>=tg2) 271 { 272 dp[i+1][j][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 273 continue; 274 } 275 if(t2==1) 276 { 277 if(tag){ 278 for(int t=0;t<=num*2;++t){ 279 if(s2[1]=='+')dp[i+1][min(j+t,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 280 else dp[i+1][max(j-t,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 281 } 282 } 283 else 284 { 285 if(s2[1]=='+')dp[i+1][min(j+num,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 286 else dp[i+1][max(j-num,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 287 } 288 } 289 else if(t2==2) 290 { 291 if(tag){ 292 for(int t=0;t<=num*2;++t){ 293 if(s2[1]=='+')dp[i+1][j][min(k+t,8)][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 294 else dp[i+1][j][max(k-t,0)][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 295 } 296 } 297 else 298 { 299 if(s2[1]=='+')dp[i+1][j][min(k+num,8)][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 300 else dp[i+1][j][max(k-num,0)][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 301 } 302 } 303 else if(t2==3) 304 { 305 if(tag){ 306 for(int t=0;t<=num*2;++t){ 307 if(s2[1]=='+')dp[i+1][j][k][min(o+t,8)][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 308 else dp[i+1][j][k][max(o-t,0)][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 309 } 310 } 311 else 312 { 313 if(s2[1]=='+')dp[i+1][j][k][min(o+num,8)][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 314 else dp[i+1][j][k][max(o-num,0)][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 315 } 316 } 317 else 318 { 319 if(tag){ 320 for(int t=0;t<=num*2;++t){ 321 if(s2[1]=='+')dp[i+1][j][k][o][min(l+t,8)]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 322 else dp[i+1][j][k][o][max(l-t,0)]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 323 } 324 } 325 else 326 { 327 if(s2[1]=='+')dp[i+1][j][k][o][min(l+num,8)]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 328 else dp[i+1][j][k][o][max(l-num,0)]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 329 } 330 } 331 } 332 } 333 else if(t1==2) 334 { 335 for(int tmd=0;tmd<=2*a[2][k];++tmd) 336 { 337 if(tmd>=tg2) 338 { 339 dp[i+1][j][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 340 continue; 341 } 342 if(t2==1) 343 { 344 if(tag){ 345 for(int t=0;t<=num*2;++t){ 346 if(s2[1]=='+')dp[i+1][min(j+t,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 347 else dp[i+1][max(j-t,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 348 } 349 } 350 else 351 { 352 if(s2[1]=='+')dp[i+1][min(j+num,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 353 else dp[i+1][max(j-num,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 354 } 355 } 356 else if(t2==2) 357 { 358 if(tag){ 359 for(int t=0;t<=num*2;++t){ 360 if(s2[1]=='+')dp[i+1][j][min(k+t,8)][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 361 else dp[i+1][j][max(k-t,0)][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 362 } 363 } 364 else 365 { 366 if(s2[1]=='+')dp[i+1][j][min(k+num,8)][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 367 else dp[i+1][j][max(k-num,0)][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 368 } 369 } 370 else if(t2==3) 371 { 372 if(tag){ 373 for(int t=0;t<=num*2;++t){ 374 if(s2[1]=='+')dp[i+1][j][k][min(o+t,8)][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 375 else dp[i+1][j][k][max(o-t,0)][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 376 } 377 } 378 else 379 { 380 if(s2[1]=='+')dp[i+1][j][k][min(o+num,8)][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 381 else dp[i+1][j][k][max(o-num,0)][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 382 } 383 } 384 else 385 { 386 if(tag){ 387 for(int t=0;t<=num*2;++t){ 388 if(s2[1]=='+')dp[i+1][j][k][o][min(l+t,8)]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 389 else dp[i+1][j][k][o][max(l-t,0)]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 390 } 391 } 392 else 393 { 394 if(s2[1]=='+')dp[i+1][j][k][o][min(l+num,8)]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 395 else dp[i+1][j][k][o][max(l-num,0)]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 396 } 397 } 398 } 399 } 400 else if(t1==3) 401 { 402 for(int tmd=0;tmd<=2*a[3][o];++tmd) 403 { 404 if(tmd>=tg2) 405 { 406 dp[i+1][j][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 407 continue; 408 } 409 if(t2==1) 410 { 411 if(tag){ 412 for(int t=0;t<=num*2;++t){ 413 if(s2[1]=='+')dp[i+1][min(j+t,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 414 else dp[i+1][max(j-t,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 415 } 416 } 417 else 418 { 419 if(s2[1]=='+')dp[i+1][min(j+num,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 420 else dp[i+1][max(j-num,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 421 } 422 } 423 else if(t2==2) 424 { 425 if(tag){ 426 for(int t=0;t<=num*2;++t){ 427 if(s2[1]=='+')dp[i+1][j][min(k+t,8)][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 428 else dp[i+1][j][max(k-t,0)][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 429 } 430 } 431 else 432 { 433 if(s2[1]=='+')dp[i+1][j][min(k+num,8)][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 434 else dp[i+1][j][max(k-num,0)][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 435 } 436 } 437 else if(t2==3) 438 { 439 if(tag){ 440 for(int t=0;t<=num*2;++t){ 441 if(s2[1]=='+')dp[i+1][j][k][min(o+t,8)][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 442 else dp[i+1][j][k][max(o-t,0)][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 443 } 444 } 445 else 446 { 447 if(s2[1]=='+')dp[i+1][j][k][min(o+num,8)][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 448 else dp[i+1][j][k][max(o-num,0)][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 449 } 450 } 451 else/////////////////////////////////////////////////////////////////here 452 { 453 if(tag){ 454 for(int t=0;t<=num*2;++t){ 455 // cout<<t<<endl; 456 if(s2[1]=='+')dp[i+1][j][k][o][min(l+t,8)]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 457 else dp[i+1][j][k][o][max(l-t,0)]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 458 } 459 } 460 else 461 { 462 if(s2[1]=='+')dp[i+1][j][k][o][min(l+num,8)]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 463 else dp[i+1][j][k][o][max(l-num,0)]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 464 } 465 } 466 } 467 } 468 else 469 { 470 for(int tmd=0;tmd<=2*a[4][l];++tmd) 471 { 472 if(tmd>=tg2) 473 { 474 dp[i+1][j][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 475 continue; 476 } 477 if(t2==1) 478 { 479 if(tag){ 480 for(int t=0;t<=num*2;++t){ 481 if(s2[1]=='+')dp[i+1][min(j+t,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 482 else dp[i+1][max(j-t,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 483 } 484 } 485 else 486 { 487 if(s2[1]=='+')dp[i+1][min(j+num,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 488 else dp[i+1][max(j-num,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 489 } 490 } 491 else if(t2==2) 492 { 493 if(tag){ 494 for(int t=0;t<=num*2;++t){ 495 if(s2[1]=='+')dp[i+1][j][min(k+t,8)][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 496 else dp[i+1][j][max(k-t,0)][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 497 } 498 } 499 else 500 { 501 if(s2[1]=='+')dp[i+1][j][min(k+num,8)][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 502 else dp[i+1][j][max(k-num,0)][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 503 } 504 } 505 else if(t2==3) 506 { 507 if(tag){ 508 for(int t=0;t<=num*2;++t){ 509 if(s2[1]=='+')dp[i+1][j][k][min(o+t,8)][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 510 else dp[i+1][j][k][max(o-t,0)][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 511 } 512 } 513 else 514 { 515 if(s2[1]=='+')dp[i+1][j][k][min(o+num,8)][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 516 else dp[i+1][j][k][max(o-num,0)][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 517 } 518 } 519 else 520 { 521 if(tag){ 522 for(int t=0;t<=num*2;++t){ 523 if(s2[1]=='+')dp[i+1][j][k][o][min(l+t,8)]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 524 else dp[i+1][j][k][o][max(l-t,0)]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 525 } 526 } 527 else 528 { 529 if(s2[1]=='+')dp[i+1][j][k][o][min(l+num,8)]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 530 else dp[i+1][j][k][o][max(l-num,0)]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 531 } 532 } 533 } 534 } 535 } 536 break; 537 } 538 case '>': 539 { 540 scanf("%d",&tg2); 541 if(l2==2)--tg2; 542 scanf("%s%s",s1,s2+1); 543 if(s1[1]=='i')t2=1; 544 else if(s1[1]=='p')t2=2; 545 else if(s1[1]=='a')t2=3; 546 else t2=4; 547 548 l2=strlen(s2+1); 549 for(int j=2;j<l2;++j)num=num*10+s2[j]-'0'; 550 if(s2[l2]=='?')tag=1; 551 else num=num*10+s2[l2]-'0'; 552 553 for(int j=1;j<=8;++j) 554 for(int k=1;k<=8;++k) 555 for(int o=1;o<=8;++o) 556 for(int l=1;l<=8;++l) 557 if(t1==1) 558 { 559 for(int tmd=0;tmd<=2*a[1][j];++tmd) 560 { 561 if(tmd<=tg2) 562 { 563 dp[i+1][j][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 564 continue; 565 } 566 if(t2==1) 567 { 568 if(tag){ 569 for(int t=0;t<=num*2;++t){ 570 if(s2[1]=='+')dp[i+1][min(j+t,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 571 else dp[i+1][max(j-t,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 572 } 573 } 574 else 575 { 576 if(s2[1]=='+')dp[i+1][min(j+num,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 577 else dp[i+1][max(j-num,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 578 } 579 } 580 else if(t2==2) 581 { 582 if(tag){ 583 for(int t=0;t<=num*2;++t){ 584 if(s2[1]=='+')dp[i+1][j][min(k+t,8)][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 585 else dp[i+1][j][max(k-t,0)][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 586 } 587 } 588 else 589 { 590 if(s2[1]=='+')dp[i+1][j][min(k+num,8)][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 591 else dp[i+1][j][max(k-num,0)][o][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 592 } 593 } 594 else if(t2==3) 595 { 596 if(tag){ 597 for(int t=0;t<=num*2;++t){ 598 if(s2[1]=='+')dp[i+1][j][k][min(o+t,8)][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 599 else dp[i+1][j][k][max(o-t,0)][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 600 } 601 } 602 else 603 { 604 if(s2[1]=='+')dp[i+1][j][k][min(o+num,8)][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 605 else dp[i+1][j][k][max(o-num,0)][l]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 606 } 607 } 608 else 609 { 610 if(tag){ 611 for(int t=0;t<=num*2;++t){ 612 if(s2[1]=='+')dp[i+1][j][k][o][min(l+t,8)]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 613 else dp[i+1][j][k][o][max(l-t,0)]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]*f[num][t]; 614 } 615 } 616 else 617 { 618 if(s2[1]=='+')dp[i+1][j][k][o][min(l+num,8)]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 619 else dp[i+1][j][k][o][max(l-num,0)]+=dp[i][j][k][o][l]*f[a[1][j]][tmd]; 620 } 621 } 622 } 623 } 624 else if(t1==2) 625 { 626 for(int tmd=0;tmd<=2*a[2][k];++tmd) 627 { 628 if(tmd<=tg2) 629 { 630 dp[i+1][j][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 631 continue; 632 } 633 if(t2==1) 634 { 635 if(tag){ 636 for(int t=0;t<=num*2;++t){ 637 if(s2[1]=='+')dp[i+1][min(j+t,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 638 else dp[i+1][max(j-t,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 639 } 640 } 641 else 642 { 643 if(s2[1]=='+')dp[i+1][min(j+num,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 644 else dp[i+1][max(j-num,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 645 } 646 } 647 else if(t2==2) 648 { 649 if(tag){ 650 for(int t=0;t<=num*2;++t){ 651 if(s2[1]=='+')dp[i+1][j][min(k+t,8)][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 652 else dp[i+1][j][max(k-t,0)][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 653 } 654 } 655 else 656 { 657 if(s2[1]=='+')dp[i+1][j][min(k+num,8)][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 658 else dp[i+1][j][max(k-num,0)][o][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 659 } 660 } 661 else if(t2==3) 662 { 663 if(tag){ 664 for(int t=0;t<=num*2;++t){ 665 if(s2[1]=='+')dp[i+1][j][k][min(o+t,8)][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 666 else dp[i+1][j][k][max(o-t,0)][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 667 } 668 } 669 else 670 { 671 if(s2[1]=='+')dp[i+1][j][k][min(o+num,8)][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 672 else dp[i+1][j][k][max(o-num,0)][l]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 673 } 674 } 675 else 676 { 677 if(tag){ 678 for(int t=0;t<=num*2;++t){ 679 if(s2[1]=='+')dp[i+1][j][k][o][min(l+t,8)]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 680 else dp[i+1][j][k][o][max(l-t,0)]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]*f[num][t]; 681 } 682 } 683 else 684 { 685 if(s2[1]=='+')dp[i+1][j][k][o][min(l+num,8)]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 686 else dp[i+1][j][k][o][max(l-num,0)]+=dp[i][j][k][o][l]*f[a[2][k]][tmd]; 687 } 688 } 689 } 690 } 691 else if(t1==3) 692 { 693 for(int tmd=0;tmd<=2*a[3][o];++tmd) 694 { 695 if(tmd<=tg2) 696 { 697 dp[i+1][j][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 698 continue; 699 } 700 if(t2==1) 701 { 702 if(tag){ 703 for(int t=0;t<=num*2;++t){ 704 if(s2[1]=='+')dp[i+1][min(j+t,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 705 else dp[i+1][max(j-t,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 706 } 707 } 708 else 709 { 710 if(s2[1]=='+')dp[i+1][min(j+num,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 711 else dp[i+1][max(j-num,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 712 } 713 } 714 else if(t2==2) 715 { 716 if(tag){ 717 for(int t=0;t<=num*2;++t){ 718 if(s2[1]=='+')dp[i+1][j][min(k+t,8)][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 719 else dp[i+1][j][max(k-t,0)][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 720 } 721 } 722 else 723 { 724 if(s2[1]=='+')dp[i+1][j][min(k+num,8)][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 725 else dp[i+1][j][max(k-num,0)][o][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 726 } 727 } 728 else if(t2==3) 729 { 730 if(tag){ 731 for(int t=0;t<=num*2;++t){ 732 if(s2[1]=='+')dp[i+1][j][k][min(o+t,8)][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 733 else dp[i+1][j][k][max(o-t,0)][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 734 } 735 } 736 else 737 { 738 if(s2[1]=='+')dp[i+1][j][k][min(o+num,8)][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 739 else dp[i+1][j][k][max(o-num,0)][l]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 740 } 741 } 742 else 743 { 744 745 if(tag){ 746 for(int t=0;t<=num*2;++t){ 747 if(s2[1]=='+')dp[i+1][j][k][o][min(l+t,8)]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 748 else dp[i+1][j][k][o][max(l-t,0)]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]*f[num][t]; 749 } 750 } 751 else 752 { 753 if(s2[1]=='+')dp[i+1][j][k][o][min(l+num,8)]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 754 else dp[i+1][j][k][o][max(l-num,0)]+=dp[i][j][k][o][l]*f[a[3][o]][tmd]; 755 } 756 } 757 } 758 } 759 else 760 { 761 for(int tmd=0;tmd<=2*a[4][l];++tmd) 762 { 763 if(tmd<=tg2) 764 { 765 dp[i+1][j][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 766 continue; 767 } 768 if(t2==1) 769 { 770 if(tag){ 771 for(int t=0;t<=num*2;++t){ 772 if(s2[1]=='+')dp[i+1][min(j+t,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 773 else dp[i+1][max(j-t,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 774 } 775 } 776 else 777 { 778 if(s2[1]=='+')dp[i+1][min(j+num,8)][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 779 else dp[i+1][max(j-num,0)][k][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 780 } 781 } 782 else if(t2==2) 783 { 784 if(tag){ 785 for(int t=0;t<=num*2;++t){ 786 if(s2[1]=='+')dp[i+1][j][min(k+t,8)][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 787 else dp[i+1][j][max(k-t,0)][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 788 } 789 } 790 else 791 { 792 if(s2[1]=='+')dp[i+1][j][min(k+num,8)][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 793 else dp[i+1][j][max(k-num,0)][o][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 794 } 795 } 796 else if(t2==3) 797 { 798 if(tag){ 799 for(int t=0;t<=num*2;++t){ 800 if(s2[1]=='+')dp[i+1][j][k][min(o+t,8)][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 801 else dp[i+1][j][k][max(o-t,0)][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 802 } 803 } 804 else 805 { 806 if(s2[1]=='+')dp[i+1][j][k][min(o+num,8)][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 807 else dp[i+1][j][k][max(o-num,0)][l]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 808 } 809 } 810 else 811 { 812 if(tag){ 813 for(int t=0;t<=num*2;++t){ 814 if(s2[1]=='+')dp[i+1][j][k][o][min(l+t,8)]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 815 else dp[i+1][j][k][o][max(l-t,0)]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]*f[num][t]; 816 } 817 } 818 else 819 { 820 if(s2[1]=='+')dp[i+1][j][k][o][min(l+num,8)]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 821 else dp[i+1][j][k][o][max(l-num,0)]+=dp[i][j][k][o][l]*f[a[4][l]][tmd]; 822 } 823 } 824 } 825 } 826 break; 827 } 828 case '+': 829 { 830 for(int j=2;j<l2;++j)num=num*10+s2[j]-'0'; 831 if(s2[l2]=='?')tag=1; 832 else num=num*10+s2[l2]-'0'; 833 work1(t1,i,num,tag); 834 break; 835 } 836 case '-': 837 { 838 for(int j=2;j<l2;++j)num=num*10+s2[j]-'0'; 839 if(s2[l2]=='?')tag=1; 840 else num=num*10+s2[l2]-'0'; 841 work2(t1,i,num,tag); 842 break; 843 } 844 } 845 } 846 prans(n+1); 847 }
T3，dp or 记搜，考场上像一个sb一样打了状压，其实值域只有0，1，2，3。记录每一种有多少个以及上一次的操作即可。注意打高精
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 #define N 13 7 using namespace std; 8 int n,a[N],sta; 9 int bk[N]; 10 struct Big_int{ 11 int a[60]; 12 inline void init(int x){while(x){a[++a[0]]=x%10;x/=10;}} 13 inline bool empty(){return !a[0];} 14 15 inline void print() 16 { 17 for(int i=a[0];i;--i)printf("%d",a[i]); 18 puts(""); 19 } 20 }dp[40][N][N][N][4]; 21 inline void add( Big_int &c,const Big_int &x,const int y) 22 { 23 if(!y)return; 24 c.a[0]=max(c.a[0],x.a[0]);int t=0; 25 for(int i=1;i<=c.a[0];++i){ 26 c.a[i]+=x.a[i]*y+t; 27 t=c.a[i]/10;c.a[i]%=10; 28 } 29 while(t)c.a[++c.a[0]]=t%10,t/=10; 30 return; 31 } 32 inline void work2() 33 { 34 int al=0,cnt=0; 35 for(int i=1;i<=n;++i)al+=a[i]; 36 dp[1][bk[1]][bk[2]+1][bk[3]-1][2].init(bk[3]); 37 dp[1][bk[1]+1][bk[2]-1][bk[3]][1].init(bk[2]); 38 dp[1][bk[1]-1][bk[2]][bk[3]][0].init(bk[1]); 39 for(int o=1;o<al;++o) 40 for(int i=0;i<=n;++i) 41 for(int j=0;j<=n;++j) 42 for(int k=0;k<=n;++k) 43 for(int p=0;p<=2;++p){ 44 if(dp[o][i][j][k][p].empty())continue; 45 // printf("dp[%d][%d][%d][%d][%d]=",o,i,j,k,p);dp[o][i][j][k][p].print(); 46 if(k)add(dp[o+1][i][j+1][k-1][2],dp[o][i][j][k][p],k); 47 if(j)add(dp[o+1][i+1][j-1][k][1],dp[o][i][j][k][p],j-(p==2)); 48 if(i)add(dp[o+1][i-1][j][k][0],dp[o][i][j][k][p],i-(p==1)); 49 } 50 dp[al][0][0][0][0].print(); 51 } 52 int main() 53 { 54 cin>>n; 55 for(int i=1;i<=n;++i)cin>>a[i],++bk[a[i]]; 56 work2();return 0; 57 }