上海大学程序设计联赛A-C E-F

从简单的开始。
C F B E A G
C：签到题。

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

using namespace std;

int main()
{
    double t,sum,n,flag,add;
    char c;

    cin>>t;
    while(t--)
    {
        sum=0;
        cin>>n;
        c=getchar();
        for(add=0;add<n;add++)
        {
            flag=1;
            c=getchar();
            while(c!=10)
            {
                if(c=='2'&&flag)
                {
                    flag=0;
                    sum++;
                }
                c=getchar();
            }
        }
        sum=sum/n;
        printf("%lf\n",sum);
    }
    return 0;
}

F：记每次操作的得分为p1，p2，p3...易证p1>=p2>=p3>=...，又有第一个人的得分为p1+p3+p5+...，第二个人的得分为p2+p4+p6+...故第一个人必胜。

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

using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cout<<"Yes"<<endl;
    }
    return 0;
}

B：简单的运算。写复杂了，还能简化，并且可以通过数组实现多重括号的运算。

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

using namespace std;

char p[100002]={0};

int main()
{
    long long flag=0,sum1=0,sum2=0,add=0,n,times,k,flag2;


    char c;
    c=getchar();
    while(c!=10)
    {
        p[add++]=c;
        c=getchar();
    }
    n=add;
    for(add=0;add<n;add++)
    {
        times=0;
        flag2=0;
        if(flag==0)
        {
            if(p[add]=='C'||p[add]=='H'||p[add]=='O')
            {
                if(p[add]=='C') k=13;
                if(p[add]=='H') k=1;
                if(p[add]=='O') k=17;
                while(p[add+1]<='9'&&p[add+1]>='0')
                {
                    times=times*10;
                    times+=p[add+1]-'0';
                    add++;
                    flag2=1;
                }
                if(!flag2)
                    times=1;


                sum1+=k*times;
            }
            else if(p[add]=='(')
                flag=1;
        }
        else
        {
            if(p[add]=='C'||p[add]=='H'||p[add]=='O')
            {

                if(p[add]=='C') k=13;
                if(p[add]=='H') k=1;
                if(p[add]=='O') k=17;
                while(p[add+1]<='9'&&p[add+1]>='0')
                {
                    times=times*10;
                    times+=p[add+1]-'0';
                    add++;
                    flag2=1;
                }
                if(!flag2)
                    times=1;

                sum2+=k*times;
            }
            else if(p[add]==')')
            {
                flag=0;
                while(p[add+1]<='9'&&p[add+1]>='0')
                {
                    times=times*10;
                    times+=p[add+1]-'0';
                    add++;
                    flag2=1;
                }
                if(!flag2)
                    times=1;

                sum1+=sum2*times;
                sum2=0;
            }
        }
    }
    printf("%lld",sum1);
    return 0;
}

E：体力题。首先将十六进制转化为二进制，通过二分查找找到对应数值，再转回十六进制。

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

using namespace std;

int s[100000],r[8],zz[32],yy;
long long j[100000];

int main()
{
    long long k[31];
    k[0]=1;
    int n,m,p,add,x,sum;
    char c;
    scanf("%d %d %d",&n,&m,&p);
    for(add=1;add<=30;add++)
    {
        k[add]=k[add-1]*2;
    }
    for(add=0;add<k[m-p];add++)
    {
        scanf("%lld",&j[add]);
        j[add]=j[add]*100000+add;
    }
    sort(j,j+k[m-p]);
    for(add=0;add<k[m-p];add++)
    {
        s[add]=j[add]%100000;
        j[add]=j[add]/100000;
    }

    cin>>x;
    while(x--)
    {
        c=getchar();
        for(add=0;add<8;add++)
        {
            c=getchar();
            if(c<='9'&&c>='0')
                r[add]=c-'0';
            else
                r[add]=c-'A'+10;
        }
        for(add=0;add<8;add++)
        {
            zz[add*4]=r[add]/8;
            if(zz[add*4]) r[add]-=8;
            zz[add*4+1]=r[add]/4;
            if(zz[add*4+1]) r[add]-=4;
            zz[add*4+2]=r[add]/2;
            if(zz[add*4+2]) r[add]-=2;
            zz[add*4+3]=r[add];
        }
        sum=0;
        for(add=0;add<32-p;add++)
        {
            sum=sum*2;
            sum+=zz[add];
        }
        for(add=0;add<k[m-p];add++)
        {
            if(sum==j[add])
                break;
        }
        if(add==k[m-p])
        {
            cout<<"interrupt!"<<endl;
            continue;
        }
        else
        {
            yy=s[add];
            for(add=0;add<32-p;add++)
            {
                if(yy>=k[32-p-add-1])
                {
                    zz[add]=1;
                    yy-=k[32-p-add-1];
                }
                else
                    zz[add]=0;
            }
            for(add=0;add<8;add++)
            {
                r[add]=0;
                for(int add2=0;add2<4;add2++)
                {
                    r[add]=r[add]*2;
                    r[add]+=zz[add*4+add2];
                }
                if(r[add]<10)
                    cout<<r[add];
                else
                    printf("%c",r[add]-10+'A');
            }
            cout<<endl;

        }
    }
    return 0;
}

