3526211_ce.cc

北大大牛代码 1240道题的原代码 超级权威

#include <string>
#include <algorithm>

using namespace std;

char str[5000];
string table = "NOP";
bool done = false;

string getString(int st, int ed) {

	string ret = "";

	for (int i = st; i < ed; i++) {
		ret += str[i];
	}

	return ret;
}

bool can(int p) {
	for (int i = p; ; i--) {
		if (i * 2 < p + 1) {
			break;
		}
		int pa, pb;
		pa = p;
		pb = i - 1;
		while (pa >= i && str[pa] == str[pb]) {
			pa--;
			pb--;
		}
		if (pa < i) {
			return false;
		}
	}
	return true;
}

void dfs(int p) {
	if (p == 5000) {
		done = true;
		return ;
	}
	for (int i = 0; !done && i < 3; i++) {
		char ch = table.at(i);
		if (ch == str[p - 1]) {
			continue;
		}
		str[p] = ch;
		if (can(p)) {
			dfs(p + 1);
		}
	}
}

void run() {
	str[0] = 'N';
	dfs(1);
}

void go() {
	int n;

	while (scanf("%d", &n) == 1 && n != 0) {
		for (int i = 0; i < n; i++) {
			putchar(str[i]);
		}
		putchar('\n');
	}
}

void main() {
	run();
	go();
}