Codeforces Round #587 (Div. 3)

https://codeforces.com/contest/1216/problem/A

A. Prefixes

题意大概就是每个偶数位置前面的ab数目要相等，很水，被自己坑了

1是没看见要输出修改后的字符串，2是修改的写反了。。3是忘记清零了？，生生把罚时拖的。。。

本来四分钟的题的。。然后罚时+10分钟过题，我晕了，以后还是要再认真一点，比如说把样例测完。。

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int main(){
 5     int a=0,b=0,ans=0,n;
 6     string s;
 7     ios::sync_with_stdio(0);
 8     cin>>n;cin>>s;
 9     for(int i = 0;i < n;++i){
10         if(s[i]==‘a‘)a++;
11         else if(s[i]==‘b‘)b++;
12         if(i%2){
13             if(a>b){
14                 s[i]=‘b‘;ans++;
15             }
16             else if(a<b){
17                 s[i]=‘a‘;ans++;
18             }
19             a = b = 0;
20         }
21     }
22     
23     cout<<ans<<endl;
24     cout<<s<<endl;
25     return 0;
26 }

AC代码

 

https://codeforces.com/contest/1216/problem/B

B. Shooting

也很简单，贪心+模拟，这题真的是秒写一发过，，但是我先去看c才回来写的b。。。头疼，被某个哥哥干扰了一波，，

题意是给你n和n个数，然后你按某个顺序排列，让Σai*（i-1）+1最小 ，最后输出总数和然后按原顺序输出你使用该数的”时刻“

emmm很明显就是从大到小排序然后直接算，没坑，直接写就完事了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct ac{
 4     int x,now;
 5 }s[1050];
 6 bool cmp(ac a,ac b){
 7     return a.x>b.x;
 8 }
 9 int main(){
10     int n;
11     long long ans= 0;
12     ios::sync_with_stdio(0);
13     cin>>n;
14     for(int i = 1;i <= n;++i){
15         cin>>s[i].x;
16         s[i].now=i;
17     
18     }
19     sort(s+1,s+1+n,cmp);
20     for(int i = 1; i <= n;++i){
21         ans+=(s[i].x*(i-1)+1);
22     }
23     cout<<ans<<endl;
24     for(int i = 1; i <= n;++i){
25         cout<<s[i].now<<" ";
26     }
27     return 0;
28 }

AC代码

 

https://codeforces.com/contest/1216/problem/C

C. White Sheet

呜呜呜呜呜还是简单题啊，给你一张白纸和两张黑纸的坐标，让你判断黑纸是否将白纸完全覆盖了。

这题好像有人二维前缀和过了但是我没看懂，到时候再好好看看吧。

本来我是正向考虑，算出白纸面积，黑纸覆盖了哪一块就剪掉，，，，结果没考虑到黑纸重复部分然后又不想磨了。。

后面才发现如果只有一个角相交是没有办法完全覆盖，，，所以根本不需要那样写呜呜呜呜呜

把能够覆盖的几种情况列出来，剩下的就都能看见白纸了（参考rank1的写法

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 struct ac{
 5     ll x1,y1,x2,y2;
 6 }a[2];
 7 ll x1,x2,y1,y2,s,ss[2];
 8 int main(){
 9  
10     ios::sync_with_stdio(0);
11     cin>>x1>>y1>>x2>>y2;
12     s=(x2-x1)*(y2-y1);
13     
14     for(int i = 0;i < 2;++i){
15         cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
16         ss[i]=(a[i].x2-a[i].x1)*(a[i].y2-a[i].y1);
17     }
18     if(ss[0]+ss[1] <s){
19         cout<<"YES"<<endl;return 0; 
20     }
21     if(a[0].x1<=x1&&a[0].y1<=y1&&a[0].x2>=x2&&a[0].y2>=y2){
22         cout<<"NO"<<endl;return 0;
23     }
24     if(a[1].x1<=x1&&a[1].y1<=y1&&a[1].x2>=x2&&a[1].y2>=y2){
25         cout<<"NO"<<endl;return 0;
26     }
27     if(a[0].x1<=x1&&a[0].x2>=x2&&a[1].x1<=x1&&a[1].x2>=x2)
28     {
29         if(a[0].y1<=y1&&a[0].y2>=a[1].y1&&a[1].y2>=y2){
30             cout<<"NO"<<endl;return 0;
31         }
32         if(a[1].y1<=y1&&a[1].y2>=a[0].y1&&a[0].y2>=y2){
33             cout<<"NO"<<endl;return 0;
34         }
35     }
36     if(a[0].y1<=y1&&a[0].y2>=y2&&a[1].y1<=y1&&a[1].y2>=y2){
37         if(a[0].x1<=x1&&a[0].x2>=a[1].x1&&a[1].x2>=x2){
38                 cout<<"NO"<<endl;return 0;
39         }
40         if(a[1].x1<=x1&&a[1].x2>=a[0].x1&&a[0].x2>=x2){
41                 cout<<"NO"<<endl;return 0;
42         }
43     }
44         cout<<"YES"<<endl;return 0;
45  
46 }

AC代码

（好好记住这三种情况 下次碰见同类型的得反应快一点qwq

 

https://codeforces.com/contest/1216/problem/D

D. Swords

这题过的比c还多。。。。

没有证明出来为什么这样写是对的

反正就是用最大值减去当前值得到的差值求一个整体的gcd，然后再求一遍人数就好了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[200005];
 4 int main(){
 5     int n,cnt = 0;
 6     long long ans= 0;
 7     ios::sync_with_stdio(0);
 8     cin>>n;
 9     for(int i = 0;i < n;++i)cin>>a[i];
10     sort(a,a+n);
11     for(int i = 0;i < n;++i)cnt=__gcd(cnt,a[n-1]-a[i]);
12     for(int i = 0;i < n;++i)ans+=(a[n-1]-a[i])/cnt;
13     cout<<ans<<" "<<cnt<<endl;
14     return 0;
15 }

AC代码