1>生日蛋糕
做一个蛋糕，规定体积为n(pai)，层数为n,
m,n,ri,hi均为整数
且每一层ri大于上一次rj，每一层高度hi大于hj
求最大的s表
先列方程：
V=n=∑ri*ri*hi
S=rm*rm +∑2*ri*hi
(1<=ri<=m)
可以看出，这里有明显的枚举，写dfs的特征，
枚举层数，记录上次的r,h,和直到上一层的s,v，
直到最后一层，与V比较，等则更新ans
但是n<=20000,
最大的r是132，最大的h是20000，
过大，枚举过程肯定要剪枝，
剪枝分为
1）可行性剪枝（减v）
2）最优性剪枝（减s）
a.加上估值函数mn_v,mn_s,
分别表示前i层，半径1-i枚举，高度1-i枚举的值，
这样就为搜索过程提供了一个：可行下界
以后的s和v不会过大，
（在dfs前递推预处理）
b.感觉这个剪枝不太给力，
那么我们就再加入一点，减去更多的枝
看看这个v,
似乎还可以设置一个可行上界？！
就是每次的ri*ri*hi*res +v <V
不过这个因为和ri和hi的具体值有关（ri，hi不确定），所以放在枚举中较好
那么再看看mn_s，似乎存在着一个问题：
mn_s和mn_v不太贴合，这个mn_s太理想
如果我们去贴合mn_v这个量，就要加大一层的r或h，那s与mn_s就差的多了，
最后就算与ans比较，成功更新的概率不高，
所以我们想啊想，想着再换一种思路求s的界限
看看式子：s是从侧面来的，
将s与V建立联系，就可以让s与ans更接近，不会出现中间突然的偏差，
发现：
vi=ri*ri*hi = ri*hi*2 (/2)(*ri) =si
则：resv=(n-v)
S<= s+resv/rm*2
所以完成：
#include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int n,m; int inf=99999999; int mn_s[20],mn_v[20]; int ans; int rd; void dfs(int pos,int s,int v,int mr,int mh) { if(pos==0) { if(v==n) ans=min(ans,s); return ; } if(!mh || !mr) return ; if(s+ mn_s[pos] >ans) return ; if(v+ mn_v[pos] >n) return ; if(s+ (n-v)/mr *2 >ans) return ; for(int i=mr;i;i--) { if(pos==m) s=i*i; int mx_h=min(mh, (n-v-mn_v[pos-1])/(i*i)); //printf("%d %d %d %d ",pos,s,v,mx_h); for(int j=mx_h;j>=pos;j--) dfs(pos-1,s+2*i*j,v+i*i*j,i-1,j-1); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)//枚举的是层数，表示每层的最小s,v mn_v[i]=mn_v[i-1] +i*i*i, mn_s[i]=mn_s[i-1] +i*i*2;//这里的mn_s不包括底面 ans=inf; dfs(m,0,0,sqrt(n),n); if(ans==inf) printf("0 "); else printf("%d ",ans); return 0; }
2>addition chain
一道不容易想，怎么剪枝的题
然后居然是迭代加深...
震惊，然后因为层数不多，我用的是优先队列去重，减少无用递归
#include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> using namespace std; int n,maxd; int d[10003],t[10003]; bool dfs(int pos) { if(pos>maxd) return false; int nw; priority_queue <int> q; for(int i=pos-1;i;i--) for(int j=i;j;j--) { nw=d[i]+d[j] ; if(pos<maxd ) { if((nw<<(maxd-pos))<n) break; //这里其实还可以多加一个可行性剪枝：计算之后可以到达的最大结果 if(nw<n && nw>d[pos-1]) q.push(nw);//注意这里还要求单调递增 } else if(nw==n) { for(int i=1;i<maxd;i++) printf("%d ",d[i]); printf("%d ",n); return true; } } bool ok=false; while(!q.empty() && !ok) { nw=q.top(); q.pop(); while(!q.empty() && q.top()==nw) q.pop(); d[pos]=nw; ok=dfs(pos+1); } return ok; } int main() { d[1]=1,d[2]=2; while(~scanf("%d",&n) && n ) if(n<4) { for(int i=1;i<=n;i++) printf("%d ",i); printf(" "); } else { for(maxd=3; ;maxd++)if(dfs(3)) break; } return 0; }
3>打开灯泡
好坑啊
vector在元素很少的时候，不要用，会超时
用优先队列，或者双端队列，都行
#include<cstdio> #include<cstdlib> #include<vector> #include<queue> #include<iostream> using namespace std; int n,m;char c; const int N=300003; int sz0[N],sz1[N]; int g0[N][5],g1[N][5]; int step[N]; bool vis[N]; deque <int> q; int main() { cin>>n>>m; if((n+m)%2) { cout<<"NO SOLUTION"; return 0; } int pa=1,pb=2,pc=pa+m+1,pd=pc+1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>c; if( c=='/' ) { g0[pb][sz0[pb]++]=pc,g0[pc][sz0[pc]++]=pb; g1[pa][sz1[pa]++]=pd,g1[pd][sz1[pd]++]=pa; } else { g1[pb][sz1[pb]++]=pc,g1[pc][sz1[pc]++]=pb; g0[pa][sz0[pa]++]=pd,g0[pd][sz0[pd]++]=pa; } pa++,pb++,pc++,pd++; } pa++,pb++; pc++,pd++; } int ed=(n+1)*(m+1); q.push_front(1); step[1]=1; while(!q.empty() ) { int t=q.front() ;q.pop_front() ; if(vis[t]) continue; vis[t]=true; if(t ==ed) { cout<<step[t]-1; return 0; } for(int i=0;i<sz0[t ];i++) { int v=g0[t ][i]; if(step[v] && step[v]<=step[t] ) continue; step[v]=step[t] ,q.push_front(v) ; if(v ==ed) { cout<<step[t]-1; return 0; } } for(int i=0;i<sz1[t ];i++) { int v=g1[t ][i]; if(step[v] && step[v]<=step[t] +1) continue; step[v]=step[t] +1,q.push_back(v) ; } } return 0; }
4>埃及分数
很烦的分数操作，用上了高精度中学的结构体操作，不错，但是爆了int
以后注意吧
#include<cstdio> #include<cstdlib> #define int long long using namespace std; int gcd(int a,int b) { if(!b) return a; else return gcd(b,a%b); }; struct fs { int a,b;// a/b void yuefen() { if(a>1) { int g=gcd(a,b); a/=g,b/=g; } } }; fs operator - (fs &a,fs &b) { fs c; c.a =a.a *b.b -b.a *a.b ; c.b =a.b *b.b ; c.yuefen() ; return c; } bool cmp (fs &a,fs &b) { fs c=a,d=b; c.b *=b.b ,c.a *=b.b ; d.b *=a.b ,d.a *=a.b ; return c.a <d.a ; } fs operator * (fs &a,int &b) { fs c=a; c.a *=b; c.yuefen() ; return c; } bool ok; int A,B,mx; int d[100000],ans[100000]; void dfs(fs nw,int dep,fs ll) { if(dep==mx) { if(nw.a ==1 && (nw.b <ans[mx] || !ans[mx] ) ) { ok=true; for(int i=1;i<mx;i++) ans[i]=d[i]; ans[mx]=nw.b ; } return ; } ll.b ++; int cnt=mx-dep+1; fs t=ll*cnt; while(cmp(nw,ll) || nw.b ==ll.b ) ll.b ++; while(cmp(nw ,t) ) { d[dep]=ll.b ; fs check=nw-ll; dfs(check,dep+1,ll); ll.b ++; t=ll*cnt; } } signed main() { scanf("%lld%lld",&A,&B); fs t,tt; tt.a =1,tt.b =1; t.a =A,t.b =B; t.yuefen() ; for(int i=3;;i++) { mx=i; dfs(t,1,tt); if(ok) { for(int j=1;j<=mx;j++) printf("%lld ",ans[j]); return 0; } } return 0; }
5>魔板
单点修改，单个数字，还是没有字符串好用
#include<cstdio> #include<cstdlib> #include<string> #include<map> #include<queue> #include<iostream> using namespace std; string ed; map <string ,int > step; struct node { string s,op; int stp; }st; queue <node> q; void A(node nw) { string t; for(int i=7;i>=0;i--) t+=nw.s[i] ; if(step[t]>0) return ; if(t==ed) { cout<<nw.stp <<endl; cout<<nw.op +'A'<<endl; exit(0); } node tt; step[t] = tt.stp =nw.stp +1; tt.s =t ,tt.op = nw.op +'A'; q.push(tt); } void B(node nw) { string t; t+=nw.s[3] ; for(int i=0;i<3;i++) t+=nw.s[i] ; for(int i=5;i<8;i++) t+=nw.s[i] ; t+=nw.s[4] ; if(step[t]>0) return ; if(t==ed) { cout<<nw.stp <<endl; cout<<nw.op +'B'<<endl; exit(0); } node tt; step[t] = tt.stp =nw.stp +1; tt.s =t ,tt.op = nw.op +'B'; q.push(tt); } void C(node nw) { string t=nw.s ; char c=t[1]; t[1]=t[6]; t[6]=t[5]; t[5]=t[2]; t[2]=c; if(step[t]>0) return ; if(t==ed) { cout<<nw.stp <<endl; cout<<nw.op +'C'<<endl; exit(0); } node tt; step[t] = tt.stp =nw.stp +1; tt.s =t ,tt.op = nw.op +'C'; q.push(tt); } int main () { int x; for(int i=0;i<8;i++) scanf("%d",&x),ed +=(char)('0'+x); for(int i=1;i<=8;i++) st.s +=(char)('0'+i); if(st.s ==ed) { printf("0 "); return 0; } st.stp =1; step[st.s ] =1; q.push(st); while(!q.empty() ) { node ttt=q.front(); q.pop() ; A(ttt); B(ttt); C(ttt); } return 0; }
6>knight moves
用了双端搜索，两个queue
940ms->240ms
#include<cstdio> #include<cstdlib> #include<queue> #include<cstring> using namespace std; int l,T; const int N=303; struct node { int x,y; node(int xx,int yy) { x=xx,y=yy; } node(){} }; queue <node> q1,q2; int sz1,sz2; int stp1[N][N],stp2[N][N]; int py[8][2]={{1,2},{2,1},{-1,2},{2,-1},{1,-2},{-2,1},{-1,-2},{-2,-1}}; bool ok; void bfs() { while(sz1>sz2) { node nw=q1.front() ; q1.pop() ,sz1--; for(int i=0;i<8;i++) { int nx=nw.x +py[i][0]; int ny=nw.y +py[i][1]; if(nx<0 || ny<0 || nx>=l || ny>=l || stp1[nx][ny] ) continue; if(stp2[nx][ny]) { printf("%d ",stp2[nx][ny]+stp1[nw.x ][nw.y ]-1); ok=true; return ; } stp1[nx][ny]=stp1[nw.x ][nw.y ]+1; q1.push(node(nx,ny)),sz1++; } } while(sz1<=sz2) { node nw=q2.front() ; q2.pop() ,sz2--; for(int i=0;i<8;i++) { int nx=nw.x +py[i][0]; int ny=nw.y +py[i][1]; if(nx<0 || ny<0 || nx>=l || ny>=l || stp2[nx][ny] ) continue; if(stp1[nx][ny]) { printf("%d ",stp1[nx][ny]+stp2[nw.x ][nw.y ]-1); ok=true; return ; } stp2[nx][ny]=stp2[nw.x ][nw.y ]+1; q2.push(node(nx,ny)),sz2++; } } } int main() { scanf("%d",&T); while(T--) { memset(stp1,0,sizeof(stp1)); memset(stp2,0,sizeof(stp2)); while(!q1.empty() ) q1.pop() ; while(!q2.empty() ) q2.pop() ; scanf("%d",&l); node t; scanf("%d%d",&t.x ,&t.y ); q1.push(t),stp1[t.x ][t.y ]++ ; scanf("%d%d",&t.x ,&t.y ); q2.push(t),stp2[t.x ][t.y ]=-1 ; sz1=sz2=1; if(stp1[t.x ][t.y ] ==1) { printf("0 "); continue; } ok=false; while((sz1 || sz2 )&& !ok) bfs(); } return 0; }
7>拯救大兵瑞恩
好坑的状态设计，不过还好一遍过了
#include<cstdio> #include<cstdlib> #include<bitset> #include<queue> using namespace std; int n,m,p; const int mx_state=(1<<10)+3,M=13; int py[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int wall[M][M][5],key[M][M]; int step[M][M][mx_state]; struct node { int x,y,state; node(int xx,int yy,int ss) {x=xx,y=yy,state=ss;} node(){} }; queue <node> q; int get_fx(int a,int b) { if(a==1 && !b) return 0; if(a==-1 &&!b) return 2; if(b==1 && !a) return 1; if(b==-1 &&!a) return 3; } void bfs() { step[1][1][0]=1; q.push(node(1,1,0)); while(!q.empty() ) { node nw=q.front();q.pop(); for(int i=0;i<4;i++) { if(wall[nw.x ][nw.y ][i]==-1 || (wall[nw.x ][nw.y ][i] & nw.state ) !=wall[nw.x ][nw.y ][i] ) continue; int nx=nw.x +py[i][0]; int ny=nw.y +py[i][1]; int st=nw.state | key[nx][ny]; if(!nx || !ny || nx>n || ny>m || step[nx][ny][st] ) continue; step[nx][ny][st] =step[nw.x ][nw.y ][nw.state ] +1; if(nx==n && ny==m ) { printf("%d ",step[nx][ny][st] -1); exit(0); } else q.push(node(nx,ny,st ) ); } } } int main() { scanf("%d%d%d",&n,&m,&p); int t,xi,yi,x2,y2,fx,ky; scanf("%d",&t); while(t--) { scanf("%d%d%d%d%d",&xi,&yi,&x2,&y2,&ky); fx=get_fx(x2-xi,y2-yi); if(!ky) wall[xi][yi][fx]=wall[x2][y2][(fx+2)%4]=-1; else wall[xi][yi][fx] |=(1<<ky), wall[x2][y2][(fx+2)%4] |=(1<<ky); } scanf("%d",&t); while(t--) { scanf("%d%d%d",&xi,&yi,&ky); key[xi][yi]|=(1<<ky); } bfs(); printf("-1 "); return 0; }
8>weight
一道很绕的搜索题
已知原数列 a1,a2,⋯,an 中的前 1项，前 2 项，前3项， ⋯⋯ ，前 n 项的和，
以及后 1 项，后 2 项，后 3 项， ⋯⋯ ，后 n 项的和，但是所有的数都被打乱了顺序。
此外，我们还知道数列中的数存在于集合 S 中。试求原数列。当存在多组可能的数列时，求字典序最小的数列。
直接枚举前n-1个和，求数列...
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,nn,sum; const int N=1003; int m,st[N]; int a[N<<1],d[N],pre_sum[N],bac_sum[N]; bool check(int nw,int p1,int p2) { for(int i=p1;i<n;i++) pre_sum[i]=pre_sum[i-1]+d[i]; for(int i=p2;i>0;i--) bac_sum[i]=bac_sum[i+1]+d[i]; while(p1<n && p2>0) { if(p1<n && pre_sum[p1]==a[nw]) p1++,nw++; else if(p2>0 && bac_sum[p2]==a[nw]) p2--,nw++; else return false; } return true; } void print() { for(int i=1;i<=n;i++) printf("%d ",d[i]); exit(0); } void dfs(int nw,int p1,int p2) { if(p1==p2) { d[p1]=sum-pre_sum[p1-1]-bac_sum[p2+1]; int pos=lower_bound(st+1,st+m+1,d[p1])-st; if(st[pos]!=d[p1]) return ; if(check(nw,p1,p2)) print(); return ; } d[p1]=a[nw]-pre_sum[p1-1]; pre_sum[p1]=a[nw]; int pos=lower_bound(st+1,st+m+1,d[p1])-st; if(st[pos]==d[p1]) dfs(nw+1,p1+1,p2); d[p2]=a[nw]-bac_sum[p2+1]; bac_sum[p2]=a[nw]; pos=lower_bound(st+1,st+m+1,d[p2])-st; if(st[pos]==d[p2]) dfs(nw+1,p1,p2-1); } int main() { scanf("%d",&n); nn=n<<1; for(int i=1;i<=nn;i++) scanf("%d",&a[i]); sort(a+1,a+nn+1); scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&st[i]); sort(st+1,st+m+1); sum=a[nn]; pre_sum[1]=d[1]=a[1]; dfs(2,2,n); return 0; }