A. Sea Battle
给出四个整数w1,h1,w2,h2 计算在方格上围出w1h1与w2h2的方形所需要的方块的数量

数学
显然ans = (max(w1,w2)+h1+h2+2) * 2，凹入的部分可以换到方形凸出的地方，使得两个方形被围住

1
2
3
4
5
6
7
8
int w1,h1,w2,h2,ans;

int main(){
	cin>>w1>>h1>>w2>>h2;
	ans = (max(w1,w2)+h1+h2+2) * 2;
	cout<<ans<<endl;
	return 0;
}

B. Draw!
给出n个数对，对应某个时刻的比分，输出最大的平局的次数6

对于数对(a,b)和数对(c,d)，要平局次数最大，则中间可能出现(x,x)是最好的，而x小于c,d中最小的，大于a,b中最大的，所以取平均值，如果a，b不相等，则可能出现x = min(a,b)的情况，有1的贡献，所以每次输入的时候，ans = ans + max(0,min(c,d) - max(a,b) + (a!=b))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n,a[10007],b[10007],ans = 1;
int tmp1,tmp2;
int main(){
	mst(a,0);
	mst(b,0);
	cin>>n;
	for(int i =  1;i<=n;i++){
		cin>>a[i]>>b[i];
		tmp1 = max(a[i-1],b[i-1]);
		tmp2 = min(a[i],b[i]);
		ans+= max(0,tmp2-tmp1+(a[i-1]!=b[i-1]));
	}
	cout<<ans<<endl;
	return 0;
}

C. Birthday
Vlad过生日有n个朋友，要让这n个朋友围成一圈使得他每个人与相邻两个人之间的高度差距最小
输入n与他们的高度，输出最优的序列

贪心
要让高度差距最小，可以把高的尽量凑在一起，然后向两边递减即可
排序一次，分为两个数组，依次输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n,a[200];
vector<int> t1,t2;

int main(){
	cin>>n;
	for(int i = 0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	for(int i = 0;i<n;i+=2){
		t1.push_back(a[i]);
		if(i+1 >= n) break;
		t2.push_back(a[i+1]);
	}
	for(int i = 0;i<t1.size();i++){
		if(i==0) cout<<t1[i];
		else cout<<" "<<t1[i];
	}
	for(int i = t2.size() -1 ;i>=0;i--) cout<<" "<<t2[i];
	cout<<endl;
	return 0;
}

D. Gourmet choice
第一天有n个菜，第二天有m个菜，給一个n*m矩阵，含有“>”、“=”、“<”，a（i，j）指的是：第一天的第i件菜的美味度>=<第二天的第j件菜的美味度。求出满足这个矩阵的n+m件菜的各自的美味度，要求使用的最大数字尽量小。

并查集 + 拓扑排序
将相等的视为同一元素放入并查集，按照对应关系进行建图，然后拓扑排序，数字依照bfs的顺序依次递增

拓扑排序：
https://www.cnblogs.com/en-heng/p/5085690.html
https://blog.csdn.net/qq_41713256/article/details/80805338

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int fa[3000],n,m,in[3000],ans[3000];
char str[1007][1007];
vector<int> G[3007];

int tfind(int x){
	return x == fa[x]?x:fa[x] = tfind(fa[x]);
}

bool toposort(){
	mst(ans,0);
	queue<int> Q;
	for(int i = 1;i<=n+m;i++) if(tfind(i) == i && in[tfind(i)] == 0) Q.push(tfind(i)),ans[tfind(i)] = 1;
	while(!Q.empty()){
		int u = Q.front();
		Q.pop();
		for(int i = 0;i<G[u].size();i++){
			int v = G[u][i];
			in[v]--;
			if(in[v] == 0) Q.push(v),ans[v] = ans[u] + 1;
		}
	}
	for(int i = 1;i<=n+m;i++) if(!ans[tfind(i)]) return false;
	return true;
}

void Addedge(int u,int v){
	G[u].push_back(v);
	in[v]++;
}

int main(){
	cin>>n>>m;
	for(int i = 1;i<=n+m;i++) fa[i] = i;
	for(int i = 1;i<=n;i++){
		cin>>str[i];
		for(int j = 0;j<m;j++){
			if(str[i][j] == '='){
				int x = tfind(i),y = tfind(n+j+1);
				fa[x] = y; 
			}
		}
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<m;j++){
			if(str[i][j] == '<') Addedge(tfind(i),tfind(n+j+1));
			else if(str[i][j] == '>') Addedge(tfind(n+j+1),tfind(i));
		}
	}
	if(!toposort()){
		cout<<"No"<<endl;
	}
	else{
		cout<<"Yes"<<endl;
		for(int i = 1;i<=n;i++) cout<<ans[tfind(i)]<<" ";
		cout<<endl;
		for(int i = n+1;i<=n+m;i++) cout<<ans[tfind(i)]<<" ";
		cout<<endl;
	}
	return 0;
}

