竞赛讨论区 > T2 这样为什么WA 50?

T2 这样为什么WA 50?

头像
星夜201907132011908
编辑于 2021-10-12 20:45:43 APP内打开
赞 0 | 收藏 0 | 回复1 | 浏览183
先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条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