【NOIP2013模拟11.5A组】游戏节目

Description

有三支队伍,分别是A,B,C。有n个游戏节目,玩第i个游戏,队伍A可以得到的分数是A[i],队伍B可以得到的分数是B[i],队伍C可以得到的分数是C[i]。由于时间有限,可能不是每个节目都能玩,于是节目主持人决定要从n个游戏节目里面挑选至少k个节目出来(被选中的节目不分次序),使得队伍A成为赢家。队伍A能成为赢家的条件是队伍A的总得分要比队伍B的总得分要高,同时也要比队伍C的总得分要高。节目主持人有多少种不同的选取方案?
Input
第一行,两个整数n和k。
第二行, n个整数,分别是A[1]、A[2]、A[3]…A[n]。
第三行, n个整数,分别是B[1]、B[2]、B[3]…B[n]。
第四行, n个整数,分别是C[1]、C[2]、C[3]…C[n]。
output
一个整数,表示不同的选取方案数量。
Sample Input
3 2
1 1 2
1 1 1
1 1 1
Sample Output
3
【样例解释】
方案一:选取节目1和节目3。
方案二:选取节目2和节目3。
方案三:选取节目1、节目2、节目3。

The solution

最近好懒 啊 ,直接套题解了。。。
o((>ω< ))o

分两步处理:

First:把问题简单化,假设没有k的限制,设求出来的方案总数是x。
Second:考虑k的限制,由于k<7,可以穷举n个节目取0个,n个节目取1个,n个节目取2个,n个节目取3个,n个节目取3个,n个节目取4个,n个节目取5个,n个节目取6个,穷举完这几种情况就可以知道哪些方案是合法的。而且

C340+C341+C342+C343+C344+C345+C346=1676116

没写错吧。。(⊙﹏⊙)b。。

装个B C=Combinations

也就是这个穷举不超过1676116次。设第二步的方案总数是y。

那么,最后应该输出的答案就是x – y。

第二步的方案数y可以搜索计算结果,下面重点讲讲第一步的方案数x如何求。

由于n最大是34,直接搜索会超时。

可以把n个节目平均分成两部分,
即第1至第n/2个节目归为第1部分,
第n/2+1个节目至第n个节目归为第2部分。

第1部分:显然最多只有17个节目,每个节目可以取或者不取,穷举这17个节目的所有情况,显然有2^17种取法,
对于每一种取法,
队伍A都有一个得分,设为scoreA,
队伍B也有一个得分scoreB
队伍C也有一个得分scoreC
不妨设difAB1 = scoreA – scoreB, difAC1 = scoreA – scoreC,
即每一种取法,都可以计算出一对值(difAB1,difAC1),

第2部分:显然最多也只有17个节目。每个节目可以取或者不取,穷举这17个节目的所有情况,显然也是有2^17种取法。
同理,对于每一种取法,
设difAB1 = scoreA – scoreB, difAC1 = scoreA – scoreC
,即每一种取法都可以计算出一对值(difAB2,difAC2),

显然,如果一个方案要成立,必须要同时满足:
difAB1 + difAB2 > 0 (即队伍A的总得分比队伍B的总得分高)
difAC1 + difAC2 > 0 (即队伍A的总得分比队伍C的总得分高)

于是,
问题转化为,枚举一对值(difAB1,difAC1),在第2部分里面查询有(difAB2,difAC2)使得同时满足
difAB1 + difAB2 > 0
difAC1 + difAC2 > 0

显然,对于第2部分,可以用树状数组或者线段树之类的数据结构进行保存,以备第1部分的查询所需。

由于分两步求答案,于是时间复杂度 =O( x + y = 2^17 * Log(2^17) + 1676116)

Code

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#define fo(i,a,b) for (int i=a;i<=b;i++)
#define fd(i,a,b) for (int i=a;i>=b;i--)
#define N 1048577
#define maxn 40 
#define INF 2147483647
using namespace std;
struct note
{
    long long x,y;
    bool mark;  
}ab[N];
struct note1
{
    long long ac,ab;
}a1[N];
struct note2
{
    long long ac,ab;
}a2[N];
int a[maxn],b[maxn],c[maxn],tree[N]; 
int n,k,t1=0,t2=0,t=0;
long long x=0,y=0,j=1;
long long tab=0,tac=0;

bool cmp1(note1 a,note1 b) {
  return a.ac<b.ac;}
bool cmp2(note2 a,note2 b) {
  return a.ac>b.ac;}
bool cmp3(note a,note b) {
  return a.x<b.x;}

void dfs1(int x,int z,long long sab,long long sac)
{
    if (x>=k) return;
    if (sab>0 && sac>0) y++;
    fo(i,z+1,n) dfs1(x+1,i,sab+a[i]-b[i],sac+a[i]-c[i]);    
}
void dfs2(int x)
{
    a1[++t1].ab=tab;
    a1[t1].ac=tac;
    fo(i,x+1,n/2)
    {
        tab+=a[i]-b[i];
        tac+=a[i]-c[i];
        dfs2(i);
        tab-=(a[i]-b[i]);
        tac-=(a[i]-c[i]);   
    }
}
void dfs3(int x)
{
    a2[++t2].ab=tab;
    a2[t2].ac=tac;
    fo(i,x+1,n)
    {
        tab+=a[i]-b[i];
        tac+=a[i]-c[i];
        dfs3(i);
        tab-=(a[i]-b[i]);
        tac-=(a[i]-c[i]);
    }
}
void change(int v,int l,int r)
{
    if (l==r)
    {
        tree[v]++;
        return;
    }
    int mid=(l+r)>>1;
    if (a2[j].ab<=mid) change(v*2,l,mid);
    else change(v*2+1,mid+1,r);
    tree[v]=tree[v*2]+tree[v*2+1];
}
int get(int v,int l,int r,int x,int y)
{
    if (!y) return 0;
    if (l==x && r==y) return tree[v];
    int mid=(l+r)>>1;
    if (y<=mid) return get(v*2,l,mid,x,y);
    else if (x>mid) return get(v*2+1,mid+1,r,x,y);
    else return get(v*2,l,mid,x,mid)+get(v*2+1,mid+1,r,mid+1,y);
}

int main()
{
    freopen("show.in","r",stdin);
    freopen("show.out","w",stdout);
    scanf("%d%d",&n,&k);
    fo(i,1,n) scanf("%d",&a[i]);
    fo(i,1,n) scanf("%d",&b[i]);
    fo(i,1,n) scanf("%d",&c[i]);
    dfs1(0,0,0,0);
    dfs2(0);
    dfs3(n/2);
    fo(i,1,t1) ab[i].x=a1[i].ab,ab[i].y=i,ab[i].mark=0;
    fo(i,t1+1,t1+t2) ab[i].x=-a2[i-t1].ab,ab[i].y=i-t1,ab[i].mark=1;
    sort(ab+1,ab+t1+t2+1,cmp3);
    ab[0].x=-INF;
    fo(i,1,t1+t2)
    {
        if (ab[i].x!=ab[i-1].x) t++;
        if (!ab[i].mark) a1[ab[i].y].ab=t;
        else a2[ab[i].y].ab=t;
    }
    sort(a1+1,a1+1+t1,cmp1);
    sort(a2+1,a2+1+t2,cmp2);
    fo(i,1,t1)
    {
        while (j<=t2 && a1[i].ac+a2[j].ac>0) change(1,1,t),j++;
        x+=get(1,1,t,1,a1[i].ab-1);
    }
    printf("%lld\n",x-y);
    return 0;
}
    原文作者:HownoneHe
    原文地址: https://blog.csdn.net/HownoneHe/article/details/51889600
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