太鼓达人

太鼓达人

题意

求一个长度为 \(2^n\) 的 \(01\) 序列，使得将其变为环后，\(2^n\) 个长度为 \(n\) 的段都不相同。

输出字典序最小的解。

思路

前 \(n\) 个必为 \(0\)，后 \(n\) 个必为 \(1\)。

先把已经出现过的字符串加入 set，然后枚举每一位。

如果该位填 \(0\) 不会重复，则填 \(0\)，否则填 \(1\)，使用 set 判断。

暴力验证发现正确。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
string ans = "";
string temp = "";
string tempp;
set <string> S;
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++) ans += "0";
	for (int i = 1; i <= n; i ++) temp += "0";
	for (int i = 1; i <= n; i ++) tempp += "1";
	S.insert(temp);
	for (int i = 1; i <= n; i ++) {
		S.insert(tempp);
		tempp.erase(tempp.begin());
		tempp += "0";
	}
	for (int i = n + 1; i <= (1 << n) - n; i ++) {
		temp.erase(temp.begin());
		tempp = temp + "0";
		if (S.find(tempp) == S.end()) {
			ans += "0";
			temp += "0";
			S.insert(tempp);
			continue;
		}
		tempp = temp + "1";
		S.insert(tempp);
		ans += "1", temp += "1";
	}
	for (int i = 1; i <= n; i ++) ans += "1";
	cout << (1 << n) << " " << ans << "\n"; 
}
signed main() {
	int Case = 1;
//	cin >> Case;
	while (Case --)
		solve();
	return 0;
}