大大出的题
大大经常吐槽没有人补，所以我决定做一个康康
A. APA of Orz Pandas
题意：给你一个包含+-*/%和()的表达式，让你把它转化成java里BigInteger的形式
大概就像这样 "a.add(b).remainder(M).multiply(d.substract(e.multiply(f)).add(g.divide(h))).multiply (BigInteger.ValueOf(233)) ... ..."
有意思的模拟题，不是很好写
首先要看清题，a+(b+c)应该输出为a.add(b.add(c))而不是a.add(b).add(c)
我之前看错题，使得这个题难度高了一点，但是那样也可以做，只需预处理无用括号即可
观察可以发现，不存在(a.add(b)).add(c)这种说法，也就是说，括号的本质作用是改变运算顺序，然后把括号里的表达式作为一个对象参与运算
那么就可以把括号里的东西看成一个变量，然后问题就转化为没有括号的表达式的处理
对于括号中的括号，可以把输出写成参数l和r的函数，功能为输出下标为[l,r]的子区间，然后递归处理
接下来的问题是找到输出序列中括号的包含范围，例如a+b*c要表示为a.add(b.multiply(c))，如何找到add右括号的位置
可以开一个栈
左括号可以直接压入
当压入右括号时，可以把左右括号中的所有运算符，包括括号全部湮灭
当压入+-时，可以把所有栈头的运算符湮灭，并令其右括号的位置在此运算符之前，但应在遇到左括号时停止
当压入*/%时，可以把栈头的*/%运算符湮灭，并令其右括号的位置在此运算符之前，但应遇到左括号或+-为止
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 char fc[5][10]={ 8 {‘a‘,‘d‘,‘d‘,0}, 9 {‘s‘,‘u‘,‘b‘,‘s‘,‘t‘,‘r‘,‘a‘,‘c‘,‘t‘,0}, 10 {‘m‘,‘u‘,‘l‘,‘t‘,‘i‘,‘p‘,‘l‘,‘y‘,0}, 11 {‘d‘,‘i‘,‘v‘,‘i‘,‘d‘,‘e‘,0}, 12 {‘r‘,‘e‘,‘m‘,‘a‘,‘i‘,‘n‘,‘d‘,‘e‘,‘r‘,0} 13 }; 14 int fs[256]; 15 char s[11000]; int n; 16 char q[11000]; int p[11000],hd=0; 17 bool flg[11000]; 18 int nxt[11000]; 19 bool chck(char x){ return x==‘+‘||x==‘-‘||x==‘*‘||x==‘/‘||x==‘%‘||x==‘(‘||x==‘)‘;} 20 bool chck1(char x){ return x==‘+‘||x==‘-‘||!x;} 21 bool chck2(char x){ return x==‘*‘||x==‘/‘||x==‘%‘||!x;} 22 void ot(int x,int y){ 23 for(int i=x;i<=y;++i)if(s[i] && s[i]!=‘(‘ && s[i]!=‘)‘){ 24 if(!chck(s[i])) printf("%c",s[i]); 25 else{ 26 printf("."); 27 for(int j=0;fc[fs[(int)s[i]]][j];++j) printf("%c",fc[fs[(int)s[i]]][j]); 28 printf("("); ot(i+1,nxt[i]); printf(")"); 29 i=nxt[i]; 30 } 31 } 32 } 33 void prvs(){ 34 fs[‘+‘]=0,fs[‘-‘]=1,fs[‘*‘]=2,fs[‘/‘]=3,fs[‘%‘]=4; 35 hd=0; 36 for(int i=1;i<=n;++i) flg[i]=false; 37 s[0]=0,s[n+1]=0; 38 for(int i=1;i<=n;++i) nxt[i]=0; 39 } 40 int main(){ 41 //freopen("ddd.in","r",stdin); 42 while(scanf("%s",s+1)!=EOF){ 43 n=strlen(s+1); prvs(); 44 for(int i=1;i<=n;++i)if(chck(s[i])){ 45 if(s[i]==‘)‘){ 46 bool mk1=false,mk2=false; 47 for(;q[hd]!=‘(‘;--hd){ 48 if(q[hd]==‘+‘||q[hd]==‘-‘) mk1=true; 49 if(q[hd]==‘*‘||q[hd]==‘/‘||q[hd]==‘%‘) mk2=true; 50 } 51 if((chck2(s[i+1])||chck2(s[p[hd]-1])) && !mk1){ 52 if(!mk2) flg[i]=true,flg[p[hd]]=true; 53 if(s[p[hd]-1]!=‘/‘&&s[p[hd]-1]!=‘%‘) flg[i]=true,flg[p[hd]]=true; 54 } 55 if(s[i+1]==‘)‘ && s[p[hd]-1]==‘(‘) 56 flg[i]=true,flg[p[hd]]=true; 57 if(chck1(s[i+1]) && chck1(s[p[hd]-1])) 58 flg[i]=true,flg[p[hd]]=true; 59 nxt[p[hd]]=i; 60 --hd; 61 } 62 else q[++hd]=s[i]; p[hd]=i; 63 } 64 hd=0; 65 for(int i=1;i<=n;++i){ 66 //if(flg[i]) s[i]=0; 67 if(s[i] && chck(s[i])){ 68 if(s[i]==‘(‘) q[++hd]=s[i],p[hd]=i; 69 if(s[i]==‘)‘){ 70 for(;q[hd]!=‘(‘;--hd) nxt[p[hd]]=i-1; 71 --hd; 72 } 73 if(chck1(s[i])){ 74 for(;hd && q[hd]!=‘(‘;--hd) nxt[p[hd]]=i-1; 75 q[++hd]=s[i],p[hd]=i; 76 } 77 if(chck2(s[i])){ 78 for(;hd && q[hd]!=‘(‘ && !chck1(q[hd]);--hd) nxt[p[hd]]=i-1; 79 q[++hd]=s[i],p[hd]=i; 80 } 81 } 82 } 83 for(;hd;--hd) nxt[p[hd]]=n; 84 /*for(int i=1;i<=n;++i) cout<<i<<" "; 85 cout<<endl; 86 for(int i=1;i<=n;++i) cout<<s[i]<<" "; 87 cout<<endl; 88 for(int i=1;i<=n;++i) cout<<nxt[i]<<" "; 89 cout<<endl;*/ 90 ot(1,n); printf("\n"); 91 } 92 return 0; 93 } 94 95
B. Brute Force of Orz Pandas
题意：
给你一个输出n层汉诺塔最优解的详细步骤的程序
输入n和k，要求你输入当此程序输入为n时的第k行输入，如果k大于总行数则输出Orz
最开始的思路时数学/推公式/找规律解决，这样其实比较难搞
我们发现，直接运行给出的程序不可行是因为给出的程序会遍历每一种情况，而如果我们发现调用某个递归函数导致的输出大于当前查询的行数，完全可以跳过它
而对于每个递归的输出行数，可以由公式快速得到
那么类似在平衡树上查找第k大的方式
对于每一层，如果k小于第一个递归将输出的行数，那么进第一个递归，递归解决问题
如果等于第一个递归输出行数+1，说明找到我们的答案
如果大于第一个递归输出行数+1，就令k-=第一个递归输出行数+1，然后进第二个递归
对于n很大的情况，由于k不大，所有只有当函数中的size很小的时候才有可能涉及到中间的printf和第二个递归
那么可以预处理出最大的满足第一个递归输出行数>=所求行数的size，然后从这里开始递归即可
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 int rd(){int z=0,mk=1; char ch=getchar(); 8 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mk=-1; ch=getchar();} 9 while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘; ch=getchar();} 10 return z*mk; 11 } 12 const int oo=1000000007; 13 struct edg{int y,nxt,v;}e[41000]; int lk[210],ltp=1; 14 void ist(int x,int y,int v){ 15 e[++ltp]=(edg){y,lk[x],v}; lk[x]=ltp; 16 e[++ltp]=(edg){x,lk[y],0}; lk[y]=ltp; 17 } 18 int n,m,o,a[210]; int s,t; 19 int lvl[210]; 20 int q[210],hd=0; 21 int crt[210]; 22 bool gtlvl(){ 23 for(int i=s;i<=t;++i) lvl[i]=0; 24 lvl[(q[(hd=1)]=s)]=1; 25 for(int k=1;k<=hd;++k){ 26 crt[q[k]]=lk[q[k]]; 27 for(int i=lk[q[k]];i;i=e[i].nxt)if(e[i].v && !lvl[e[i].y]){ 28 lvl[e[i].y]=lvl[q[k]]+1; 29 q[++hd]=e[i].y; 30 } 31 } 32 return lvl[t]; 33 } 34 int mxflw(int x,int y){ 35 if(x==t) return y; 36 int bwl=0,flw=0; 37 for(int i=crt[x];i && bwl<y;i=e[i].nxt)if(lvl[e[i].y]==lvl[x]+1 && e[i].v) 38 if((flw=mxflw(e[i].y,min(e[i].v,y-bwl)))){ 39 e[i].v-=flw,e[i^1].v+=flw; 40 //cout<<e[i^1].y<<"->"<<e[i].y<<" "<<flw<<endl; 41 bwl+=flw; 42 if(!e[i].v) crt[x]=e[i].nxt; 43 } 44 if(!bwl) lvl[x]=0; 45 return bwl; 46 } 47 int dnc(){ 48 int bwl=0,flw=0; 49 while(gtlvl())while((flw=mxflw(s,oo))){ 50 bwl+=flw; 51 //printf("%d %d\n",bwl,flw); 52 } 53 return bwl; 54 } 55 void prvs(){ 56 ltp=1; 57 for(int i=0;i<=n+m+1;++i) lk[i]=0; 58 } 59 int main(){ 60 //freopen("ddd.in","r",stdin); 61 while(scanf("%d%d",&n,&m)!=EOF){ 62 prvs(); s=0,t=n+m+1; 63 int sm=0; 64 for(int i=1;i<=n;++i){ 65 a[i]=rd(); 66 sm+=a[i]; 67 ist(s,i,a[i]); 68 } 69 for(int i=n+1;i<=n+m;++i){ 70 a[i]=rd(); 71 sm+=a[i]; 72 ist(i,t,a[i]); 73 } 74 o=rd(); 75 int l,r; 76 while(o --> 0){ 77 l=rd(),r=rd(); 78 if(l>r) swap(l,r); 79 ist(l,r,oo); 80 } 81 printf("%d\n",sm-dnc()); 82 /*for(int i=s;i<=t;++i){ 83 cout<<i<<":"<<endl; 84 for(int j=lk[i];j;j=e[j].nxt) printf("%d %d\n",e[j].y,e[j].v); 85 }*/ 86 } 87 return 0; 88 } 89 90
原文：https://www.cnblogs.com/cdcq/p/11739066.html