A：从这题开始略有难度。首先可以将题转化为 将n/k分解成三个互质的且不为一的数。
令n=n/k。考虑n为偶数，则三个数一定为偶+奇+奇，不妨设a=2，b=n/2-1,c=n/2+1，如果b和c为偶数则b--，c++。
若n为奇数，考虑n%3==0，则a=n/3-2,b=n/3,c=n/3+2。考虑n%3==2，则a=(n-2)/3-2,b=(n-2)/3,c=(n-2)/3
+2+2。此时会出现a与c都是3的倍数的情况，则a-=2,b+=2。考虑n%3==4也就是n%3==1,a=(n-4)/3-2,b=(n-4)/3+2,c=(n-4)/3+2+2。此时会出现a与c都是3的倍数的情况，则b-=2，c+=2。
易证使用上面的方法不会出现abc不互质的情况，但需要排除abc为1的情况，即n<=9，n=11，13，17

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

using namespace std;

int main()
{
    long long t,n,k,a,b,c;
    cin>>t;

    while(t--)
    {
        cin>>n>>k;
        if(n%k!=0)
        {
            printf("-1 -1 -1\n");
            continue;
        }
        n=n/k;
        if(n<=9||n==11||n==13||n==17)
        {
            printf("-1 -1 -1\n");
            continue;
        }
        if(n%2==0)
        {
            a=2;
            b=(n-2)/2-1;
            c=(n-2)/2+1;
            if(b%2==0)
            {
                b--;
                c++;
            }
        }
        else
        {
            if(n%3==0)
            {
                a=n/3-2;
                b=n/3;
                c=n/3+2;
            }
            else if(n%3==2)
            {
                a=(n-2)/3-2;
                b=(n-2)/3;
                c=(n-2)/3+2+2;
                if(c%3==0)
                {
                    a-=2;
                    b+=2;
                }
            }
            else if(n%3==1)
            {
                a=(n-4)/3-2;
                b=(n-4)/3+2;
                c=(n-4)/3+2+2;
                if(c%3==0)
                {
                    b-=2;
                    c+=2;
                }
            }
        }
        a=a*k,b=b*k,c=c*k;
        printf("%lld %lld %lld\n",a,b,c);
    }
}

G：没有全过，回头再找一下疏漏。
大体思路是用dp。将问题转化在2n+1个数中取n个不相邻的数，找最大的和。假设取1 3 5 7...2n-1，那么可以将问题转化为：将两个空格插入已经取好的数列中。即：将两个空格安排再2n+1个数中间。因此设立数组zz[200020][3]，其中zz[a][b]表示到第a个数已经用了b个空格的情况下，可能的最大值。
例：有1 3 6 2 4 8 9 7
zz[1][0]=1
zz[1][1]=-1e17
zz[1][2]=-1e17 注意到取第一个数的话，不可能是已经使用了一个或两个空格的状态
zz[2][0]=-1e17 注意到取第二个数的话，不可能是没有使用空格的状态
zz[2][1]=3
zz[2][2]=-1e17
zz[3][0]=zz[1][0]+6=7 不使用空格，那么应该取第1 3个数
zz[3][1]=-1e17
zz[3][2]=6 两个空格，即第1和第2都不取，直接取第3

