暑假集训D3 2023.7.26 补题

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;
}

以后也应该注意到,这种数据范围非常小的应该优先考虑深搜.之前蓝桥杯飞机那道题也是类似的.