今天在XJOJ爆了零 感觉很不爽
平常就知道bitset可以做很多事 这里做个整理
首先是floyd传递闭包啦
邻接矩阵是由一堆0和1组成的
然后如果满足了f[i][k] 那么 所有第k行为1的j都可以让f[i][j]=1
这样可以形象的写出一个N^2传递闭包
void floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) if(f[i][k]) f[i]|=f[k]; }
这个或运算在状压下完成 速度飞快
然后是XJOI的比赛题：
4维空间中有1个点集A，|A|=n,用(a,b,c,d)表示每个点。
共有m个询问，每次询问输入一个点(a,b,c,d)，求最大的S,其中S={p|p∈A且ap<=a,bp<=b,cp<=c,dp<=d}，输出|S|
数据范围<=30000 时限2s
这个看上去就很晕啊 我们必须要想办法降维
一个恶心的做法是排序降一维 树状数组降一维 用树套树再降两维？【我不会啊】
不过我们想一个暴力的做法
对于每个询问 离线处理 加入到数组中
对每一维按照这一维第一关键字 是否为询问为第二关键字（保证询问在后面）
然后我们可以维护一个01串 f[i]=0代表i这个点没有合适的询问对应 1代表有
然后每次遇到询问就统计01串中1的个数 加进去就好啦
这个正好可以使用bitset优化！！
神了！
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<bitset> using namespace std; const int N=31005; bitset<N>s[N],t; struct pos { double x[4]; int id,q; }a[N*2]; int p,n,m; bool cmp(pos a,pos b) { if(a.x[p]==b.x[p])return a.id;//把id放到前面 return a.x[p]<b.x[p]; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=0;j<4;j++) scanf("%lf",&a[i].x[j]); a[i].id=i; } scanf("%d",&m); for(int i=n+1;i<=n+m;i++) { for(int j=0;j<4;j++) scanf("%lf",&a[i].x[j]); a[i].q=i-n; } for(p=0;p<4;p++) { sort(a+1,a+n+m+1,cmp);t=0; for(int i=1;i<=n+m;i++) { if(a[i].q) { if(p!=0)s[a[i].q]&=t; else s[a[i].q]=t; } else t[a[i].id]=1; } } for(int i=1;i<=m;i++)printf("%d\n",s[i].count()); }
这个可以推广到多维的！！！
顺便附带一个bitset写的状压==简直思路清晰 妈妈再也不用担心我位运算写错啦
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<bitset> using namespace std; const int N=1<<10; int all[200],tot; int ok[200][200]; int cnt[200]; bitset<20>tep,t1,t2; int n,m; void init() { for(int i=0;i<(1<<n);i++) { tep=i;bool flag=1; for(int j=0;j<n;j++) if(tep[j]==1&&tep[j+1]==1){flag=0;break;} if(flag) all[++tot]=i,cnt[tot]=tep.count(); } for(int i=1;i<=tot;i++) for(int j=1;j<=tot;j++) { t1=all[i],t2=all[j]; bool flag=1; for(int k=0;k<n;k++) if(t1[k]==1) if(t2[k]||t2[k-1]||t2[k+1]){flag=0;break;} ok[i][j]=flag; } } long long f[15][200][100]; void dp() { for(int i=1;i<=tot;i++) f[1][i][cnt[i]]=1; for(int i=1;i<n;i++) for(int j=1;j<=tot;j++) for(int k=0;k<=m;k++) { for(int s=1;s<=tot;s++) if(ok[j][s]&&k+cnt[s]<=m)f[i+1][s][k+cnt[s]]+=f[i][j][k]; } long long ans=0; for(int i=1;i<=tot;i++) ans+=f[n][i][m]; printf("%lld\n",ans); } int main() { scanf("%d%d",&n,&m); init(); dp(); }
什么鬼！
什么恶心的做法啊显然我的是正解啊啊啊啊啊啊、
再说了是树套树降两维而不是平衡树啊！
咳lca已经写过高级数据结构的做法了少年你不来一发吗
我蒟蒻 并不会高级数据结构== orz
不不不神犇带我学可持久化啊
写完你也许会码力上升！
Orz Icebound
orz orz 蒟蒻icebound跪烂了
神犇求带啥是纳什均衡
神TM博弈
咋TM博弈
orz