【树状数组or线段树

线段树"/>

【树状数组or线段树

前言

又是一道奇奇怪怪的题目（信竞就没有不奇怪的题目）

题目

Time Limits: 1000 ms  Memory Limits: 262144 KB 

有三支队伍，分别是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 21 1 21 1 11 1 1

Sample Output

3

【样例解释】     

方案一：选取节目1和节目3。     

方案二：选取节目2和节目3。     

方案三：选取节目1、节目2、节目3。

【数据范围】

对于40%数据，2 <= n <= 20。

对于100%数据，2 <= n <= 34,  1 <= k <= min(n,7),  1 <=A[i], B[i], C[i]<= 10^9。

分析

特别鸣谢：

最开始自己“灵光一现”，想到了“状压”，于是50行以内解决本题，后来反应过来n<=34，非常大... ...

考虑按题意要求的来计算的话，最大总数会有，这是非常大的，不好操作

于是反面考虑：答案 = 总方案数 - 节目数不满足K的方案数 ，

其中节目数K最大为7，那么由排列组合公式：，可见穷举最多1676116次，那就可以暴力计算

接下来考虑总方案数如何计算，n最大为34，暴力枚举的话时间复杂度很高，所以采用类似“CDQ分治”的思想

将n=34分为17和17进行分治，就可以暴力枚举了，每一半的复杂度为，这样的操作 好像被 称为【折半搜索】

于是将穷举后所有的状态数分为了两组，称为A组与B组，暴力枚举后考虑如何合并、得出答案

设A组的一种节目状态为，B组，

，，

，，

可得不等式：

 并且 （）

转化为： 并且 （）

将不等式看做： 并且 ，那么问题最后就转化为了一个【二维偏序】的问题（详情：二维偏序）

只要按其中一个关键字排序，另一个先离散化后用树状数组或线段树统计组合方法数即可

我又一次为“人类的智慧”所震惊qwq... ...

状压暴力40分代码

本来40分，考试时数组开小了，20分飞了，QAQ

发现自己对状压已经有一定的理解了，至少能自己简单用一用qwq

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;//记得开ll 
const int MAXN=1e7;
ll a[34+5],b[34+5],c[34+5];
ll sa[MAXN+5],sb[MAXN+5],sc[MAXN+5]; 
ll pre[34+5];
ll n,k,ans;
int main()
{//freopen("show.in","r",stdin);//freopen("show.out","w",stdout);scanf("%lld%lld",&n,&k);//至少挑k个节目 for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++)scanf("%lld",&b[i]);for(int i=1;i<=n;i++)scanf("%lld",&c[i]);	pre[1]=1;for(int i=2;i<=n+1;i++)pre[i]=pre[i-1]*2;for(ll S=0;S<=(1<<n)-1;S++){ll cnt=0;for(int i=1;i<=n;i++)if(1<<(i-1)&S)//第i位是1cnt++;for(int i=1;i<=n;i++)if(!(1<<(i-1)&S))//枚举一个是0的位 {sa[S+pre[i]]=sa[S]+a[i];sb[S+pre[i]]=sb[S]+b[i];sc[S+pre[i]]=sc[S]+c[i];}if(cnt>=k&&sa[S]>sb[S]&&sa[S]>sc[S])ans++;}printf("%lld",ans);return 0;
}

AC代码

这里有个很智慧的同学：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;//记得开ll 
const int MAXN=34,MAXM=1500000*3;
ll a[MAXN+5],b[MAXN+5],c[MAXN+5];
ll tree[MAXM+5];
ll n,k,mid,tot,cnt;
ll ans1,ans2;
struct node
{ll x,y;int f,id;//f=0:在前一半,f=1:在后一半 
}p[MAXM+5];
bool cmp1(node a,node b)
{return a.y<b.y;
}
bool cmp2(node a,node b)
{if(a.x==b.x)return a.f<b.f;return a.x<b.x;
}
void dfs(int id,ll A,ll B,ll C,int cnt)
{if(cnt>=k)return ;if(id>n){if(A>B&&A>C)ans1++;return ;}dfs(id+1,A,B,C,cnt);dfs(id+1,A+a[id],B+b[id],C+c[id],cnt+1);
}
void dfs1(int id,ll A,ll B,ll C)
{if(id>mid){ll x=A-B,y=A-C;p[++tot].x=x,p[tot].y=y,p[tot].f=0;return ;}dfs1(id+1,A,B,C);dfs1(id+1,A+a[id],B+b[id],C+c[id]);
}
void dfs2(int id,ll A,ll B,ll C)
{if(id>n){ll x=B-A,y=C-A;p[++tot].x=x,p[tot].y=y,p[tot].f=1;return ;}dfs2(id+1,A,B,C);dfs2(id+1,A+a[id],B+b[id],C+c[id]);
}
int lowbit(int x)
{return x&(-x);
}
ll query(int x)
{ll ret=0;for(;x;x-=lowbit(x))ret+=tree[x];return ret;
}
void update(int x,ll val)
{for(;x<=cnt;x+=lowbit(x))tree[x]+=val;return ;
}
int main()
{//freopen("show.in","r",stdin);//freopen("show.out","w",stdout);scanf("%lld%lld",&n,&k);//至少挑k个节目 mid=(n+1)/2;for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++)scanf("%lld",&b[i]);for(int i=1;i<=n;i++)scanf("%lld",&c[i]);	dfs(1,0,0,0,0);//得出小于k的答案 dfs1(1,0,0,0);//搜索前一半 dfs2(mid+1,0,0,0);//搜索后一半sort(p+1,p+tot+1,cmp1); p[1].id=1,cnt=1;for(int i=2;i<=tot;i++)//将y值离散化 {if(p[i].y!=p[i-1].y)cnt++;p[i].id=cnt;}sort(p+1,p+tot+1,cmp2);for(int i=1;i<=tot;i++){if(p[i].f==1)//B组的点直接加入树状数组update(p[i].id,1);else//遇到A组的点，统计答案ans2+=query(p[i].id-1);//严格小于}printf("%lld",ans2-ans1);return 0;
}