[C++知识库]Codeforces Round #775 A-D

总体来说，这场比赛题目好，但是因为很多小的优化没学到，所以C寄了一发，最后机房提前二十分钟关门，D算是寄了。

A. Game
题意：给定一个长度为n的01串，如果是连着的1可以直接走，如果是0可以跳过，当然1也可以跳过，跳过的长度即为花费，问从头走到尾如果只跳一次需要多少花费。

思路：注意读题，只能跳一次，所以只要需要跳，必然是一次性跳过所有的0，直接模拟就好了

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,temp,pos1=0,pos2=0;
    for(cin>>t;t;t--)
    {
        cin>>n;
        pos1=0,pos2=0;
        for(int i=1;i<=n;i++)
        {
            cin>>temp;
            if(!temp&&!pos1)
                pos1=i;
            if(!temp)
                pos2=i;
        }
        if(pos2==0)
            cout<<0<<endl;
        else
        cout<<pos2-pos1+2<<endl;
    }
    return 0;
}

B - Game of Ball Passing
题意：n个人互相传球，每个人传球的次数已知，问他们最少用了多少个球。

思路：用最大的传球次数减去所有的，小于等于0就只用了一个球，否则就输出剩下的

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define N 1000000+100
long long a[N];
int main()
{
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1);
        if(a[n]==0)
        {
            cout<<0<<endl;
            continue;
        }
        for(int i=n-1;i>=1;i--)
            a[n]-=a[i];
        if(a[n]<=0)
            cout<<1<<endl;
        else
            cout<<a[n]<<endl;
    }
    return 0;
}

C - Weird Sum
题意：给定一个矩阵，每个单元格有一个数字代表颜色，求所有颜色相同的单元格任意组合的曼哈顿距离
思路：暴力，直接写个桶把所有颜色相同的装在一起，再枚举求和的时候注意用多项式的规律优化一下，不然会TLE

#include <bits/stdc++.h>
using namespace std;
#define N 1000000+100
struct node{
    long long x,y,c;
};
node a[N];
long long col[N],sum[N];
bool cmp1(node x,node y){
    return x.c<y.c;
}
bool cmp2(node x,node y){
    return x.x>y.x;
}
bool cmp3(node x,node y){
    return x.y>y.y;
}
int main()
{
   // freopen("in.txt","r",stdin);
    register int n,m,cnt=0,maxx=-1,minn=1e9;
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=m;j++)
        {
            scanf("%d",&a[++cnt].c);
            a[cnt].x=i;
            a[cnt].y=j;
            col[a[cnt].c]++;
            maxx=maxx>a[cnt].c?maxx:a[cnt].c;
            minn=minn<a[cnt].c?minn:a[cnt].c;
        }
    }
    sort(a+1,a+cnt+1,cmp1);
    for(register int i=minn;i<=maxx;i++)
        sum[i]=sum[i-1]+col[i];
    register long long ans=0;
    for(register int i=minn;i<=maxx;i++)
    {
        sort(a+sum[i-1]+1,a+sum[i]+1,cmp2);
        for(register int j=1+sum[i-1],k=sum[i]-sum[i-1]-1;j<=sum[i];k-=2,j++)
            ans+=a[j].x*(long long)k;
        sort(a+sum[i-1]+1,a+sum[i]+1,cmp3);
        for(register int j=1+sum[i-1],k=sum[i]-sum[i-1]-1;j<=sum[i];k-=2,j++)
            ans+=a[j].y*(long long)k;
    }
    cout<<ans<<endl;
    return 0;
}

D - Integral Array
正难则反
题意：给定一个数列，我们要求这个数列选取任意两个满足x<=y的数x,y（x和y可以相同）,都满足y/x向下取整存在于数组中。
如果满足要求输出YES
否则输出NO

思路：我们每次分析不满足题意的情况是存在一个r不属于数列并且有y/x=r，所以我们可以枚举所有数组中不存在的数，如果对于这个不存在的数r在数组中有y/x能和r相等，那么就肯定不满足题意了。

#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 1000000+100
 
int a[N];
bool vis[N];
int main()
{
    register int t,n,c;
    //freopen("in.txt","r",stdin);
    for(scanf("%d",&t);t;t--)
    {
        scanf("%d%d",&n,&c);
        for(register int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            vis[a[i]]=1;
        }
        sort(a+1,a+n+1);
        bool falg=true;
        for(register int i=1;i<=c;i++)
        {
            if(vis[i])
                continue;
            if(!falg)
                break;
            for(register int j=i;j<=c;j+=i)
            {
                register int y=j/i;
                if(!vis[y])
                    continue;
                register int pos=lower_bound(a+1,a+n+1,j)-a;
                if(pos==n+1||a[pos]>=y+j)
                    continue;
                else
                {
                    falg=false;
                    break;
                }
            }
        }
        if(falg)
            puts("YES");
        else
            puts("NO");
        for(register int i=1;i<=n;i++)
            vis[a[i]]=false;
    }
    return 0;
}