【折半搜索·二维偏序】jzoj3512游戏节目 纪中集训提高B组

节目 纪中集训提高B组"/>

【折半搜索·二维偏序】jzoj3512游戏节目 纪中集训提高B组

3512【NOIP2013模拟11.5A组】游戏节目(show)
(File IO): input:show.in output:show.out
Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits

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。

Data Constraint

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

n = 20 n=20 n=20有40pts的暴力分，这个就不说了。
100分做法的话，首先注意到 k k k的范围非常友好，所以正难则反一下，我们可以用总的满足条件的方案数减去选的节目少于 k k k的方案数就是答案了嘛。求选的节目少于 k k k的方案数用40pts的暴力的方法就可以了。
然后考虑求全部的方案数。接下来我们再看到 n n n，这个 n n n的范围是有它的道理的，你看它既不是很大，但是又不是小到连暴力就可以水过，这充分地体现了OI的有趣之处（怎么又开始哲学 ）。
你看它除以2的话就可以暴力了，所以考虑折半搜索。
问了一下老师哪种题用折半搜索比较合适的，老师说其实不太常用，就是范围看起来像这道题这个样子的，还有就是合并答案不是很复杂的（其实我觉得这道题合并答案的部分最难啊喂），有的分成的两半还不一定用同一种算法，有的还不一定从中间分开，要看题目的一些性质。（怎么感觉跟分治很像咧），最常见的一类就是meet in middle那种（挖坑待填）。
折半搜索，每一半的复杂度为 2 n 2 2^{\frac{n}{2}} 22n​（上取整还是下取整这个不重要的啦 ，实现的时候随便搞一下反正能包含所有节目就行）
下面考虑合并答案：
假设左边的一种组合节目的三个权值之和分别为 A i , B i , C i A_i,B_i,C_i Ai​,Bi​,Ci​，左边的为 A j , B j , C j A_j,B_j,C_j Aj​,Bj​,Cj​
然后合并的时候要保证合法，即为：
A i + A j &gt; B i + B j A_i+A_j&gt;B_i+B_j Ai​+Aj​>Bi​+Bj​
A i + A j &gt; C i + C j A_i+A_j&gt;C_i+C_j Ai​+Aj​>Ci​+Cj​
然后套路一波，我们要把下标一样的数放到一起，即为：
A i − B j &gt; B j − A j A_i-B_j&gt;B_j-A_j Ai​−Bj​>Bj​−Aj​
A i − C j &gt; C j − A j A_i-C_j&gt;C_j-A_j Ai​−Cj​>Cj​−Aj​
简化一下，每一个下标就是两个关键字：
x i &gt; x j x_i&gt;x_j xi​>xj​
y i &gt; y j y_i&gt;y_j yi​>yj​
（这好像就是一个二维偏序问题）
然后按所有的 x x x从小到大排序一下。
然后遍历它，这样可以保证 x x x的大小关系， y y y的话，就再用数据结构维护一下。
每一次枚举到一个点，如果它是 j j j集合的，就把它塞进去，如果是 i i i集合的，就查找（这里我们要求严格小于要注意了）。
这个数据结构我们可以用权值线段树。（因为值域比较大，所以我们可以动态开点）
或者先离散化一下（对 y y y， x x x就不用了，因为它不需要被塞到数据结构里面），再做数据结构的操作，这样子的话树状数组应该也是可以的。

再丢一篇讲解二维偏序的博客，个人觉得讲得很好：
二维偏序

这道题如果没有听评讲的话，确实自己也想不到这么深入呢，虽然觉得范围有点什么猫腻，但是还是只会爆搜呢。

