1. 字符串复原

【题目大意】

给出n个长度为3的字符串，它们都是一个字串S的长度为3的连续字串，而且字串不包含除了这n个字符串以外的，长度为3的连续子串。求出字串S。

【题解】
hash+离散+欧拉路

# include <stdio.h>
using namespace std;

int n, T, rn;
char st[3];

int head[666666], next[666666], to[666666], tot=0, in[666666], out[666666], hd1[666666];
int s[666666], sn=0, ls[666666];
bool used[666666];
int fc[666666], top, ans[666666], gg[666666], gn=0;
int fa[666666];

// ============UNIONSET============== //
inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
// ============UNIONSET============== //

// ============HASH============= //
inline int hash(char a, char b) {
	return a * 256 + b;
}
char UNHASHa, UNHASHb;
inline void unhash(int s) {
	UNHASHb = s % 256;
	UNHASHa = (s - UNHASHb)/256;
}
// ============HASH============= //

inline void add(int a, int b) {
	++tot;
	next[tot] = head[a];
	head[a] = tot;
	to[tot] = b;
	out[a] ++;
	in[b] ++;
	used[tot] = 0;
}

// ===========FLEURY============= //
inline void dfs(int x) {
	ans[++top] = x;
	for (int i=hd1[x]; i; i=next[i]) {
		if(!used[i]) {
			used[i] = 1;
			out[x] --;
			in[to[i]] --;
			hd1[x] = i;
			dfs(to[i]);
			break;
		}
	}
}

inline void fleury(int s) {
	top = 1;
	ans[top] = s;
	while(top > 0) {
		int can = 0;
		if(out[ans[top]] >= 1) can = 1;
		if(can == 0) {
			gg[++gn] = ans[top];
			--top;
		} else {
			--top;
			dfs(ans[top+1]);
		}
	}
}
// ===========FLEURY============= //

int main() {
	freopen("recover.in", "r", stdin);
	freopen("recover.out", "w", stdout);
	scanf("%d", &T);
	for (int I=1; I<=T; ++I) {
		tot=0; sn=0; gn=0;
		scanf("%d", &n);
		for (int i=1; i<=n+66; ++i) 
			head[i] = in[i] = out[i] = 0, fa[i] = i;
		for (int i=1; i<=n; ++i) {
			scanf("%s", st);
			int front = hash(st[0], st[1]), back = hash(st[1], st[2]);
//			printf("%d %d\n", front, back);	
			if(fc[front] != I) {
				fc[front] = I;
				s[++sn] = front;
				ls[front] = sn;
//				printf("***new front\n");
			}
			if(fc[back] != I) {
				fc[back] = I;
				s[++sn] = back;
				ls[back] = sn;
//				printf("***new back\n");
			}
			front = ls[front]; back = ls[back];
			add(front, back);
			int fu = getf(front), fv = getf(back);
			fa[fu] = fv;
//			printf("edge: %d %d  bh=%d\n", front, back, tot);
		}
//		for (int i=1; i<=sn; ++i) 
//			printf("number = %d, in = %d, out = %d\n", i, in[i], out[i]);
		int start=-1, end=-1;
		bool no=0;
		for (int i=1; i<=sn; ++i) {
			hd1[i] = head[i];
			if(in[i] - out[i] == 1) {
				if(end==-1) end=i;
				else {
					no=1;
					break;
				}
			} else if(in[i] - out[i] == -1) {
				if(start==-1) start=i;
				else {
					no=1;
					break;
				}
			} else if(in[i] != out[i]) {
				no = 1;
				break;
			}
		}
		for (int i=1; i<n; ++i) {
			if(getf(i) != getf(i+1)) {
				no = 1;
				break;
			}
		}
		if(no) {
			puts("NO");
			continue;
		}
//		printf("start = %d, end = %d\n", start, end);
		if(start == -1 && end == -1) 
			start = 1, end = 1;
		puts("YES");
		gg[++gn] = start;
		fleury(start);
		for (int i=gn; i>=3; --i) {
			gg[i] = s[gg[i]];
			unhash(gg[i]);
			printf("%c", UNHASHa);
		}
		gg[2] = s[gg[2]];
		unhash(gg[2]);
		printf("%c%c", UNHASHa, UNHASHb);
		printf("\n");
	}
	return 0;
}

2. 好排列

【题目大意】

给出一个排列的大小关系（大于，小于），求排列方案数量

【题解】

f[i, j] 1...i的排列最后一个是j的满足要求的方案数量

随便转移一下前缀和搞搞

# include <stdio.h>
# include <algorithm>
# include <string.h>
using namespace std;
int T, n, m;
long long f[2020][2020];
int s[2020];
bool t[2020];
const int MOD = 1e9+7;
int main() {
	freopen("good.in", "r", stdin);
	freopen("good.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		memset(f, 0, sizeof(f));
		memset(t, 0, sizeof(t));
		scanf("%d %d", &n, &m);
		for (int i=1; i<=m; ++i) {
			scanf("%d", &s[i]);
			t[s[i]+1] = 1;
		}
		f[1][1] = 1;
		for (int i=2; i<=n; ++i) {
			if(t[i] == 1) {
				long long sum = 0;
				for (int j=1; j<=i; ++j) {
					f[i][j] = sum;
					sum = (sum + f[i-1][j]) % MOD;
				}
			} else {
				long long sum = 0;
				for (int j=i; j>=1; --j) {
					sum = (sum + f[i-1][j]) % MOD;
					f[i][j] = sum;
				}
			}
		}
		long long ans = 0;
		for (int i=1; i<=n; ++i) ans = (ans + f[n][i]) % MOD;
		printf("%lld\n", ans);
	}
	return 0;
}
		
	

3. 黑帮

【题目大意】同codeforces 690A1,A2

【题解】

随便考虑一下就行啦，见codeforces 690A 题解

# include <stdio.h>
using namespace std;

int T;
int n, S;

int main() {
	freopen("distribute.in", "r", stdin);
	freopen("distribute.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &S);
		if(S==1) {
			printf("%d\n", (n+1)/2);
			continue;
		} else {
			if(n&1) 
				printf("%d\n", (n-1)/2);
			else {
				int s = 1;
				if(n <= 2)
					printf("%d\n", (n-1)/2);
				else {
					for (int i=1; i<=30; ++i) {
						s = s * 2;
						if((long long)s*2 > n) {
							printf("%d\n", (n-s)/2);
							break;
						}
					}
				}
			}
		}
	}
	return 0;
}