lemonoil

OI__nothing is impossible

搜索专题

• 标签: 搜索

今天胡老说考搜索就是考暴力，没有分的就不用来了，结果最后。。。 我是唯一有分的，GG。 第三道题太难了，我就不写了。。。

魔法数字

这里写图片描述 （A.pas/.c/.cpp） 时间限制：1.0s，空间限制131072 KB 题目描述： 给一个六位数A 和另外一个六位数B. 你有一根魔法棒，初始时指向A 的最左边数字，每一次你可以选择下列操作 之一： 1.将当前魔杖指向的数字与最左端的一个数字调换位置。 2.将当前魔杖指向的数字与最右端的一个数字调换位置。 3.将当前魔杖指向的数字+1。(若当前魔杖指向的数字为9 则无效) 4.将当前魔杖指向的数字−1。(若当前魔杖指向的数字为0 则无效) 5.将当前魔杖向右移动一位。 6.将当前魔杖向左移动一位。 输入描述： 多组数据，处理到EOF 对于每组数据，包含两个6 位数A,B 输出描述： 对于每组数据，输出一行表示答案..

样例输入： 1 123456 654321 样例输出： 11

数据范围： 100%的数据保证：1 <= 数据组数 <= 200

题解

直接暴力搜索所有数字？不可行 只需要考虑这些数字在哪些位置是否出现过，6^6状态

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<cstring>
const int maxn=1000005;
const int HASH=1428571;
struct data{
	int k,v;
	bool a[6];
}q[maxn];
int vis[HASH+1],v[maxn],tennum[8]={1000000},sum[8],num[8],a,b,head,tail,LM;
bool judge(int u){
	int h=q[u].v%HASH,t=vis[h];
	while(t!=-1){
		if(q[u].v==q[t].v)return 0;
		t=v[t];
	}
	v[u]=vis[h],vis[h]=u;	
	return 1;
}
void FH(data u,int k){
	q[tail].k=u.k+1,q[tail++].a[k]=1;
}
void FS(int f,int k,int id,data u){
	if(f){
        q[tail]=u;
     	int t=num[k],v=0;num[k]=num[id],num[id]=t;
     	for(register int i=0;i<=6;++i)v+=num[i]*tennum[i];
   	    q[tail].v=v;
   	    if(judge(tail))FH(u,k);
  	   	num[id]=num[k],num[k]=t;
	}
}
void FT(int f,data p,int u){
	q[tail]=p;
	int v=LM+f;
	q[tail].v=v;
	if(judge(tail))FH(p,u+f);
}
int bfs(){
	head=0,tail=1;
	judge(head);
	while(head<tail){
		data p=q[head++];
		LM=p.v;
		for(register int i=6;i>=0;--i)num[i]=p.v%10,p.v/=10;
		int u=num[6],f;
		f=1;
		if((!num[u])||(!u))f=0;
		FS(f,0,u,p);
		f=1;
		if(((!num[5])&&(!u))||u==5)f=0;
		FS(f,5,u,p);
		if(u<5)FT(1,p,u);
		if(u) FT(-1,p,u);
	}
 	return tail;
}
int main(){
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	for(register int i=1;i<=6;++i)
		tennum[i]=tennum[i-1]/10;
	while(scanf("%d%d",&a,&b)!=EOF){
		memset(vis,-1,sizeof(vis));
		memset(q[0].a,0,sizeof(q[0].a));
		q[0].v=a*10,q[0].k=0,q[0].a[0]=1;
		for(register int i=5;i>=0;--i)sum[i]=b%10,b/=10;
		int res=bfs(),ans=999999;
		for(register int i=0;i<res;++i){
			q[i].v/=10;
			int num[6],rez=q[i].k;
			for(register int j=5;j>=0;--j){
				num[j]=q[i].v%10;
				q[i].v/=10;
			}
			for(register int k=0;k<6;++k)
				if(sum[k]!=num[k]&&!q[i].a[k]){
		  			rez=999999;break;
		  		}else rez+=((sum[k]-num[k])>0?(sum[k]-num[k]):-(sum[k]-num[k]));
			ans=ans>rez?rez:ans;
		}
		printf("%d\n",ans);
	}
	return 0;	
}

BitMask

（B.pas/.c/.cpp） 这里写图片描述 时间限制： 3.0s，空间限制 131072 KB 题目描述： 给出 2 x n的方格，每个方格初始都没有颜色，每次你可以选择其中一矩形区域，将其涂成某个颜色 C，现给出最终状态，请问少需要多步能到达 最终状态？ 输入描述： 输入第一行为一个整数T，表示数据组数 对于每组数据输入的第一行表示n( 1 <= n <= 8 )，接下来 2行，每个一长度n的字符串，保证字符串只包含大写字母 输出描述： 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 对于每组数据，输出一行表示答案 。 样例输入： 3 3 ABA CBC 3 BAA CCB 3 BBB BAB 样例输出： 3 3 2 数据范围： 50%的数据保证： 1 <= T <= 200且 n是随机产生的 是随机产生的 50%的数据保证： 1 <= T <= 25 且 n 为 8

题解

直接暴力BFS即可，每次抽取一个矩形进行位运算即可

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<cstring>
#define rep(i,x,y) for(register int i=x;i<y;++i)
#define CM(x,v) memset((x),v,sizeof(x))
char mp[3][10];
bool vis[27];
int t,n,m,head,tail,tot,u,v,dis[1<<17],Q[1<<19]; 
void bfs(int x){
    CM(dis,-1);
    head=tail=dis[x]=0;
    Q[tail++]=x;
    while(head!=tail){
        u=Q[head++];
        rep(F1,0,n)rep(F2,F1,n)rep(F3,0,2)rep(F4,F3,2){
            CM(vis,0),tot=0;
            rep(i,F3,F4+1)rep(j,F1,F2+1){
            	if(tot>1)break;
            	if((u&(1<<(i*n+j))))continue;
                if(!vis[mp[i][j]-'A'])++tot,vis[mp[i][j]-'A']=1;
            }
            if(tot==1){
                v=u;
                rep(i,F3,F4+1)rep(j,F1,F2+1)v|=1<<(i*n+j);
                if(dis[v]==-1){
                    dis[v]=dis[u]+1;
                    if(v==m)return;
                    if(dis[v]<(n<<1))Q[tail++]=v;
                }
            }
    	}
    }
}
template<class T>inline void readin(T &res){
	static char ch;T flag=1;
	while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
	while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;res*=flag;
}
inline void readst(char x[]){
	static char ch;int len=0;
	while((ch=getchar())<'A'||ch>'Z');x[len++]=ch;
	while((ch=getchar())>='A'&&ch<='Z')x[len++]=ch;
}
int main(){
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
    readin(t);
    while(t--){
        readin(n),readst(mp[0]),readst(mp[1]);
        m=(1<<(n<<1))-1,bfs(0);
        printf("%d\n",dis[m]);
    }
    return 0;
}

BruteForce

这里写图片描述 这里写图片描述 只有一组测试数据，保证 T<= 10且 n=12的数据不超过 2组， n=11的数据不的数据不的数据不超过2组

题解

首先暴力的求出环的方案数 之后暴力枚举环之后缩点用Matrix-Tree定理计算生成树即可

没有code

MARK一下MARIX—TREE

click it and link me

Launch CodeCogs Equation Editor