由于我太菜了，连正常的线段树都不能熟练地玩，更不用说权值线段树了，所以我的做法就是离散化+树状数组。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<cstdlib>
using namespace std;
#define N 40
#define M 1310780*3//2^17=131072
#define ll long long
#define INF 0x3f3f3f3f
inline int rd()
{int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
int n,k,a[N],b[N],c[N],mid/*折半搜索*/,cnt/*离散化编号*/;
struct node{ll x,y;int id;//离散化编号bool f;//在前一半还是后一半 
}pt[M];
ll tot,ans1,ans2;
ll tree[M];//树状数组本体 
bool cmp1(node p,node q)
{return p.y<q.y;
}
bool cmp2(node p,node q)
{if(p.x==q.x) return p.f<q.f;//因为要严格小于 所以先查找再插入return p.x<q.x;
}
void dfs(int i,ll A,ll B,ll C,int chosen)
{if(chosen>=k) return ;if(i>n) {if(A>B&&A>C)ans1++;return ;}dfs(i+1,A,B,C,chosen);dfs(i+1,A+a[i],B+b[i],C+c[i],chosen+1);
}
void dfs1(int i,ll A,ll B,ll C)
{if(i>mid) {pt[++tot].x=A-B,pt[tot].y=A-C,pt[tot].f=0;return ;}dfs1(i+1,A,B,C);dfs1(i+1,A+a[i],B+b[i],C+c[i]);
}
void dfs2(int i,ll A,ll B,ll C)
{if(i>n) {pt[++tot].x=B-A,pt[tot].y=C-A,pt[tot].f=1;return;}dfs2(i+1,A,B,C);dfs2(i+1,A+a[i],B+b[i],C+c[i]);
}
//----树状数组
int lowbit(int x)
{return x&(-x);
}
ll query(int x)
{ll ans=0;for(;x;x-=lowbit(x))ans+=tree[x];return ans;
}
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);n=rd(),k=rd();mid=(1+n)>>1;for(int i=1;i<=n;i++) a[i]=rd();for(int i=1;i<=n;i++) b[i]=rd();for(int i=1;i<=n;i++) c[i]=rd();dfs(1,0,0,0,0);//搜小于k dfs1(1,0,0,0);//前一半dfs2(mid+1,0,0,0);//后一半sort(pt+1,pt+tot+1,cmp1);pt[1].id=1,cnt=1;for(int i=2;i<=tot;i++)//离散化y {if(pt[i].y!=pt[i-1].y)cnt++;pt[i].id=cnt;}sort(pt+1,pt+1+tot,cmp2);for(int i=1;i<=tot;i++){if(pt[i].f==1)update(pt[i].id,1);else ans2+=query(pt[i].id-1);//严格小于 }printf("%lld\n",ans2-ans1);return 0;
}

以下是写丑了的暴力程序：
（我的这种写法必须要在i>n之后才能统计答案，因为我是枚举每个位置选还是不选，所以在i>n之后才是所有的排列，如果在中间就开始统计答案，则会造成重复（在中间就满足了chosen>=k的条件，在后面的枚举的时候都不选，则就重复了之前的那个情况））

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<cstdlib>
using namespace std;
#define N 40
#define ll long long
#define INF 0x3f3f3f3f
#define MOD 1000000000
inline int rd()
{int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
int n,k,a[N],b[N],c[N];
ll ans;
inline void dfs(int i,ll A,ll B,ll C,int chosen)
{if(chosen>=k){if(A>B&&A>C)ans++;}if(i>n)return ;dfs(i+1,A,B,C,chosen);dfs(i+1,A+a[i],B+b[i],C+c[i],chosen+1);return ;
}
int main()
{freopen("show.in","r",stdin);freopen("show.out","w",stdout);n=rd(),k=rd();for(int i=1;i<=n;i++)a[i]=rd();for(int i=1;i<=n;i++)b[i]=rd();for(int i=1;i<=n;i++)c[i]=rd();dfs(1,0,0,0,0);printf("%lld\n",ans);return 0;
}

以下是正常的暴力程序：

关于为什么要花时间调暴力：在正解想不出来的情况下（尤其是像我这样菜的选手），暴力是一种很好的骗分手段（如果这次考试暴力没有写挂的话，15pts->40pts 总分165pts->190pts rank:53->38）；在想出来正解的时候，可以用暴力对拍看自己有没有写挂，所以我觉得能够正确并快速地写出暴力是一种不可或缺的能力。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<cstdlib>
using namespace std;
#define N 40
#define ll long long
#define INF 0x3f3f3f3f
#define MOD 1000000000
inline int rd()
{int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
int n,k,a[N],b[N],c[N];
ll ans;
void dfs(int i,ll A,ll B,ll C,int chosen)
{	if(i>n){if(chosen>=k){if(A>B&&A>C)ans++;}return ;}dfs(i+1,A,B,C,chosen);dfs(i+1,A+a[i],B+b[i],C+c[i],chosen+1);return ;
}
int main()
{freopen("show.in","r",stdin);freopen("show.out","w",stdout);n=rd(),k=rd();for(int i=1;i<=n;i++)a[i]=rd();for(int i=1;i<=n;i++)b[i]=rd();for(int i=1;i<=n;i++)c[i]=rd();//for(int i=1;i<=n;i++)//	printf("%d ",b[i]);dfs(1,0,0,0,0);printf("%lld\n",ans);return 0;
}

附：
jzoj官方题解：

分两步处理：
第一步：把问题简单化，假设没有k的限制，设求出来的方案总数是x。
第二步：考虑k的限制，由于k<7，可以穷举n个节目取0个，n个节目取1个，n个节目取2个，n个节目取3个，n个节目取3个，n个节目取4个，n个节目取5个，n个节目取6个，穷举完这几种情况就可以知道哪些方案是合法的。而且Combinations(34,0) + Combinations(34,1) + Combinations(34,2) + Combinations(34,3) + Combinations(34,4) + Combinations(34,5) + Combinations(34,6) = 1676116。
也就是这个穷举不超过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部分的查询所需。

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