CF#652(div.2) A-D

A题：纯白送

#include<stdio.h>

int main()
{
    int t,a;

    scanf("%d",&t);

    while(t--)
    {
        scanf("%d",&a);
        if(a%4)
        {
            printf("NO\n");
        }
        else
        printf("YES\n");
     } 
}

B题：
先从最后的1开始，如果它后面不是1也不是末尾，那么判断：如果它后面是连续2个0就消去第一个，直至遇到1。此时消除原来的1。

！！注意，这个解法被hack了。要注意到如果进行到最前面的1，且它前面有0后面只剩最后一个0时，这时候要变成1而不是0。这样就可以和前面的0进一步消除。
！！题解暂未更新

#include<stdio.h>

int main()
{
    int t,a,p[100000]={0},add,n,add2,swi;
    char c;

    scanf("%d",&t);

    while(t--)
    {
        scanf("%d",&n);
        c=getchar();
        for(add=0;add<n;add++)
        {
            c=getchar();
            p[add]=c-'0';
        }
        p[n]=-1;

        for(add=n-2;add>=0;add--)
        {
            swi=0;
            if(p[add]==1)
            {
                for(add2=add+1;add2<n&&p[add2]!=1;add2++)
                {
                    p[add2]=-1;
                    swi=1;
                }
                if(swi)
                {
                    p[add2-1]=0;
                    p[add]=-1;
                }
            }
        }

        for(add=0;add<n;add++)
        {
            if(p[add]!=-1)
            printf("%d",p[add]);
        }
        printf("\n");
     } 
}

C题：首先把数和每个人需要的数量排序。给每个人分配一个最大的数，然后按需要的数量从小到大分配从大到小的数。这样可以使被浪费的数尽可能小。

#include<stdio.h>
#include<iostream>
#include<algorithm>

long long p[200000],w[200000];

using namespace std;

int main()
{
    long long t,n,k,sum,mem;
    long long add,add2;

    scanf("%lld",&t);

    while(t--)
    {
        scanf("%lld %lld",&n,&k);

        for(add=0;add<n;add++)
            scanf("%lld",&p[add]);
        for(add=0;add<k;add++)
            scanf("%lld",&w[add]);

        sort(p,p+n);
        sort(w,w+k);

        sum=0;
        add2=n-1;
        for(add=0;w[add]==1&&add<k;add++)
        {
            sum+=p[add2]*2;
            add2--;
            //printf("[1 %lld]",sum);
        }

        mem=add;

        for(;add<k;add++)
        {
            sum+=p[add2];
            add2--;
            //printf("[2 %lld]",sum);
        }

        for(add=mem;add<k;add++)
        {
            sum+=p[add2-w[add]+2];
            //printf("[3 %lld %lld %lld]",sum,add2,p[add2]);
            add2-=w[add]-1;
        }

        printf("%lld\n",sum);

    }

}

D题：思维题。注意到f(n)=2f(n-2)+f(n-1)+4(n%3==0)就可以了，很有意思的一道题。

#include<stdio.h>

long long p[2000001];

int main()
{
    long long t,add,q;

    p[1]=0;
    p[2]=0;

    for(add=3;add<=2000000;add++)
    {
        p[add]=p[add-2]*2+p[add-1];
        if(add%3==0)
            p[add]+=4;

        p[add]=p[add]%1000000007;
    }

    scanf("%lld",&t);

    while(t--)
    {
        scanf("%lld",&q);
        printf("%lld\n",p[q]);
    }

    return 0;
}