先bfs预处理出1号点通过三种操作不经过[-1e7,1e7]以外的点能到达的所有点的集合S,并记录集合内每个点的pre
每次询问先处理x直到x∈S,再不断找pre直到x=1
处理方法:如果x%2==0,x/=2,否则x=3*x+1;
#include<cstdio> using namespace std; typedef long long LL; const int N=1e7; int pr[N*2+5],Q[N*2+5],h,t,q,d,l; LL out[1505]; bool vs[N*2+5]; inline LL Z(LL x) {return x<0?-x:x;} void push(int v,int x) { if(Z(v)<=N) if(!vs[v+N]) Q[++t]=v,pr[v+N]=x,vs[v+N]=1; } int main() { scanf("%d%d%d",&q,&d,&l); Q[h=t=1]=vs[1+N]=1; while(h<=t) { int x=Q[h++];push(x*2,x); if(Z(x)<=l&&Z(x-d)<=l) push(x-d,x); if((x%3+3)%3==1) push((x-1)/3,x); } while(q--) { LL x;scanf("%lld",&x);t=0; while(Z(x)>N||!vs[x+N]) { out[++t]=x; if(x%2==0) x/=2; else x=x*3+1; } while(1) { out[++t]=x; if(x==1) break; x=pr[x+N]; }printf("%d",t-1); while(t--) printf(" %d",out[t+1]); puts(""); }return 0; }
全部评论
(1) 回帖