Codeforces Round #618 (Div. 2)全题解（A-E）

Codeforces Round #618 (Div. 2)全题解（A-E）

比赛题目地址：https://codeforces.com/contest/1300

# Name
A Non-zero standard input/output1 s, 256 MB Submit Add to favourites img x10972
B Assigning to Classes standard input/output2 s, 256 MB Submit Add to favourites img x9480
C Anu Has a Function standard input/output1 s, 256 MB Submit Add to favourites img x4802
D Aerodynamic standard input/output1 s, 256 MB Submit Add to favourites img x2146
E Water Balance standard input/output3 s, 256 MB Submit Add to favourites img x839

A.Non-zero

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=100000+7;
int a[106];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        int sum=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        int ans=0;
        if(sum>0)
        {
            for(int i=1;i<=n;i++)
            {
                if(a[i]==0) ans++;
            }
            printf("%d\n",ans);
        }
        else if(sum<=0)
        {
            int k=-1*sum;
            for(int i=1;i<=n;i++)
            {
                if(a[i]==0) ans++;
            }
            if(ans==k)
            {
                printf("%d\n",ans+1);
            }
            else printf("%d\n",ans);
        }
    }

    return 0;
}

B.Assigning to Classes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=300000+7;
int a[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=2*n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a+1,a+1+2*n);
        int minn=abs(a[n+1]-a[n]);
        printf("%d\n",minn);
    }
    return 0;
}

C.Anu Has a Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=300000+7;
int a[maxn];
int main()
{
   int n,c,t,flag=-1;;
   scanf("%d",&n);
   for(int i=0;i<n;i++) scanf("%d",&a[i]);
   for(int i=32;~i;i--)
   {
       t=-1;
       c=0;
       for(int j=0;j<n;j++)
       {
           if(a[j]&(1ll<<i))
           {
               t=j;
               c++;
           }
       }
        if(c==1)
        {
            flag=t;
            break;
        }
   }
   if(~flag) printf("%d ",a[flag]);
   for(int i=0;i<n;i++)
   {
       if(flag==i) continue;
       printf("%d ",a[i]);
   }
    return 0;
}

D.Aerodynamic

多画几个图形，不难发现只需要判断该图形是否为中心对称图形即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=100000+7;
int x[maxn],y[maxn];
int cnt=0;
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    if(n%2==1) {printf("NO\n");return 0;}
    int j=n/2+1;
    double ansx=(x[1]+x[j])/2.0;
    double ansy=(y[1]+y[j])/2.0;
    int flag=1;
    for(int i=1;i<=n/2;i++)
    {
        double ansxx=(x[i]+x[j])/2.0;
        double ansyy=(y[i]+y[j])/2.0;
        if(ansxx!=ansx||ansy!=ansyy)  flag=0;
        j++;
    }
    if(flag==0) printf("NO\n");
    else printf("YES\n");
    return 0;
}

E.Water Balance

维护凸包的写法看了一个红名的方法，写起来很简洁，也很容易理解。

1vwjLF.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=10000000;
const int maxn=1000000+7;

int n;
double a[maxn],s[maxn];
int top,q[maxn];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lf",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    for (int i=n;i>=1;i--)
    {
        q[++top]=i;
        while (top >= 2&&(s[q[top]]-s[i-1])/(q[top]-(i-1))>(s[q[top-1]]-s[q[top]])/(q[top-1]-q[top]))
        {
            top--;
        }
    }
    q[top+1]=0;
    for (int i=top; i>=1; i--)
    {
        double avg=(s[q[i]]-s[q[i+1]])/(q[i]-q[i+1]);
        for (int j = q[i + 1] + 1; j <= q[i]; j++)
            printf("%.10f\n",avg);
    }
    return 0;
}