Zimpha的比赛看上去很excited？（雾）

前面A题hack了14发全成功了，final test后排第19，excited。

今天起来一看掉到90多了发现A题不算hack。。无言以对，而且竟然rated了，好在rating涨了。

A. GCD is Funny

黑板上有$n$个数$a_1, a_2, ..., a_n$，你有一种操作：取三个数擦除，选择其中两个数取gcd，把gcd在黑板上写两遍。很明显$n-2$轮后会有两个一样的数，求可能的数的集合。

$n \leq 500, a_i \leq 1000, T \leq 100$

【题解】就是元素个数在$[2, n-2]$范围内的gcd都可行。用一些特别的技巧（类似拓扑dp？）

复杂度$O(Tn|a_i|)$

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

using namespace std;

int T, n, a[510], amx;
int f[1010], g[1010], gn;
inline int gcd(int u, int v) {
	return v == 0 ? u : gcd(v, u%v);
}

int main() {
	scanf("%d", &T);
	for (int cas=1; cas<=T; ++cas) {
		scanf("%d", &n);
		amx = -1;
		for (int i=1; i<=n; ++i) {
			scanf("%d", &a[i]);
			amx = max(amx, a[i]);
		}
		gn = 0;
		for (int i=1; i<=1000; ++i)
			f[i] = g[i] = 0;
		int GCD = a[1];
		for (int i=1; i<=n; ++i) {
			GCD = gcd(GCD, a[i]);
			for (int j=gn; j>=1; --j) {
				int tmp = gcd(g[j], a[i]);
				if (! f[tmp]) 
					g[++gn] = tmp;
				f[tmp] += f[g[j]];
			}
			if(!f[a[i]]) g[++gn] = a[i];
			f[a[i]] ++;
		}
		for (int i=1; i<=n; ++i) f[a[i]] --;
		f[GCD] --;
		bool first = 1;
		for (int i=1; i<=1000; ++i) {
			if(f[i]) {
				if(first) {
					printf("%d", i);
					first = 0;
				} else printf(" %d", i);
			}
		}
		puts("");
	}
	return 0;	
}

B. Square Distance

求一个字符串，使得它的前半部分能完全匹配它的后半部分，且与题目给的字符串的不匹配位置数等于$m$

$|S| \leq 1000, m \leq |S|$

DP一半，因为要字典序最小，所以倒着dp，之后贪心填数字即可。

# include <stdio.h>
# include <string.h> 
// # include <bits/stdc++.h>

using namespace std;

int n, m;
char s[1010];
bool f[1010][1010];
char t[1010]; 
// f[i, j]  到i位置，失配j位是否可行。 


int main() {
	int T; scanf("%d", &T);
	while(T--) {
		memset(f, 0, sizeof(f)); 
		scanf("%d%d", &n, &m);
		scanf("%s", s+1);
		int diff = 0;
		for (int i=1; i<=n/2; ++i) {
			if(s[i] != s[i+n/2]) ++diff;
		}
		if(diff>m) {
			puts("Impossible");
			continue;
		}
		f[n/2+1][0]=1; 
		for (int i=n/2; i>=1; --i)
			if(s[i] == s[i+n/2]) {
				for (int j=0; j<=m; ++j) {
					f[i][j] |= f[i+1][j];
					if(j>=2) f[i][j] |= f[i+1][j-2];
				}
			} else {
				for (int j=1; j<=m; ++j) {
					f[i][j] |= f[i+1][j-1];
					if(j>=2) f[i][j] |= f[i+1][j-2];
				}
			}
		if(f[1][m] == 0) {
			puts("Impossible");
			continue;
		}
		int cursp = 0;
		for (int i=1; i<=n/2; ++i)
			for (int j='a'; j<='z'; ++j) {
				int curj = cursp;
				if(j != s[i] || j != s[i+n/2]) ++ curj;
				if(j != s[i] && j != s[i+n/2]) ++ curj;
				if(m - curj < 0) continue; 
				if(f[i+1][m - curj]) {
					 t[i] = j; t[i+n/2] = j; 
					 j = 'z'+1;
					 cursp = curj;
				}
			}
		for (int i=1; i<=n; ++i) printf("%c", t[i]);
		puts("");		  
	}
	return 0;
}

C. LCIS

求LCIS，要求数是连续的自然数。

$n \leq 100000, T \leq 1000$

【题解】

为啥别人都用dp呢我用的还是图论做法……

很明显后面相邻一定没有前面相邻优，可以构出一张图，每个点只往出去连一条边。然后就是最长链啦，$O(n)$解决，总复杂度$O(n)$。

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

using namespace std;

const int M=1000010;
int nexta[100010], nextb[100010], bb[1000010], a[100010], b[100010], lsta[1000010], lstb[1000010];
bool vis[100010];
int ans = -1;
int T, n, m;
int main() {
	scanf("%d", &T);
	while(T--) {
		ans = -1;
		scanf("%d%d", &n, &m);
		for (int i=1; i<=n; ++i)
			scanf("%d", &a[i]), vis[i]=0, lsta[a[i]] = lsta[a[i]+1] = n+1;
		for (int i=1; i<=m; ++i) {
			scanf("%d", &b[i]);
			lstb[b[i]] = lstb[b[i]+1] = m+1;
		}
		for (int i=n; i>=1; --i)
			bb[a[i]] = m+1;
		for (int i=m; i>=1; --i) 
			bb[b[i]] = i;
		for (int i=n; i>=1; --i) {
			lsta[a[i]] = i;
			nexta[i] = lsta[a[i]+1];
		}
		for (int i=m; i>=1; --i) {
			lstb[b[i]] = i;
			nextb[i] = lstb[b[i]+1];
		}
		for (int i=1; i<=n; ++i) {
			if(!vis[i]) {
				int start=a[i], l=0;
				int x=i, y=bb[a[i]];
				for (;;) {
					if(1 <= x && 1 <= y && x <= n && y <= m) {
						++l;
						vis[i] = 1;
						x = nexta[x], y = nextb[y];
					} else break;
				}
				if(l>ans) ans=l;
			}
		}
		printf("%d\n", ans);
	}

	return 0;
}