T19216 毒瘤题 bitset求七维偏序 分块

T19216 毒瘤题 bitset求七维偏序 分块

​​‎

题目描述

题目名称是骗你的(^_^)

———————————————————————————————————

蒟蒻leoly最近天天被Icefox吊打网络流TvT

蒟蒻leoly最近天天被elijahqi喂-喂到撑TvT

蒟蒻leoly最近天天被VisJiao智商碾压TvT

———————————————————————————————————

一天，蒟蒻leoly实在忍无可忍，他想对Icefox、elijahqi、VisJiao进行打击报复！

蒟蒻leoly出了一题《毒瘤题》：

elijahqi有n个妹子，第i个妹子的魅力为ai，若妹子A的魅力不小于妹子B(A!=B)，则妹子A碾压妹子B

问每个妹子分别碾压了多少个妹子呢？

n<=10，1<=ai<=10^9

———————————————————————————————————

蒟蒻leoly的标程是状压DP：

枚举每个妹子，计算她的答案，f[s]=s集合中有多少个妹子符合要求，每次给s新加一个元素，蒟蒻leoly的标程的复杂度为O(2^n*n^2)

———————————————————————————————————

elijahqi看到这题后顿时觉得非常生气：我怎么可能只有10个妹子？！

于是elijahqi痛D了蒟蒻leoly，并把n改为50000（天津市中小学漂亮妹子总数），并随手AC了加强后的题

蒟蒻leoly看着自己的标程MLE+TLE，感觉实力被碾压，非常失落……

———————————————————————————————————

这时VisJiao来了：

elijahqi的妹子不光魅力高，同时她们的身材和容颜都非常漂亮！

如果一个妹子这三方面都不低于另一个妹子，这样才算得上是碾压！

然后VisJiao随手AC了他加强后的题

———————————————————————————————————

Icefox很快A完了今天bzoj的50道题，过来凑凑热闹：

外表不是最重要的，最重要的是内在！

elijahqi的妹子，气质和修养都是完美的！

如果一个妹子这五个方面都不低于另一个妹子，这样才能算碾压！

然后Icefox随手AC了他加强后的题

———————————————————————————————————

elijahqi刚刚D完了蒟蒻leoly，看到大家都在讨论自己的妹子，那必须要说两句：

既然我是理科男，那妹子的理科在我面前都是浮云！

我更喜欢文学素养更高的妹子！

一个妹子若想碾压另一个妹子，文学素养也必须碾压！

然后elijahqi想了又想，AC了他加强后的题

———————————————————————————————————

刚给NKOI出了一道智商题的VisJiao实在看不下去了：

你们讨论的这几个方面，我看都不如智商重要！

妹子们只有智商足够高，才能和我愉快地玩♂耍♀！

智商不够怎么行？！

然后VisJiao写了又写，AC了他加强后的题

———————————————————————————————————

蒟蒻leoly依然只会O(2^n*n^2)的状压DP，他想请你教教他，呜呜呜…… 输入输出格式

输入格式：

第一行2个正整数n、m，表示elijahqi共有n个妹子，你需要考虑她们的m个方面（魅力、身材、容颜、气质、修养、文学素养、智商）

接下来n行，每行m个整数描述一个妹子m个方面的优秀程度（数值越大越优秀）

输出格式：

输出n行，第i行表示第i个妹子碾压的妹子数量（不包括自己） 输入输出样例

输入样例#1： 复制

5 4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 5 4 4 5 4

输出样例#1： 复制

0 1 2 3 3

说明

测试点1：n=50000，m=1

测试点2：n=50000，m=2

测试点3：n=50000，m=3

测试点4：n=50000，m=3

测试点5：n=50000，m=4

测试点6：n=50000，m=4

测试点7：n=50000，m=5

测试点8：n=50000，m=5

测试点9：n=50000，m=6

测试点10：n=50000，m=7

妹子数少了elijahqi会生气，故所有数据n都是50000（天津市中小学漂亮妹子总数）

对于100%的数据：n=50000，1<=m<=7，1<=数值<=10^9

来自蒟蒻leoly的原题的算法提示：状压DP

题目描述都是骗人的elijahqi只是只辣鸡而已

内存太大开不下怎么搞 分块搞 先把块内的合并起来 然后对块做个前缀和 如果不是完整的块我需要暴力去算一算 最后统计答案的时候 如果最后一个的大小和我询问的一样大我也退出 然后暴力算一遍这个块 否则边界不好给

#include#include#define N 55000#define NN 225#includeusing namespace std;bitsets[NN][8],ans[8];int D,n,k,sa[N][8],L[NN][8],R[NN][8];inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x;}struct node{ int x,id; friend bool operator<(node a,node b){return a.x=NN) R[now][D]=i,++now,L[now][D]=i+1,s[now][D]=s[now-1][D]; }R[now][D]=n;L[0][D]=now; } for (int i=1;i<=n;++i){ for (int j=1;j<=k;++j) { ans[j].reset();int now=1; while(now<=L[0][D]) {if (a[j][R[now][j]].x>=sa[i][j]) break;else now++;} ans[j]=s[now-1][j]; for (int z=L[now][j];z<=R[now][j];++z){ if (a[j][z].x>sa[i][j]) break;else ans[j].set(a[j][z].id); } } for (int j=2;j<=k;++j) ans[1]&=ans[j];printf("%d\n",ans[1].count()-1); } return 0;}

高维kd-tree也可搞部分分

#include#include#include#define N 55000#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x;}int D,n,m,id,idx,root,ans[N],Ans;struct node1{ int d[7],id; int& operator[](int x){return d[x];} friend bool operator<(node1 a,node1 b){return a[D]>1;x=mid;D=dim;nth_element(point+l,point+mid,point+r+1);tree[x].left=tree[x].right=0; tree[x].x=point[mid];for (int i=0;imid) build(tree[x].right,mid+1,r,(dim+1)%m);update(x);//if (l==1&&r==1)printf("%d %d %d %d %d\n",tree[x].left,tree[x].right,l,r,tree[x].size);//printf("fds\n");}inline void insert1(int &x,int dim){ if (!x){x=idx;tree[x].left=tree[x].right=0;tree[x].x=point[idx]; for (int i=0;ib[i]) return 0; return 1;}inline bool judge1(int x){ for (int i=0;iP[i]) return 0; return 1;}inline bool judge2(int x){ for (int i=0;iP[i]) return 0; return 1;}inline void query(int x){ if (!x) return; if (check(tree[x].x,P)) ++Ans; if (tree[x].left){ if (judge1(tree[x].left)) Ans+=tree[tree[x].left].size; else if (judge2(tree[x].left)) query(tree[x].left); } if (tree[x].right){ if (judge1(tree[x].right)) Ans+=tree[tree[x].right].size; else if (judge2(tree[x].right)) query(tree[x].right); }}inline void print(int x){ if(tree[x].left) print(tree[x].left); for (int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。