Educational Codeforces Round 152 (Rated for Div. 2)(A~D)

Favelcpp / 2023-07-29 / 原文

感觉代码越写越丑了......

但能过题就是了

A. Morning Sandwich

莫诺卡普总是用美味的三明治开始他的早晨。莫诺卡普做的三明治总是由面包、奶酪和/或火腿组成。

三明治总是遵循以下公式

一块面包
一片奶酪或火腿
一块面包
一片奶酪或火腿
一块面包

因此，面包总是放在顶部和底部，面包和馅料交替出现，馅料是一片奶酪或火腿。每一块面包和每一片奶酪或火腿被称为一层。

今天，莫诺卡普一觉醒来，发现自己有

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define int long long
 5 
 6 signed main()
 7 {
 8     ios::sync_with_stdio(false);
 9     cin.tie(0);cout.tie(0);
10     int _=1;
11     cin>>_;
12     while (_--){
13         int b,c,h;
14         cin>>b>>c>>h;
15         int d=c+h;
16         if (d<=b-1) cout<<d*2+1<<'\n';
17         else cout<<b*2-1<<'\n';
18     }
19 }

B. Monsters

Monocarp 正在玩另一款电脑游戏。他的角色又在杀死一些怪物。一共有

单卡普的角色有一个能力，可以对当前生命值高的怪物造成

Monocarp 使用他的能力直到所有怪物死亡。你的任务是决定怪物死亡的顺序

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define int long long
 5 const int maxn=3e5+10;
 6 
 7 struct node{
 8     int a;
 9     int id;
10 };
11 
12 struct node a[maxn];
13 
14 bool cmp(struct node a,struct node b)
15 {
16     if (a.a!=b.a) return a.a>b.a;//不分开写会WA3，虽然不清楚为什么
17     return a.id<b.id;
18 }
19 
20 signed main()
21 {
22     ios::sync_with_stdio(false);
23     cin.tie(0);cout.tie(0);
24     int _=1;
25     cin>>_;
26     while (_--){
27         int n,k;
28         cin>>n>>k;
29         for (int i=0;i<n;i++){
30             cin>>a[i].a;
31             a[i].id=i+1;
32             a[i].a%=k;
33             if (a[i].a==0) a[i].a=k;
34         }
35         sort(a,a+n,cmp);
36         for (int i=0;i<n;i++) cout<<a[i].id<<" ";
37         cout<<'\n';
38     }
39 }

C. Binary String Copying

给你一个字符串

你复制了这个字符串的

你的任务是计算

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define int long long
 5 const int maxn=2e5+10;
 6 int zero[maxn],one[maxn];
 7 
 8 signed main()
 9 {
10     ios::sync_with_stdio(false);
11     cin.tie(0);cout.tie(0);
12     int _=1;
13     cin>>_;
14     while (_--){
15         int n,m;
16         cin>>n>>m;
17         string s;
18         cin>>s;
19         int z=0,o=0;
20         for (int i=0;i<n;i++){
21             if (s[i]=='0') zero[z++]=i+1;
22             else one[o++]=i+1;;
23         }
24         zero[z++]=maxn;
25         one[o++]=maxn;
26         bool ps=false;
27         int ans=0,cnt=1;
28         map<int,int> mp;
29         set<int> sa[o];
30         while (m--){
31             int l,r;
32             cin>>l>>r;
33             int id=lower_bound(one,one+o,l)-one;
34             int idd=upper_bound(zero,zero+z,r)-zero-1;
35             if (id==o-1||one[id]>=zero[idd]){
36                 if (ps) continue;
37                 else{
38                     ps=true;
39                     ans++;
40                     continue;
41                 }
42             }
43             else{
44                 if (idd==z){
45                     if (ps) continue;
46                     else{
47                         ps=true;
48                         ans++;
49                         continue;
50                     }
51                 }
52                 if (mp[one[id]]==0){
53                     mp[one[id]]=cnt++;
54                     sa[mp[one[id]]].insert(zero[idd]);
55                     ans++;
56                 }
57                 else{
58                     if (sa[mp[one[id]]].find(zero[idd])!=sa[mp[one[id]]].end()) continue;
59                     else{
60                         sa[mp[one[id]]].insert(zero[idd]);
61                         ans++;
62                     }
63                 }
64             }
65         }
66         cout<<ans<<'\n';
67     }
68 }

D. Array Painting

给你一个由

您的目标是将数组中的每个元素涂成红色。为此，您可以执行两种类型的操作：

支付一枚硬币，选择一个蓝色元素并将其涂成红色；
选择一个不等于

要实现目标，你至少需要花费多少金币？

有连续的非零将其合并，取这些数的最大值占据那个位置，然后模拟即可

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define int long long
 5 const int maxn=2e5+10;
 6 int a[maxn],b[maxn];
 7 
 8 signed main()
 9 {
10     ios::sync_with_stdio(false);
11     cin.tie(0);cout.tie(0);
12     int _=1;
13 //    cin>>_;
14     while (_--){
15         int n;
16         cin>>n;
17         for (int i=0;i<n;i++) cin>>a[i];
18         int cnt=1;
19         for (int i=0;i<n;i++){
20             if (a[i]==0) b[cnt++]=a[i];
21             else{
22                 int mx=a[i];
23                 for (int j=i;j<n;j++){
24                     if (a[j]!=0){
25                         mx=max(mx,a[j]);
26                     }
27                     else{
28                         i=j-1;
29                         break;
30                     }
31                     if (j==n-1) i=n-1;
32                 }
33                 b[cnt++]=mx;
34             }
35         }
36 //        for (int i=0;i<cnt;i++) cout<<b[i]<<" ";
37 //        cout<<'\n';
38         int ans=0;
39         bitset<maxn> bo;
40         bo[0]=1;
41         for (int i=1;i<cnt;i++){
42             if (b[i]==1){
43                 if (b[i-1]==0&&bo[i-1]==0) bo[i-1]=1,ans++;
44                 else if (b[i+1]==0&&bo[i+1]==0) bo[i+1]=1,ans++;
45                 else ans++;
46             }
47             if (b[i]==2){
48                 bo[i-1]=1;
49                 bo[i+1]=1;
50                 ans++;
51             }
52         }
53         for (int i=1;i<cnt;i++){
54             if (b[i]==0&&bo[i]==0) ans++;
55         }
56         cout<<ans<<'\n';
57     }
58 }