牛客小白月赛22

链接：https://ac.nowcoder.com/acm/contest/4462/C
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

一列上有12个孔，这12个孔中有些孔被遮挡住了。

假定我们用 '-' 来表示没被遮挡住的孔，用 'o' 来表示被遮挡住的孔。

如果相邻的三个孔有两个孔被遮挡，并且被遮挡的两个孔相邻，就是 '-oo' 和 'oo-'。

对于这样的三个孔，我们可以将中间的孔的遮挡物移开，代价是将一端的遮挡物移到另一端没有被遮挡的孔上面。

对于一列给定的孔，你的任务是制定操作的顺序，使得最后剩余的被遮挡的孔的个数最少,并输出最后剩余的被遮挡的孔的个数。

输入描述:

第一行输入一个

接下来n行，每行12个字符，代表孔的状态。

输出描述:

对于每行输入在一行中输出一个数字代表答案。

输入

5
---oo-------
-o--o-oo----
-o----ooo---
oooooooooooo
oooooooooo-o

输出

DFS即可，可以将这个字符串看作是一个二进制串，把所有的情况先处理一下，然后对应询问直接输出即可。

https://pasteme.cn/28187

直接按题意DFS，感觉也能写

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 const int INF=0x3f3f3f3f;
 4 const double eps =1e-8;
 5 const int mod=1e9+7;
 6 const int maxn=1e5+10;
 7 using namespace std;
 8 
 9 string str;
10 int ans;
11 
12 int DFS()
13 {
14     for(int i=0;i<10;i++)
15     {
16         if(str[i]=='-'&&str[i+1]=='o'&&str[i+2]=='o')
17         {
18             str[i]='o'; str[i+1]='-'; str[i+2]='-';
19             DFS();
20             str[i]='-'; str[i+1]='o'; str[i+2]='o';
21         }
22         if(str[i]=='o'&&str[i+1]=='o'&&str[i+2]=='-')
23         {
24             str[i]='-'; str[i+1]='-'; str[i+2]='o';
25             DFS();
26             str[i]='o'; str[i+1]='o'; str[i+2]='-';
27         }
28     }
29     int num=0;
30     for(int i=0;i<12;i++)
31     {
32         if(str[i]=='o') num++;
33     }
34     ans=min(ans,num);
35 }
36 
37 int main()
38 {
39     #ifdef DEBUG
40     freopen("sample.txt","r",stdin);
41     #endif
42     
43     int T;
44     cin>>T;
45     while(T--)
46     {
47         ans=INF;
48         cin>>str;
49         DFS();
50         cout<<ans<<'
';
51     }
52     
53     return 0;
54 }

状态压缩

原牛客题解：https://ac.nowcoder.com/acm/problem/blogs/202476

一共12个孔，只有2^12=4096种情况，但是查询次数很多，我们可以考虑用二进制1和0表示‘o’和‘-’两种状态，进行状态压缩，用一个二进制数代表一种情况。然后再在记忆化搜索的过程中把已知情况的答案记录下来，方便下次直接用。

搜索的时候就找 '-oo' 和 'oo-'，注意到它们有共同点：中间是1，两边不相同。“将中间的孔的遮挡物移开，将一端的遮挡物移到另一端没有被遮挡的孔上面。”其实就是把中间的1变为0，再把两边互换，对于二进制数011和110，我们只要将它^111即异或7（1和0异或上0不变，异或1则可互换）

附：运算符优先级

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 const int INF=0x3f3f3f3f;
 4 const double eps =1e-8;
 5 const int mod=1e9+7;
 6 const int maxn=1e5+10;
 7 using namespace std;
 8 
 9 int vis[1<<12]; //记忆化数组
10 
11 int DFS(int x)
12 {
13     if(vis[x] || x==0) return vis[x]; //如果这种状态已经搜过了直接返回答案
14     int num=0; //状态中1的个数
15     for(int i=0;i<12;i++)
16         if(x>>i&1) num++;
17     for(int i=0;i<10;i++) //枚举'-oo' 和 'oo-'的右端
18     {
19         if(x>>(i+1)&1  &&  x>>i&1 ^ x>>(i+2)&1) //如果中间是1，两边不相同（异或为1）。注意运算符优先级，这里由高到低分别是()、+、>>、&、^
20             num=min(num,DFS(x^7<<i)); //进行操作继续搜索
21     }
22     return vis[x]=num; //记忆化
23 }
24 
25 int main()
26 {
27     #ifdef DEBUG
28     freopen("sample.txt","r",stdin);
29     #endif
30     
31     int T;
32     scanf("%d",&T);
33     while(T--)
34     {
35         int x=0; vis[0]=0;
36         char str[15];
37         scanf("%s",str);
38         for(int i=0;i<12;i++)
39             x=(x<<1)+(str[i]=='o'? 1:0); //将状态压缩进二进制数x
40         printf("%d
",DFS(x));
41     }
42     
43     return 0;
44 }