Educational Codeforces Round 152 (Rated for Div. 2)(A~D)
感觉代码越写越丑了......
但能过题就是了
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 }