E. String Multiplication
定义字符串s与字符串t的乘法操作，s·t所得字符串为将s的每个字符分开，然后t插入到空隙中
现在要输入n个字符串，输出这n个字符串相乘后得到的字符串中最大连续的字符有多少个

贪心
可以从第一个字符串开始推导，在字符串相乘的过程中，主要检查后面相乘的字符串的前缀与后缀，然后进行转移，相当于将前面的字符串拆开然后逐个放入，主要查询字母中答案最大的即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int n,f[100007][26],pre[26],suf[26],ans = 0;
char s[100007];

void Solve(int *f){
	cin>>s;
	int l = strlen(s);
	int mx = 0,cnt = 0;
	for(int i = 0;i<26;i++){
		mx = cnt = 0;
		for(int j = 0;j<l;j++){
			if(s[j] == i + 'a') mx = max(mx,++cnt);
			else cnt = 0;
		}
		f[i] = mx,pre[i] = suf[i] = 0;
		for(int j = 0;j<l;j++){
			if(s[j] == i + 'a') pre[i]++;
			else break;
		}
		for(int j = l-1;j>=0;j--){
			if(s[j] == i + 'a') suf[i]++;
			else break;
		}
	}
}

int main(){
	mst(f,0);
	cin>>n;
	Solve(f[1]);
	for(int i = 2;i<=n;i++){
		Solve(f[i]);
		int l = strlen(s);
		for(int j = 0;j<26;j++){
			if(f[i - 1][j]){
				if(pre[j]!=l) f[i][j] = max(f[i][j],pre[j]+suf[j]+1);
				else f[i][j] = max(f[i][j],l*(f[i-1][j]+1)+ f[i-1][j]);
			}
		}
	}
	for(int i = 0;i<26;i++) ans = max(ans,f[n][i]);
	cout<<ans<<endl;
	return 0;
}

F. Asya And Kittens
Asya有n只猫，要把它们关在n个笼子里，在第i天第ai和第bi两只小猫想要玩耍，Asya就要把它们之间的挡板拆掉
但是现在Asya忘了一开始每只小猫是在哪个笼子里面了，但是她记得每天的ai、bi，所以请输出可能的笼子的安排

并查集
每次合并的猫并不是一定相邻，而是在合并之前在不同的笼子里面相邻，即不同的连通块中，所以考虑用并查集而不是对连通图的重建，n-1条边的连通图重建不能保证每个点都只有两个出点，所以用并查集进行模拟合并
为了输出对应的顺序，用r数组和son数组进行操作，相当于按照合并顺序将每个数字串起来，最后依次输出son数组即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int fa[150007],son[150007],r[150007],n,a,b;

int tfind(int x){
	return x==fa[x]?x:(fa[x] = tfind(fa[x]));
}

int main(){
	cin>>n;
	for(int i = 1;i<=n;i++) fa[i] = r[i] = i;
	for(int i = 1;i<n;i++){
		cin>>a>>b;
		a = tfind(a);
		b = tfind(b);
		son[r[a]] = b;
		r[a] = r[b];
		fa[b] = a;
	}
	int tmp = tfind(1);
	cout<<tmp;
	for(int i = son[tmp];i;i = son[i]) cout<<" "<<i;
	cout<<endl;
	return 0;
}

G. Most Dangerous Shark
从左到右依次有n个Domino骨牌，手动推倒第i个骨牌的花费为ci，每个骨牌之间的距离为1，第i个骨牌的高度为hi，可以选择向右或向左推到这个骨牌，它将会压倒该方向上距离它小于hi的所有骨牌，求推倒所有骨牌的最小消费

copy
单调栈 DP
https://www.cnblogs.com/TinyWong/p/10427161.html
令L[i],R[i]分别表示第i个骨牌向左（右）推倒后，会将(L[i],i]（[i,R[i])）区间内的骨牌推倒。这个可以用单调栈在O(n)时间内解决。
令f[i]表示（只通过推倒前i个骨牌来）推倒前i个骨牌的最小花费，则对1≤i≤n，
$f[i]=min(f[L[i]]+ci,minj<i<R[j]{f[j−1]+cj})$
这个动态规划也能用单调栈在O(n)时间内解决。