p1. 求一个$n$个节点的树，把几个点当做根提起来，能够变成二叉树。

$n \leq 100000$

# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <stdlib.h>

using namespace std;

int n, du[300010];
int ans[300010], an=0;

int main() {
	freopen("root.in", "r", stdin);
	freopen("root.out", "w", stdout);
	scanf("%d", &n);
	for (int i=1, u, v; i<n; ++i) {
		scanf("%d%d", &u, &v);
		du[u]++;
		du[v]++;
	} 
	for (int i=1; i<=n; ++i)
		if(du[i] < 3) ans[++an] = i;
	for (int i=1; i<=n; ++i) {
		if(du[i] >= 4) {
			puts("0");
			return 0;
		}
	}
	printf("%d\n", an);
	for (int i=1; i<an; ++i) printf("%d ", ans[i]);
	printf("%d\n", ans[an]);
	return 0;
}

p2.

$ n \leq 50, |S| \leq 50$

【题解】

好像只要随便哈希哈希下就行了？或者排序出来比较就行了。

# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <stdlib.h>

using namespace std;

int n;
char str[60][60];
bool del[60];
int len[60];
//int hash1[1400], hash2[1300], hash3[1300], hash4[1300];

struct two {
	char a, b;
} sx[66], sy[66];
int sxn, syn;

inline bool cmp(two x, two y) {
	return x.a < y.a || (x.a == y.a && x.b < y.b); 
}

inline void comp(int x, int y) {
//	puts("now checking");
//	puts(str[x]+1), puts(str[y]+1);
	sxn = syn = 0;
	int xlen = len[x], ylen = len[y];
	if(xlen != ylen) return;
	int tox, toy;
	if(xlen & 1) {
		if(str[x][xlen] != str[y][ylen]) return;
	}
	for (int i=1; i<=xlen/2; ++i)
		sx[++sxn].a = str[x][2*i-1], sx[sxn].b = str[x][2*i];
	for (int i=1; i<=ylen/2; ++i)
		sy[++syn].a = str[y][2*i-1], sy[syn].b = str[y][2*i];
	sort(sx+1, sx+sxn+1, cmp);
	sort(sy+1, sy+syn+1, cmp);
	for (int i=1; i<=sxn; ++i)
		if(sx[i].a != sy[i].a || sx[i].b != sy[i].b) return; 
	
//	puts("first ok");
//	puts(""); 
/*
	for (int i=1; i<=1337; ++i) hash1[i] = hash2[i] = hash3[i] = hash4[i] = 0;
	for (int i=1; i<=xlen/2; ++i) {
		hash1[(str[x][2*i-1] * 257 + str[x][2*i]) % 1337] ++;
		hash2[(str[x][2*i-1] * 88889 + str[x][2*i]) % 1019] ++;
		hash3[(str[x][2*i-1] + str[x][2*i] * 22223) % 1023] ++;
		hash4[(str[x][2*i-1] * 66667 + str[x][2*i]) % 1017] ++;
	}
	for (int i=1; i<=ylen/2; ++i) {
		int t1 = (str[y][2*i-1] * 257 + str[y][2*i]) % 1337,
		    t2 = (str[y][2*i-1] * 88889 + str[y][2*i]) % 1019,
			t3 = (str[y][2*i-1] + str[y][2*i] * 22223) % 1023,
			t4 = (str[y][2*i-1] * 66667 + str[y][2*i]) % 1017;
		hash1[t1] --;
		hash2[t2] --;
		hash3[t3] --;
		hash4[t4] --;
		if(hash1[t1] < 0 || hash2[t2] < 0 || hash3[t3] < 0 || hash4[t4] < 0) {
//			printf("=======WA ON TESTING %d\n", i);
			return;
		}
	}
//	puts(str[x]+1), puts(str[y]+1);
//	printf("same!\n");
//	puts("");
*/
	
	del[x] = del[y] = 1;
}

int main() {
	freopen("list.in", "r", stdin);
	freopen("list.out", "w", stdout);
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%s", str[i]);
		len[i] = strlen(str[i]);
		del[i] = 0;
	}
	for (int i=1; i<=n; ++i) {
		for (int j=len[i]; j>=1; --j)
			str[i][j] = str[i][j-1];
		str[i][0] = 0;
		for (int j=1; j<=len[i]/2; ++j)
			if(str[i][2*j-1] > str[i][2*j]) swap(str[i][2*j-1], str[i][2*j]);
//		puts(str[i]+1);
//		puts("");
	} 
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j) {
			if(del[i] || del[j] || i==j) continue;
			comp(i, j);
		}
	int undel = 0;
	for (int i=1; i<=n; ++i) if(!del[i]) undel ++;
	printf("%d\n", undel);
	return 0;
}

p3.  BZOJ2725