多校 2013 5

n 个点 m条边

然后n个点权 m条边边权

A B 2 个人

每个人每次取一个点都让自己分数大如果一个人同时取到了一条边的2点那么这条边权也是他的

具体的做法是把边权拆成一半然后分给2个点然后按点权排序如果变不在同一个人身上那么会被减掉

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

using namespace std;

typedef long long ll;

#define MAXN 100010

double z[MAXN];
bool cmp(double a,double b)
{
    return a>b;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%lf",&z[i]);
        double a,b;
        a=b=0;
        for(int i=1;i<=m;i++)
        {
            int u,v;
            double w;
            scanf("%d%d%lf",&u,&v,&w);
            z[u]+=w/2;
            z[v]+=w/2;
        }
        sort(z+1,z+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
            if(i&1)
                a=a+z[i];
            else
                b=b+z[i];
        }
        printf("%.0lf
",a-b);
    }
    return 0;
}

View Code

n个人 m

然后n个人的分数老师已经知道了n个人分数的和 %m 然后你可以抹去段分数但是留下来的分数的和%m要和原来一样

前缀和记录余数的位置 0!!!

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

using namespace std;

#define MAXN 100010
#define inf  1e12+7
typedef __int64 ll;

int z[MAXN];
int sum[MAXN];
int pr[MAXN];

int main()
{

    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&z[i]);
            z[i]=(z[i]%m+m)%m;
            sum[i]=(sum[i-1]+z[i])%m;
        }
        int mx=0;
        memset(pr,-1,sizeof(pr));
        pr[0]=0;
        for(int i=1;i<=n;i++)
        {
            if(pr[sum[i]]==-1)
                pr[sum[i]]=i;
            else
            {
                mx=max(mx,i-pr[sum[i]]);
            }
        }
        printf("%d
",mx);
    }
    return 0;
}

View Code

n 然后n+1 个数

n 个运算符 | & ^

这个运算符消失的概率

求数字的期望

枚举二进制每一位求期望

q 是1的概率

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

using namespace std;


#define MAXN 210
int z[MAXN];
char s[MAXN][6];
double p[MAXN];

int main()
{
    int n,ca;
    ca=1;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<=n;i++)
            scanf("%d",&z[i]);
        for(int i=1;i<=n;i++)
            scanf("%s",s[i]);
        for(int i=1;i<=n;i++)
            scanf("%lf",&p[i]);
        double ans=0;
        for(int i=0;i<=20;i++)
        {
            double q;
            if(z[0]&(1<<i))
                q=1;
            else
                q=0;
            for(int j=1;j<=n;j++)
            {
                if(z[j]&(1<<i))
                {
                    if(s[j][0]=='&')
                        continue;
                    else if(s[j][0]=='|')
                        q=q+(1-q)*(1-p[j]);
                    else
                        q=q*p[j]+(1-q)*(1-p[j]);
                }
                else
                {
                    if(s[j][0]=='&')
                        q=q*p[j];
                }

            }
            ans=ans+q*(1<<i);
        }

        printf("Case %d:
%.6lf
",ca++,ans);
    }
    return 0;
}

View Code