关于 bfs 的做法

考虑用

f_i

表示用

i

根木棍组成的最优数字中最后一位是什么，由于 bfs 可以保证深度从小到大（即数字从小到大），遍历顺序按照数字大小遍历，遍历过的不会再遍历，应该可以保证正确性且预处理复杂度

O(n)

。

每次使用

lst_i

记录上一个是什么，用一个栈把各个数位依次连接起来就是最终的答案。

不知道这种解法是否正确，如有错误请指出并 Hack。

CPP

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int M=1e5+5;
bitset<M>vis;	queue<int>q;
int T,n,x,f[M],lst[M];
inline void solve(int x,int pre,int num){
	if(vis[x])return;
	vis[x]=1,f[x]=num,lst[x]=pre,q.push(x);
}
signed main(){
	q.push(0);
	while(q.size()){
		int x=q.front();	q.pop();
		if(x&&x+6<M)solve(x+6,x,0);
		if(x+2<M)	solve(x+2,x,1);
		if(x+5<M)	solve(x+5,x,2);
		if(x+4<M)	solve(x+4,x,4);
		if(x+6<M)	solve(x+6,x,6);
		if(x+3<M)	solve(x+3,x,7);
		if(x+7<M)	solve(x+7,x,8);
	} scanf("%lld",&T);
	while(T--){
		scanf("%lld",&x);
		if(!vis[x])puts("-1");
		else {
			stack<int>s;
			while(x)s.push(f[x]),x=lst[x];
			while(s.size())
				printf("%lld",s.top()),s.pop();
			puts("");
		}
	} return 0;
}

通过了民间数据，最慢点 28ms，记录详情

讨论操作

回复

相关推荐

关于 bfs 的做法