[校內(nèi)互測]最長（dfs+hash）

2019-11-11 05:24:50

字體：大中小

供稿：網(wǎng)友

題目描述

這里寫圖片描述

題解

首先暴搜哪些種類出現(xiàn)了，判斷k 沒出現(xiàn)的種類將序列分成了若干部分，答案只可能在這些部分中產(chǎn)生假如一共有x種顏色，將前x-1種都賦一個(gè)hash值，然后將最后一個(gè)的hash值記為前面所有hash值的和的相反數(shù) 然后對序列求前綴和，前綴和相等的兩個(gè)點(diǎn)就對應(yīng)了一段合法的區(qū)間（所有的顏色出現(xiàn)次數(shù)一樣）然后對前綴和排序，相等的選最遠(yuǎn)的兩個(gè)點(diǎn) 測試的時(shí)候開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);