POJ3278&&1426&&3126&&3087&&3414

接上次的，标签是BFS专题

其实无论是Deepth还是Breadth都是Search

3278

又是撸过的题目

1426

找一个十进制数（我刚开始看样例以为是二进制数），使得它每一位上都是1或0，且是n的倍数（不包括0）

BFS表搜之后就打表即可

BFS CODE

#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_SIZE=105;
int n,len[MAX_SIZE<<1];
bool q[1048580][MAX_SIZE];
inline char tc(void)
{
	static char fl[100000],*A=fl,*B=fl;
	return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
	x=0; char ch=tc();
	while (ch<'0'||ch>'9') ch=tc();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline bool check(bool *bl,int len,int k)
{
	int res=0;
	for (register int i=1;i<=len;++i)
	res=(res*10+bl[i])%k;
	return !res;
}
inline void print(bool *bl,int len)
{
	for (register int i=1;i<=len;++i)
	putchar(bl[i]+'0');
	putchar('
');
}
inline void BFS(void)
{
	q[1][1]=1; len[1]=1;
	int head=0,tail=1;
	bool bl[MAX_SIZE];
	while (head<tail)
	{
		memcpy(bl,q[++head],sizeof(bl));
		if (check(bl,len[head],n)) { print(bl,len[head]); return; }
		memcpy(q[++tail],bl,sizeof(bl)); len[tail]=len[head]+1; q[tail][len[tail]]=0;
		memcpy(q[++tail],bl,sizeof(bl)); len[tail]=len[head]+1; q[tail][len[tail]]=1;
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	read(n);
	while (n)
	{
		BFS(); 
		read(n);
	}
	return 0;
}

打表 CODE

#include<string>
#include<iostream>
using namespace std;
const string ans[201]=
{
"",
"1",
"10",
"111",
"100",
"10",
"1110",
"1001",
"1000",
"111111111",
"10",
"11",
"11100",
"1001",
"10010",
"1110",
"10000",
"11101",
"1111111110",
"11001",
"100",
"10101",
"110",
"110101",
"111000",
"100",
"10010",
"1101111111",
"100100",
"1101101",
"1110",
"111011",
"100000",
"111111",
"111010",
"10010",
"11111111100",
"111",
"110010",
"10101",
"1000",
"11111",
"101010",
"1101101",
"1100",
"1111111110",
"1101010",
"10011",
"1110000",
"1100001",
"100",
"100011",
"100100",
"100011",
"11011111110",
"110",
"1001000",
"11001",
"11011010",
"11011111",
"11100",
"100101",
"1110110",
"1111011111",
"1000000",
"10010",
"1111110",
"1101011",
"1110100",
"10000101",
"10010",
"10011",
"111111111000",
"10001",
"1110",
"11100",
"1100100",
"1001",
"101010",
"10010011",
"10000",
"1111111101",
"111110",
"101011",
"1010100",
"111010",
"11011010",
"11010111",
"11000",
"11010101",
"1111111110",
"1001",
"11010100",
"10000011",
"100110",
"110010",
"11100000",
"11100001",
"11000010",
"111111111111111111",
"100",
"101",
"1000110",
"11100001",
"1001000",
"101010",
"1000110",
"100010011",
"110111111100",
"1001010111",
"110",
"111",
"10010000",
"1011011",
"110010",
"1101010",
"110110100",
"10101111111",
"110111110",
"100111011",
"111000",
"11011",
"1001010",
"10001100111",
"11101100",
"1000",
"11110111110",
"11010011",
"10000000",
"100100001",
"10010",
"101001",
"11111100",
"11101111",
"11010110",
"11011111110",
"11101000",
"10001",
"100001010",
"110110101",
"100100",
"10011",
"100110",
"1001",
"1111111110000",
"11011010",
"100010",
"1100001",
"11100",
"110111",
"11100",
"1110001",
"11001000",
"10111110111",
"10010",
"1110110",
"1010100",
"10101101011",
"100100110",
"100011",
"100000",
"11101111",
"11111111010",
"1010111",
"1111100",
"1111110",
"1010110",
"11111011",
"10101000",
"10111101",
"111010",
"1111011111",
"110110100",
"1011001101",
"110101110",
"100100",
"110000",
"100101111",
"110101010",
"11010111",
"11111111100",
"1001111",
"10010",
"100101",
"110101000",
"1110",
"100000110",
"1001011",
"1001100",
"1010111010111",
"110010",
"11101111",
"111000000",
"11001",
"111000010",
"101010",
"110000100",
"1101000101",
"1111111111111111110",
"111000011",
"1000"
};
int n;
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n;
	while (n)
	{
		cout<<ans[n]<<endl;
		cin>>n;
	}
	return 0;
}

3126

给出一个四位数，你每次可以替换其中一位上的数字，但是必须满足操作后的数是质数

埃氏筛（不会欧拉筛）之后BFS即可

CODE

#include<cstdio>
#include<cstring>
using namespace std;
const int N=10000;
bool prime[N],vis[N];
int n,a,b,q[N],step[N];
inline char tc(void)
{
	static char fl[100000],*A=fl,*B=fl;
	return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
	x=0; char ch=tc();
	while (ch<'0'||ch>'9') ch=tc();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(int x)
{
	if (x/10) write(x/10);
	putchar(x%10+'0');
}
inline void get_prime(void)
{
	for (register int i=2;i<N;++i)
	if (prime[i]) for (register int j=i<<1;j<N;j+=i) prime[j]=0;
}
inline int BFS(int a,int b)
{
	q[1]=a; step[a]=0; vis[a]=1;
	int head=0,tail=1;
	while (head<tail)
	{
		int now=q[++head];
		if (now==b) return step[head];
		for (register int radix=1;radix<=1000;radix*=10)
		for (register int i=0;i<=9;++i)
		{
			int t=((now/radix/10)*10+i)*radix+(now%radix);
			if (t>=1000&&t<=9999&&!vis[t]&&prime[t]) q[++tail]=t,vis[t]=1,step[tail]=step[head]+1;
		}
	}
	return -1;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	memset(prime,true,sizeof(prime));
	get_prime();
	read(n);
	while (n--)
	{
		read(a); read(b);
		memset(vis,0,sizeof(vis));
		int k=BFS(a,b);
		if (k!=-1) write(k),putchar('
'); else puts("Impossible");
	}
	return 0;
}

3087

这是模拟题吧

给你两个长度为c的字符串s1,s2，你每次可以进行洗牌，问几次操作后能使洗过的牌达到目标状态

要注意到，如果已经出现重复了，但是还没有到目标状态，那么就impossible了

map即可

CODE

#include<iostream>
#include<string>
#include<map>
using namespace std;
map <string,bool> hash;
string s1,s2,s,temp;
int n,c;
int main()
{
	register int i,j;
	std::ios::sync_with_stdio(false);
	for (cin>>n,i=1;i<=n;++i)
	{
		hash.clear();
		cin>>c; cin>>s1>>s2>>s;
		for (int cnt=1;;++cnt)
		{
			temp="";
			for (j=0;j<c;++j)
			temp+=s2[j],temp+=s1[j];
			if (temp==s) { cout<<i<<' '<<cnt<<endl; break; }
			if (hash[temp]) { cout<<i<<' '<<-1<<endl; break; }
			hash[temp]=1; s1.assign(temp,0,c); s2.assign(temp,c,c);
		}
	}
	return 0;
}

3414

给出两个水壶，最大容量为a，b。有以下操作：

  1. FILL(i) 加满i
  2. DROP(i) 把i里的水道光
  3. POUR(i,j) 把i水壶的水全部倒入j水壶中

因为就两个水壶，BFS即可

CODE

#include<iostream>
#include<string>
using namespace std;
const int N=105;
const string F1="FILL(1)",F2="FILL(2)",D1="DROP(1)",D2="DROP(2)",P1="POUR(1,2)",P2="POUR(2,1)";
bool vis[N*N+N];
int a,b,c,q[N*N][2],step[N*N],pre[N*N],rear;
string work[N*N];
inline int hash(int x,int y)
{
	return x*N+y;
}
inline int BFS(void)
{
	q[1][0]=q[1][1]=0; vis[0]=1; step[1]=0;
	int head=0,tail=1,h,x,y,xx,yy;
	while (head<tail)
	{
		x=q[++head][0],y=q[head][1];
		if (x==c||y==c) { rear=head; return step[head]; }
		h=hash(a,y);
		if (!vis[h]) q[++tail][0]=a,q[tail][1]=y,step[tail]=step[head]+1,vis[h]=1,work[tail]=F1,pre[tail]=head;
		h=hash(x,b);
		if (!vis[h]) q[++tail][0]=x,q[tail][1]=b,step[tail]=step[head]+1,vis[h]=1,work[tail]=F2,pre[tail]=head;
		h=hash(0,y);
		if (!vis[h]) q[++tail][0]=0,q[tail][1]=y,step[tail]=step[head]+1,vis[h]=1,work[tail]=D1,pre[tail]=head;
		h=hash(x,0);
		if (!vis[h]) q[++tail][0]=x,q[tail][1]=0,step[tail]=step[head]+1,vis[h]=1,work[tail]=D2,pre[tail]=head;
		yy=x+y>b?b:x+y,xx=x+y>b?x+y-b:0;
		h=hash(xx,yy);
		if (!vis[h]) q[++tail][0]=xx,q[tail][1]=yy,step[tail]=step[head]+1,vis[h]=1,work[tail]=P1,pre[tail]=head;
		xx=x+y>a?a:x+y,yy=x+y>a?x+y-a:0;
		h=hash(xx,yy);
		if (!vis[h]) q[++tail][0]=xx,q[tail][1]=yy,step[tail]=step[head]+1,vis[h]=1,work[tail]=P2,pre[tail]=head;
	}
	return -1;
}
inline void print(int now)
{
	if (pre[now]!=1) print(pre[now]);
	cout<<work[now]<<endl;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>a>>b>>c;
	int k=BFS();
	if (k!=-1) cout<<k<<endl,print(rear); else cout<<"impossible";
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cjjsb/p/8869854.html