好久没写过题解了,最近都在切水题,没什么可写,今天这题感觉一定要写写,刚开始一直思考路径无果,后来想到路径可以用字符串转移,这个击破后就以为一番风顺了,然而死在了取模那里,负数取模,应该变成正数,这样wa了几次,曾一度怀疑是我空间爆了,事实证明不是,虽然是4^n,显然最大是k*m全部访问,显然字符长度和那个n是一致的,4^n<=k*m显然n很小,也就是空间不会爆,开始没想到这点,我还被队友骂了,说我太暴力了。。。最近是太暴力了,开了个1E的数组水了一题。。。
这题主要就是取模,bfs,还有路径处理。
Run ID | Submit Time | Judge Status | Pro.ID | Exe.Time | Exe.Memory | Code Len. | Language | Author |
5095163 | 2011-12-01 23:23:05 | Accepted | 1104 | 78MS | 424K | 1700 B | C++ | xym2010 |
代码
#include<cstdio> #include<string> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<map> #include<algorithm> #define For(i,a,n) for(int i=a;i<n;i++) #define rep(i,n) For(i,0,n) using namespace std; int n,m,k,fina; char ch[4]={'+','-','*','%'}; struct node { int num,step; string road; }ans; int deal(int x,int key) { if(key==0) return x+m; else if(key==1) return x-m; else if(key==2) return x*m; else { int tem=x%m; if(tem<0) tem=tem+m; return tem; } } void bfs() { int tem; map < int,int > mp; mp[n]=1; queue< node >q; node in,out; in.num=n,in.step=0,in.road=""; q.push(in); while(!q.empty()) { out=q.front();q.pop(); rep(i,4) { tem=deal(out.num,i)%(k*m); if(mp[tem]==0) { in.num=tem,in.step=out.step+1,in.road=out.road+ch[i]; mp[tem]=1; int x=tem%k; if(x<0) x=x+k; if(x==fina) { ans=in; return ; } else q.push(in); } } } } int main() { while(1) { scanf("%d%d%d",&n,&k,&m); if(n==m&&m==k&&k==0)return 0; fina=(n+1)%k; if(fina<0) fina+=k; ans.step=0; bfs(); printf("%d\n",ans.step); if(ans.step) cout<<ans.road<<endl; } return 0; }