Educational Codeforces Round 55 (Rated for Div. 2)

A.Vasya and Book

三种情况讨论一下

Educational Codeforces Round 55 (Rated for Div. 2)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int _;
 6     scanf("%d",&_);
 7     while(_--)
 8     {
 9         int n,d,x,y;
10         scanf("%d%d%d%d",&n,&x,&y,&d);
11         if((n-y)%d!=0&&(x-y)%d!=0&&(y-1)%d!=0)
12         {
13             printf("-1\n");
14         }
15         else
16         {
17             int s=n;
18             if((y-x)%d==0)s=min(s,abs(y-x)/d);
19             if((n-y)%d==0)s=min(s,(n-y)/d+(n+d-1-x)/d);
20             if((y-1)%d==0)s=min(s,(x+d-2)/d+(y-1)/d);
21             printf("%d\n",s);
22         }
23     }
24     return 0;
25 }

View Code

B. Vova and Trophies

把G切开这样共有k段

针对k的数量分三类处理

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char a[100001];
 4 int k,l[100001],r[100001];
 5 int main()
 6 {
 7     int n;
 8     scanf("%d\n",&n);
 9     scanf("%s",a);
10     int i=0;
11     while(i<n)
12     {
13         while(i<n&&a[i]!='G')i++;
14         if(i>=n)break;
15         k++;
16         l[k]=i;
17         while(i<n&&a[i]=='G')i++;
18         r[k]=i-1;
19     }
20     int ans=k==0?0:r[1]-l[1]+1+(k>=2);
21     for(i=2;i<=k;i++)
22     {
23         if(l[i]-2==r[i-1])ans=max(ans,r[i]+r[i-1]-l[i]-l[i-1]+3-(k<=2));
24         else ans=max(ans,r[i]-l[i]+1+(k>=2));
25     }
26     printf("%d",ans);
27     return 0;
28 }

View Code

C. Multi-Subject Competition

如果一个项目能派x人出战，且x人的战斗值之和为正

那么就把它加入到最终每个项目派x人出战的贡献中

最后扫一遍答案

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node
 4 {
 5     int c,r;
 6 }nu[100001];
 7 bool cmp(node i,node j)
 8 {
 9     return i.r!=j.r?i.r<j.r:i.c>j.c;
10 }
11 int s[100001];
12 int main()
13 {
14     int n,m;
15     scanf("%d%d",&n,&m);
16     for(int i=1;i<=n;i++)
17     {
18         scanf("%d%d",&nu[i].r,&nu[i].c);
19     }
20     sort(nu+1,nu+n+1,cmp);
21     int N=0,ss;
22     for(int i=1;i<=n;i++)
23     {
24         if(nu[i].r!=nu[i-1].r){ss=0;N=0;}
25         ss+=nu[i].c;
26         N++;
27         if(ss>0)s[N]+=ss;
28     }
29     int ans=0;
30     for(int i=1;i<=n;i++)ans=max(s[i],ans);
31     printf("%d",ans);
32     return 0;
33 }

View Code

D. Maximum Diameter Graph

每个度大于等于2的点在最后的图中一定形成一条链

然后链的头和尾加一个度为1的点（如果有）

构不成图就是度大于等于2的每个点度-2的和小于度为1的点数量-2

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 vector<int> n0,n1,nx;
 4 int main()
 5 {
 6     int n,s1=0,s2=0,n2=0,x;
 7     scanf("%d",&n);
 8     for(int i=1;i<=n;i++)
 9     {
10         scanf("%d",&x);
11         if(x==1)
12         {
13             n0.push_back(i);
14             s1++;
15         }
16         else
17         {
18             n1.push_back(i);
19             nx.push_back(x-2);
20             s2+=x-2;
21             n2++;
22         }
23     }
24     if(s1>s2+2){printf("NO");return 0;}
25     printf("YES %d\n%d\n",n2+(s1>=1)+(s1>=2)-1,s1+n2-1);
26     if(s1>=1)printf("%d %d\n",n1[0],n0[s1-1]),s1--;
27     if(s1>=1)printf("%d %d\n",n1[n2-1],n0[s1-1]),s1--;
28     int i=0;
29     while(s1)
30     {
31         while(nx[i]==0)i++;
32         nx[i]--;
33         printf("%d %d\n",n1[i],n0[s1-1]);
34         s1--;
35     }
36     for(i=0;i<n2-1;i++)
37         printf("%d %d\n",n1[i],n1[i+1]);
38     return 0;
39 }

View Code

E. Increasing Frequency

贪心+最长连续字段和

答案=[l,r]*这一段（众数个数-C个数）+C总的个数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int nc[500001],s[500001];
 4 int pre[500001];
 5 int main()
 6 {
 7     int n,c,x;
 8     int ans=0;
 9     scanf("%d%d",&n,&c);
10     for(int i=1;i<=n;i++)
11     {
12         scanf("%d",&x);
13         if(x==c)
14             nc[i]=nc[i-1]+1;
15         else
16         {
17             nc[i]=nc[i-1];
18             s[x]=max(1,s[x]+1-nc[i]+nc[pre[x]]);
19             pre[x]=i;
20             ans=max(s[x],ans);
21         }
22     }
23     printf("%d",ans+nc[n]);
24     return 0;
25 }

View Code

后面补G最大权闭合子图学完补

F思考ing

秒客网

Educational Codeforces Round 55 (Rated for Div. 2)

相关文章