Codeforces Round #618 (Div. 2)

太菜了，也只能补补题了。。。。

A-Non-zero

这道题瞎弄一下就过了，数0的个数，把0全变成1，然后再判断现在和是不是0，和是0的话就再加上1。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
const int N=1e5+10;
int a[10000];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int sum=0;
        int k=0;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            if(a[i]==0)
            {
               k++;
            }
        }
        ans+=k;
        if(sum+k==0)
        {
            ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

B-Assigning to Classes

这道题你仔细想一下，就会发现排完序之后，最中间的两个数的差值就是所要求的最小的答案。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
const int N=1e5+10;
int a[2*N];
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);
        printf("%d\n",a[n+1]-a[n]);
    }
    return 0;
}

C-Anu Has a Function

一道贪心，只要找到一个板子来陈放这些的数就可以了，仔细看一下，那个(x|y-y)位运算之后的结果,等于是在x上把y上二进制是1的位置变成了0，这样的话，我们只要找到只有所以的数二进制位置上的1的个数和，找到最大的那个头就可以了，剩下的随便排序都可以。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int pos[30];
int w=1;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        int k=a[i];
        int cc=0;
        while(k>0)
        {
            if(k&1)
            {
                pos[cc]++;
            }
            cc++;
            k/=2;
        }
    }
    int maxx=0,ma=0;
    for(int i=1;i<=n;i++)
    {
        int k=a[i];
        int cc=0;
        ma=0;
        int num=1;
        while(k>0)
        {
           if(k&1&&pos[cc]==1)
           {
               ma+=num;
           }
           cc++,k/=2,num*=2;;
           if(ma>maxx)
           {
               maxx=ma;
               w=i;
           }
        }
    }
    printf("%d",a[w]);
    for(int i=1;i<=n;i++)
    {
      if(i!=w)
      {
          printf(" %d",a[i]);
      }
    }
    printf("\n");
    return 0;
}

D-Aerodynamic

几何题，判断一下图形中心对称。

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
    }
    if(n%2==0)
    {
        int flog=0;
        for(int i=1;i<=n/2;i++)
        {
            if(a[i]+a[n/2+i]!=a[1]+a[n/2+1]||b[i]+b[n/2+i]!=b[1]+b[n/2+1])
            {

                flog=1;
                break;
            }

        }
        if(!flog)
        {
            printf("YES\n");
        }
        else
        {
             printf("NO\n");
        }

    }
    else
    {
        printf("NO\n");
    }
    return 0;
}

E-Water Balance

题意是让我们可以让（L，R)里的数全部变成（a[L]+a[L+1]+…+a[R])/(R-L+1)。
然后通过这种方式使整个序列的字典序最小。
那我们可以分步来做，顶端top记录了当前的区间值，然后用len[top]记录值为是[top]的有多少个，然后如果后面存在较小值那么肯定要进行合并，那样的话肯定可以使整个序列的字典序变小（可以仔细想想这句话）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
double eps=1e-10;
int a[N];
double s[N],b[N];
int len[N];
int main()
{
      int n;
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
      {
          scanf("%d",&a[i]);
      }
      int top=1;
      double now=1;
      s[1]=a[1];
      len[1]=1;
      for(int i=2;i<=n;i++)
      {
         now=a[i];
         int lenow=1;
         while(s[top]>now+eps)
         {
             now=(now*lenow+s[top]*len[top])/(len[top]+lenow);
             lenow+=len[top];
             top--;
         }
         top++;
         s[top]=now;
         len[top]=lenow;
      }
      int cut=0;
      for(int i=1;i<=top;i++)
      {
          for(int j=1;j<=len[i];j++)
          {
              b[cut+j]=s[i];
          }
          cut+=len[i];
      }
      for(int i=1;i<=n;i++)
      {
          printf("%.10lf ",b[i]);
      }
      printf("\n");

    return 0;
}