zz[4][1]=max(zz[2][1],zz[1][0])+2 要么从1跳过来，要么从2顺延过来。换句话说，一种是取1 4，一种是取2 4，两种都是用了一个空格的情况。
zz[5][0]=zz[3][0]+4=11 取第1 3 5个数
zz[5][2]=max(zz[3][2],zz[1][0])+4 要么从1跳过来，要么从3顺延过来。换句话说，一种是取1 5，一种是取3 5，两种都是用了两个空格的情况。

...

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

using namespace std;

long long j[200020],v[200020]={0},zz[200020][3]; 

int main()
{
    long long find(int left,int right);

    long long n,x,add,lmax,lmm,rmax,rmm,sumt,summax=-1e16;
    cin>>n>>x;

    for(add=1;add<=n;add++)
        scanf("%lld",&j[add]);

    if(n%2==0)
    {
        sumt=0;
        for(add=1;add<n;add+=2)
        {
            sumt+=j[add];
            v[add]=1;
        }
        summax=sumt;
        for(add=n-1;add>0;add-=2)
        {
            sumt-=j[add];
            sumt+=j[add+1];
            v[add]=0;
            v[add+1]=1;
            if(summax<sumt&&v[x]) summax=sumt;
        }
        cout<<summax;
        return 0;
    }
    if(x%2==0)
    {
        sumt=0;
        for(add=2;add<=n;add+=2)
            sumt+=j[add];
        summax=sumt;
        for(add=2;add<x;add+=2)
        {
            sumt-=j[add];
            sumt+=j[add-1];
            if(sumt>summax) summax=sumt;
        }
        sumt=summax;
        for(add=n-1;add>x;add-=2)
        {
            sumt-=j[add];
            sumt+=j[add+1];
            if(sumt>summax) summax=sumt;
        }
        cout<<summax;
        return 0;
    }
    if(x!=1&&x!=n)
    {
        sumt=0;
        for(add=1;add<x;add+=2)
            sumt+=j[add];
        lmax=sumt;
        sumt=0;
        for(add=x+2;add<=n;add+=2)
            sumt+=j[add];
        rmax=sumt;

        lmm=find(1,x-2);
        rmm=find(x+2,n);
        if(lmm+rmax>rmm+lmax) summax=lmm+rmax;
        else summax=rmm+lmax;
        cout<<summax+j[x];
        return 0;
    }
    if(x==n)
        cout<<find(1,n-2)+j[x];
    else
        cout<<find(3,n)+j[x];

    return 0;
}


long long find(int left,int right)
{
    long long max(long long a,long long b);
    long long max3(long long a,long long b,long long c);

    long long n=right-left+1,add,ans;

    zz[left][0]=j[left];
    zz[left+1][1]=j[left+1];
    zz[left+2][0]=zz[left][0]+j[left+2];
    zz[left+2][2]=j[left+2];

    for(add=left+3;add<=right;add++)
    {
        if((add-left)%2==1)
            zz[add][1]=max(zz[add-3][0]+j[add],zz[add-2][1]+j[add]);
        else
        {
            zz[add][0]=zz[add-2][0]+j[add];
            zz[add][2]=max3(zz[add-4][0]+j[add],zz[add-3][1]+j[add],zz[add-2][2]+j[add]);
        }   
        /*cout<<add<<endl;
        for(add2=0;add2<3;add2++) cout<<zz[add][add2]<<" ";
        cout<<endl;*/
    }

    if(n==1) return 0;
    if(n==3) return max3(j[left],j[left+1],j[left+2]);

    ans=max3(zz[right-2][0],zz[right-1][1],zz[right][2]);
    return ans;
}

long long max(long long a,long long b)
{
    if(a>=b)
        return a;
        return b;
}

long long max3(long long a,long long b,long long c)
{
    if(a>=b&&a>=c)
        return a;
    if(b>=c)
        return b;
        return c;
}