526互联

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

发布时间 2023-07-28 23:51:05作者: Favel

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

但能过题就是了

A. Morning Sandwich

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

三明治总是遵循以下公式

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

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

今天，莫诺卡普一觉醒来，发现自己有b块面包、c片奶酪和h片火腿。他的早晨三明治最多可以有多少层？

 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 正在玩另一款电脑游戏。他的角色又在杀死一些怪物。一共有n只怪物，编号从1到n，其中的i只最初有ai点健康值。

单卡普的角色有一个能力，可以对当前生命值高的怪物造成k的伤害。如果有多个怪物，则选择指数较小的一个。如果怪物的生命值在 Monocarp 使用他的能力后小于或等于 0，那么它就会死亡。

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

给你一个字符串 s，由 n个字符 0 和/或 1 组成。

你复制了这个字符串的 m个副本，让第 i个副本成为字符串 ti。然后在每个副本上执行一个操作：对于 i-th 副本，对其子串 [li;ri]从 li-th 字符到 ri-th 字符的子串，包括两个端点）进行排序。注意：每个操作只影响一个副本，每个副本只受一个操作的影响。

你的任务是计算t1,t2,…中不同字符串的数量。请注意，只有在操作后至少有一个副本保持不变时，才应计算初始字符串 s。

 

记录0，1的位置.1的后面有几个0，对于这个1就有几个有效区间，lowerbound和upperbound去找l后的第一个1的位置（记作L）和r前的第一个0的位置（记作R），出现L>R或找不到对应的L或R时字符串本身不变，之后用set记录并查找L是否取到了有效的R，直接开maxn的set数组可能比较大（我也不知道有多大），故用map离散化一下（虽然不一定效果会变好）

用更好的做法请参考他人代码，我的这个代码写完一看自己都想笑（但过了就很棒），实际上debug了蛮长时间导致赛时没过（日常过D不过C）

 

 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

给你一个由 n个整数组成的数组，其中每个整数都是0、1或2。最初，数组的每个元素都是蓝色的。

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

  • 支付一枚硬币，选择一个蓝色元素并将其涂成红色；
  • 选择一个不等于0的红色元素和一个与其相邻的蓝色元素，将所选的红色元素减少1，并将所选的蓝色元素涂成红色。

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

 

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

 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 }