[校内互测]最长（dfs+hash）

2019-11-11 05:24:50

字体：大中小

来源：转载

供稿：网友

题目描述

这里写图片描述

题解

首先暴搜哪些种类出现了，判断k 没出现的种类将序列分成了若干部分，答案只可能在这些部分中产生假如一共有x种颜色，将前x-1种都赋一个hash值，然后将最后一个的hash值记为前面所有hash值的和的相反数然后对序列求前缀和，前缀和相等的两个点就对应了一段合法的区间（所有的颜色出现次数一样）然后对前缀和排序，相等的选最远的两个点测试的时候开O2跑得还是很快的

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>using namespace std;#define N 100005#define UNLL long longstruct data{int x,ty;}p[N];struct data2{int x;UNLL ty;}q[N];int n,k,now,Max,ans;int ch[10],ba[N];UNLL val[10],s[N];bool app[10],flag[10];int cmp2(data2 a,data2 b){ return a.ty<b.ty||a.ty==b.ty&&a.x<b.x;}void solve(int x,int y){ q[x].x=x; for (int i=x;i<=y;++i) s[i]=0; q[x].x=x;q[x].ty=0; for (int i=x+1;i<y;++i) { s[i]=s[i-1]+val[p[i].ty]; q[i].x=i;q[i].ty=s[i]; } sort(q+x,q+y,cmp2); int l=x,r=x; while (l<y) { while (r<y&&q[r].ty==q[l].ty) ++r; if (q[r-1].x>=q[l].x+1) ans=max(ans,p[q[r-1].x].x-p[q[l].x+1].x); l=r; }}void check(){ for (int i=1;i<=Max;++i) flag[i]=0; int cnt=0; for (int i=1;i<=n;++i) { if (!ch[p[i].ty]) ba[++cnt]=i; else flag[p[i].ty]=1; } UNLL sz=0,lastval=0; int last=0; for (int i=1;i<=Max;++i) if (flag[i]) { UNLL aa=rand()*rand();UNLL bb=rand()*rand(); val[i]=aa*bb; lastval=sz;sz+=val[i];last=i; } val[last]=-lastval; for (int i=2;i<=cnt;++i) { if (ba[i]-ba[i-1]<=1) continue; solve(ba[i-1],ba[i]); } if (!cnt) solve(0,n+1); else { if (ba[1]-1>1) solve(0,ba[1]); if (n+1-ba[cnt]>1) solve(ba[cnt],n+1); }}void dfs(int dep){ if (Max-dep+1+now<k) return; if (dep==Max+1) { check(); return; } if (!app[dep]) dfs(dep+1); else for (int i=0;i<=1;++i) { ch[dep]=i; if (i==1) ++now; dfs(dep+1); if (i==1) --now; }}int cmp(data a,data b){ return a.x<b.x;}int main(){ freopen("long.in","r",stdin); freopen("long.out","w",stdout); scanf("%d%d",&n,&k); srand(time(0)); for (int i=1;i<=n;++i) { scanf("%d%d",&p[i].x,&p[i].ty); app[p[i].ty]=1; Max=max(Max,p[i].ty); } sort(p+1,p+n+1,cmp); dfs(1); PRintf("%d/n",ans);}

上一篇：[BZOJ3144][Hnoi2013]切糕（最小割）

下一篇：Socket多客户端

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注