G. P6183 [USACO10MAR] The Rock Game S
题意:给定长度 n ,构造\(2^n\)个由X和O组成的字符串,使得第一个字符串和最后一个字符串只由O组成,并且相邻的字符串只有一处不同,不得有重复的字符串.
BFS貌似做不了.
看题解有佬用格雷码的知识.
代码如下
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define endl '\n'
using namespace std;
const int N = 1e5+10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
for(int i =0;i<pow(2,n);i++)
{
int num = 0;
for(int j = n-1;j>=0;j--)
{
num<<=1;
num|=((i>>(j))^(i>>(j+1)));
if(num&1)
{
cout<<'X';
}
else cout<<'O';
}
cout<<endl;
}
for(int i=0;i<n;i++)
{
cout<<"O";
}
return 0;
}
这题dfs当然也能做,不过当时做的时候T了
就没再往这方面想.
后面补题的时候发现应该是字符串比较的时候太费时间了.
我是用字符串来记录状态的,感觉时间应该差不多.
但是用二进制压缩一下状态可以大大加快比较的时间.
TLE代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define endl '\n'
using namespace std;
const int N = 1e5+10;
int n;
unordered_map<string,int> vis;
int m_step ;
string start ;
vector<string>res(32769);
int dfs(string s,int step)
{
//cout<<s<<endl;
if(step==m_step)
{
if(res[step-1]==start)
return 1;
else return 0;
}
string t = s;
for(int i =0;i<n;i++)
{
if(t[i]=='O')
{
t[i] = 'X';
}
else t[i]='O';
if(t==start&&step<m_step-1)
{
continue;
}
if(!vis[t])
{
vis[t] =1;
res[step] =t;
if(dfs(t,step+1))
{
return 1;
}
vis[t] =0;
}
if(t[i]=='O')
{
t[i] = 'X';
}
else t[i]='O';
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
m_step = pow(2,n);
string s ;
for(int i=0;i<n;i++)s+='O';
start =s;
if(dfs(s,0))
{
//cout<<"yes"<<endl;
}
cout<<start<<endl;
for(int i=0;i<m_step;i++)
{
cout<<res[i]<<endl;
}
return 0;
}
用二进制压缩以后完美通过代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
int n;
int vis[N];
int m_step ;
int res[N];
int print(int x)
{
for (int i = 0; i < n; i++)
{
if ((x >> (n - i - 1))&1)cout << "X";
else cout << "O";
}
cout << endl;
return 0;
}
int dfs(int st, int step)
{
//cout<<s<<endl;
//cout<<step<<":";
//print(st);
if (!st && step == m_step)
{
return 1;
}
for (int i = 0; i < n; i++)
{
int t = st;
t ^= (1 << i);
if (!vis[t])
{
vis[t] = 1;
res[step] = t;
if(t !=0||step==m_step-1)
{
if(dfs(t, step + 1))
{
return 1;
}
}
vis[t] = 0;
}
}
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
cin >> n;
m_step = pow(2, n);
if(!dfs(0, 0))
{
cout<<"error"<<endl;
}
for(int i=0;i<n;i++)
{
cout<<"O";
}
cout<<endl;
for(int i =0;i<m_step;i++)
{
print(res[i]);
}
return 0;
}
以后也应该注意到,这种数据范围非常小的应该优先考虑深搜.之前蓝桥杯飞机那道题也是类似的.