生活总是充满杯具的……

一开始就想到了位运算，由于一下子没转过弯，

绕了一个大圈子，最后才回到位运算……

超时代码1

1.6s

ifstream fin ("checker.in");
ofstream fout ("checker.out");

//ifstream fin("G:\\OwnCode\\c++\\acm\\in.txt");
//ofstream fout(stdout);

int			n, res, t[15], num[15];

inline bool isok(int row, int s) {
	int k = 1;
	while ( row-- ) {
		if ( t[row] == s || (t[row] >> k) == s || (t[row] << k) == s ) return false;
		++k;
	}
	return true;
}

inline int play(int k) {
	int res = -1;
	while ( k ) {
		++res;
		k >>= 1;
	}
	return res;
}

void dfs(int row) {
	int i;
//	fout << row << endl;
	if ( row == n ) {
		if ( res++ < 3 ) {
			for(i = 0; i < n-1; ++i) fout << play(t[i]) << ' ';
			fout << play(t[i]) << endl;
		}
	}
	for(i = 0; i < n; ++i ) {
		if ( isok(row, num[i]) ) {
			t[row] = num[i];
			dfs(row+1);
		}
	}
}

int main() {
	fin >> n;
	res = 0;
	for(int i = 0; i < 15; ++i) num[i] = 1<<(i+1);
	dfs(0);
	fout << res << endl;
	return 0;
}

超时代码2

1.288s

ifstream fin ("checker.in");
ofstream fout ("checker.out");

//ifstream fin("G:\\OwnCode\\c++\\acm\\in.txt");
//ofstream fout(stdout);

int			n, res, t[15], map[15][15], maps[15][15];
bool		mark[31], flag[31], smark[31];

void dfs(int row) {
//	fout << row << endl;
	int i;
	if ( row == n ) {
		if ( res++ < 3 ) {
			for(i = 0; i < n-1; ++i) fout << t[i]+1 << ' ';
			fout << t[i]+1 << endl;
		}
		return;
	}
	for(i = 0; i < n; ++i ) {
		if ( !mark[i] && !flag[map[row][i]] && !smark[maps[row][i]] ) {
			flag[map[row][i]] = true;
			smark[maps[row][i]] = true;
			mark[i] = true;
			t[row] = i;
			dfs(row+1);
			flag[map[row][i]] = false;
			smark[maps[row][i]] = false;
			mark[i] = false;
		}
	}
}

int main() {
	fin >> n;
	res = 0;
	for(int i = 0; i < 15; ++i){
//		num[i] = 1<<(i+1);
		for(int j = 0; j < 15; ++j) {
			map[i][j] = i > j ? i-j : j-i+15;
			maps[i][j] = i+j;
		}
	}
//	if ( n < 14 ) 
		dfs(0);
	/*
	else {
		for ( int i = 0; i < (n/3); ++i ) {
			t[0] = num[i];
			dfs(1);
		}
		res *= 4;
	}
	*/
	fout << res << endl;
	return 0;
}

超时代码3

1.048s

ifstream fin ("checker.in");
ofstream fout ("checker.out");

//ifstream fin("G:\\OwnCode\\c++\\acm\\in.txt");
//ofstream fout(stdout);

int			n, res, t[15], num[15];

void dfs(int row, int h, int l, int r) {
	int i;
	if ( row == n ) {
		if ( res++ < 3 ) {
			for(i = 0; i < n-1; ++i) fout << t[i]+1 << ' ';
			fout << t[i]+1 << endl;
		}
		return;
	}
	for(i = 0; i < n; ++i ) {
		if ( !(num[i]&h) && !(num[i]&l) && !(num[i]&r) ) {
			t[row] = i;
			dfs(row+1, num[i]|h, (num[i]|l)>>1, (num[i]|r)<<1);
		}
	}
}

int main() {
	fin >> n;
	res = 0;
	for(int i = 0; i < 15; ++i){
		num[i] = 1<<i;
	}
	dfs(0, 0, 0, 0);
	fout << res << endl;
	return 0;
}

最后修改的一句。。。。。

0.540s

ifstream fin ("checker.in");
ofstream fout ("checker.out");

//ifstream fin("G:\\OwnCode\\c++\\acm\\in.txt");
//ofstream fout(stdout);

int			i, n, res, t[15], num[15];

void dfs(int row, int h, int l, int r) {
	int i;
	if ( row == n ) {
		if ( res++ < 3 ) {
			for(i = 0; i < n-1; ++i) fout << t[i]+1 << ' ';
			fout << t[i]+1 << endl;
		}
		return;
	}
	for(i = 0; i < n; ++i ) {
		if ( !(num[i]&(h|l|r)) ) {//这句改了时间居然节约一半……蛋疼
			t[row] = i;
			dfs(row+1, num[i]|h, (num[i]|l)>>1, (num[i]|r)<<1);
		}
	}
}

int main() {
	fin >> n;
	res = 0;
	for(int i = 0; i < 15; ++i){
		num[i] = 1<<i;
	}
	dfs(0, 0, 0, 0);
//	for(int i = 0; i < 15; ++i) dfs(1, num[i]|0, (num[i]|0)>>1, (num[i]|0)<<1);
	fout << res << endl;
	return 0;
}