Codeforces Round #580 (Div. 2) C. Almost Equal （找規律）

題目連結：https://codeforces.com/contest/1206/problem/C

反思：比賽時一直想畫圖找到規律。（明明就不會找規律） ， 本着做出題才是第一位的想法就應該打表的。

找規律代碼：可以用STL或者dfs生成全排列，這裡使用的dfs：

參數t是環的長度：2*n , 不過也隻是能跑出n = 5 時的情況：1 4 5 8 9 2 3 6 7 10

和題目中n = 3的情況：1 4 5 2 3 6 對比即可找到規律。還有就是n 為偶數時無解。似乎可以用反證法證明，水準可能不夠就不證了。。

找規律代碼：

void dfs(int t) {
	if(t == n) {
		int cnt = 0;
		bool flag = 0;
		int mmin = 99999999 , mmax = 0; 
		for(int i = 0 ; i < n ; i++) {
			int tmp = 0;
			for(int j = 0 ; j < n/2 ; j++) {
				tmp += a[(i+j)%n];
			}
			if(!cnt)cnt = tmp;
			mmin = min(tmp,mmin); mmax = max(tmp,mmax);
			if(abs(mmax - mmin) > 1) {
				flag = 1;
				break;
			}
		}
		if(!flag) {
			ext = 1;
			return;
		}
	}
	
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			vis[i] = 1;
			a[t] = i;
			dfs(t+1);
			if(ext)return;
			vis[i] = 0;
		}
	}
}
           

題目的代碼：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int main() {
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	if(n % 2 == 0)cout << "NO\n";
	else {
		cout << "YES\n";
		for(int i = 1 ; i <= n ; i++) {
			if(i > 1) cout << " ";
			if(i % 2)cout << 2 * i - 1;
			else cout << 2 * i;
		}
		for(int i = 1 ; i <= n ; i++) {
			cout << " ";
			if(i % 2)cout << 2 * i;
			else cout << 2 * i - 1;
		}
	}
	return 0;
}