8月18日 2018百度之星复赛
题目链接:http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=827

1001 – 没有兄弟的舞会

思路:
一个很简单的贪心吧。。。对于每一个节点选出它最大和最小的儿子(注意还可以不选),然后在没有选的里面贪心找一个最大和最小值加入答案。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define MAXN 100005
#define LL long long
#define LB long double
#define INF 1e18
using namespace std;

int T, n, cnt, head[MAXN], maxson[MAXN], minson[MAXN], maxtag[MAXN], mintag[MAXN];
LL maxans, minans, w[MAXN], maxval[MAXN], minval[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs(int x, int fa)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs(to, x);
        if(w[to]>maxval[x]) maxson[x]=to, maxval[x]=w[to];
        if(w[to]<minval[x]) minson[x]=to, minval[x]=w[to];
    }
    maxans+=maxval[x];
    minans+=minval[x];
    maxtag[maxson[x]]=1;
    mintag[minson[x]]=1;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        cnt=maxans=minans=0;
        for(int i=0; i<MAXN-1; i++) head[i]=maxson[i]=minson[i]=maxval[i]=minval[i]=mintag[i]=maxtag[i]=0;
        LL mintemp=0, maxtemp=0;
        scanf("%d", &n);
        for(int i=2; i<=n; i++)
        {
            int fa;
            scanf("%d", &fa);
            addedge(fa, i);
            addedge(i, fa);
        }
        for(int i=1; i<=n; i++) scanf("%lld", &w[i]);
        dfs(1, 0);
        if(w[1]>0) maxtag[1]=1, maxans+=w[1];
        if(w[1]<0) mintag[1]=1, minans+=w[1];
        for(int i=1; i<=n; i++)
        {
            if(!mintag[i]) mintemp=min(mintemp, w[i]);
        }
        for(int i=n; i>=1; i--)
        {
            if(!maxtag[i]) maxtemp=max(maxtemp, w[i]);
        }
        printf("%lld %lld\n", maxans+maxtemp, minans+mintemp);
    }
}

1002 – 序列期望

思路:
一道蛮好的期望题。我们可以先枚举最大值$h$,然后计算最大值为$h$时对答案的贡献。最大值恰好为$h$是的贡献不方便计算,我们可以先计算最大值小于等于$h$和最大值小于$h$的期望,利用一个容斥相减就好了。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define MAXN 100005
#define LL long long
#define LB long double
#define INF 1e18
#define p 1000000007
using namespace std;

int T, n, l[MAXN], r[MAXN], tag, lmax, rmax;

LL x[MAXN], y[MAXN];

LL ksm(LL x, LL y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%p;
        y>>=1; x=(x*x)%p;
    }
    return sum;
}

LL cal(LL l, LL r) {return (l+r)*(r-l+1)/2%p;}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        lmax=rmax=0;
        LL up=0, down=1;
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d", &l[i], &r[i]);
            lmax=max(lmax, l[i]);
            rmax=max(rmax, r[i]);
        }
        for(int i=lmax; i<=rmax; i++)
        {
            tag=0;
            LL sum1=1, sum2=1;
            for(int j=1; j<=n; j++)
            {
                if(r[j]>=i) x[j]=1;
                else x[j]=i-r[j]+1;
                y[j]=i-l[j]+1;
            }
            for(int j=1; j<=n; j++) sum1=sum1*cal(x[j], y[j])%p;
            for(int j=1; j<=n; j++)
            {
                if(x[j]==1) sum2=(sum2*cal(x[j]+1, y[j]))%p;
                else sum2=(sum2*cal(x[j], y[j]))%p;
            }
            up=(up+sum1-sum2+p)%p;
        }
        for(int i=1; i<=n; i++) down=(down*(r[i]-l[i]+1))%p;
        printf("%lld\n", up*ksm(down, p-2)%p);
    }
}

1003 – 带劲的and和

思路:
首先观察式子,就可以发现我们可以对每一个联通块分开维护。对于每一个联通块里面的权值我们不难想到$v_i&v_j$可以按位来维护,对于每一位分别记录有多少个数字在这一位上出现过。然后$max(v_i, v_j)$可以比较巧妙的先将权值排序进行维护,从小到大依次按顺序计算贡献。大概的思路就是这样,详细的看代码吧(

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define MAXN 100005
#define LL long long
#define LB long double
#define INF 1e18
#define p 1000000007
using namespace std;

int T, n, m, cnt, top, sta[MAXN], head[MAXN], vis[MAXN];

LL ans, w[MAXN], num[50];


struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

bool CMP(int x, int y) {return w[x]<w[y];}

void dfs(int x)
{
    vis[x]=1; sta[++top]=x;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(vis[to]) continue;
        dfs(to);
    }
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        ans=cnt=0;
        for(int i=0; i<MAXN-1; i++) head[i]=vis[i]=0;
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++) scanf("%lld", &w[i]);
        for(int i=1; i<=m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            addedge(x, y);
            addedge(y, x);
        }
        for(int i=1; i<=n; i++)
        {
            if(vis[i]) continue;
            top=0;
            memset(num, 0, sizeof(num));
            dfs(i);
            sort(sta+1, sta+top+1, CMP);
            for(int j=1; j<=top; j++)
            {
                int temp=sta[j];
                for(int k=31; k>=0; k--)
                    if((w[temp]>>k)&1) ans=(ans+w[temp]*num[k]%p*(1LL<<k))%p, num[k]++;
            }
        }
        printf("%lld\n", ans);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注