CodeforcesRound541Div2解题记录

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)时间内解决。