ZigZagK的博客 - 2019年2月
type: channel
link: https://zigzagk.top/2019/02/
description: Never give up fighting!
items: [DP]LOJ6501(雅礼集训 2018 Day4)【Cube】题解
items: [DFS树+线性基+复杂度分析]UOJ138(UER #3)【开学前的涂鸦】题解
items: [二分+随机+斯坦纳树+思维]LOJ2977(THUSCH 2017)【巧克力】题解
items: [FWT+快速乘]Codeforces453D【Little Pony and Elements of Harmony】题解
items: [斯坦纳树+随机]HHHOJ200【稗田的梦中之梦】题解
items: [斯坦纳树]BZOJ2595(Wc2008)【游览计划】题解
items: [期望的线性性+概率DP]TopCoder【RockPaperScissors】题解
items: [离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
items: [霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解
items: [单调栈+DP]Codeforces1131G【Most Dangerous Shark】题解

[DP]LOJ6501(雅礼集训 2018 Day4)【Cube】题解
type: item
date: 2019-02-28T22:00:00+08:00
description: 题目概述定义 $0$ 维基础图形为点，$1$ 维基础图形为边，$2$ 维基础图形是正方形，$3$ 维基础图形是正方体，以此类推。问 $n$ 维基础图形由多少个 $m$ 维基础图形组成。解题报告感觉这题海星。应该不可能想象出 $4$ 维基础图形长什么样吧QAQ，所以找规律就只能在 $3$ 维之内找找的样子……先定义个 $f_{m}(n)$ 表示答案，然后考虑下怎么递推，在三维里找找规律，可以想到是这样的：$$ f_m(n)=2f_{m}(n-1)+f_{m-1}(n-1) $$就是先把 $n-1$ 维基础图形复制一遍，再把这两个 $n-1$ 维基础图形拼起来，此时降维了，所以需要的是 $m-1$ 维基础图形拼成的 $n-1$ 维基础图形。但是这样是 $O(nm)$ 的，需要化简，所以从 $m=0$ 开始推下式子：$$ f_{0}(n)=2^n\\ \begin{aligned} f_{1}(n)&=2f_1(n-1)+f_0(n-1)=2f_1(n-1)+2^{n-1}\\ &=2[2f_1(n-2)+f_0(n-2)]+2^{n-1}\\ &=4f_1(n-2)+2^{n-1}+2^{n-1}\\ &=\cdots=n2^{n-1} \end{aligned}\\ \begin{aligned} f_{2}(n)&=2f_2(n-1)+f_1(n-1)=2f_2(n-1)+(n-1)2^{n-2}\\ &=2[2f_2(n-2)+f_1(n-2)]+(n-1)2^{n-2}\\ &=4f_2(n-2)+(n-2)2^{n-2}+(n-1)2^{n-2}\\ &=\cdots={n(n-1)\over2}2^{n-2} \end{aligned}\\ \cdots $$很容易发现后面是 $2^{n-m}​$ ，前面的系数也很熟悉，是 $n\choose m$（因为 $\sum_{i=m-1}^{n-1}{i\choose m-1}={n\choose m}​$ ）。那么答案就是 $f_{m}(n)={n\choose m}2^{n-m}​$ 。示例程序#include<cstdio> using namespace std; typedef long long LL; const int maxn=100000,MOD=998244353; int te,n,m,fac[maxn+5],INV[maxn+5],pw[maxn+5]; inline void Make(int n){ INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD; fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i-1]*INV[i]%MOD; pw[0]=1;for (int i=1;i<=n;i++) pw[i]=(pw[i-1]<<1)%MOD; } #define C(x,y) ((x)<(y)?0:(LL)fac[x]*INV[y]%MOD*INV[(x)-(y)]%MOD) int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); for (Make(maxn),scanf("%d",&te);te;te--) scanf("%d%d",&n,&m),printf("%lld\n",(LL)C(n,m)*pw[n-m]%MOD);return 0; }

[DFS树+线性基+复杂度分析]UOJ138(UER #3)【开学前的涂鸦】题解
type: item
date: 2019-02-28T20:54:00+08:00
description: 题目概述原来有 $n​$ 个点的一棵树，现在加进了 $K​$ 条边。问多少种方案删边使得图依然连通。解题报告非正解警告……接下来要讲的是原题解中的算法七，不过这个解法能艹标程（度教rank1，翰爷rank2，Orz）。图中删边让我们想到DZY Loves Chinese II，我们可以给新加进来的边随机个权值（或者直接给 $2^i​$ ，由于 $K​$ 小，这样可以保证不会出错），处理出每条边被新边覆盖的权值异或和。由于不能出现线性相关，所以每种权值只能选或不选，那么爆枚每种权值选不选，做线性基判断是否线性相关（可以剪枝），如果合法就统计答案。但是权值可能有 $n​$ 种，这不就凉了？实际上只要考虑这 $K​$ 条边有关的点建出来的虚树（只有 $4K​$ 个点），虚树上的边对应的路径权值肯定相同，所以最多只有 $4K​$ 种不同的权值。但是 $4K$ 好像有点崩？能不能想办法搞少点？如果所有新加进来的边都是返祖边的话，虚树节点就只有 $3K$ 个了，这样权值也会减少到 $3K$（证明在后面）。仔细一想发现新加的边实际上和原来的树边没有任何区别……所以可以随便拿一棵DFS树出来，这样非树边就都是返祖边了。那么复杂度是 $O(2^{3K}K)​$ ，显然过不了……但是因为线性相关那道剪枝非常强力，就跑得飞快QAQ。2019.3.1UPD：法老提供了一种证法，在非树边 $(x,y),dep_x>dep_y$ 的 $x$ 后面加一个儿子 $y'$ ，然后把非树边改成 $(y',y)$ ，这样再做虚树，点数依然是 $3K$ ，但是不需要统计非树边的边权（非树边的边权一定在新加的边中出现过），所以边权数量就是 $3K$ 。示例程序#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int maxn=100000,maxk=10,maxm=maxn+maxk,MOD=998244353; int n,m,K,fa[maxn+5],val[maxm+5],cnt[maxm+5],ans;bool vis[maxn+5]; int E,lnk[maxn+5],frm[(maxm<<1)+5],son[(maxm<<1)+5],nxt[(maxm<<1)+5]; struct data {int s[maxk+5];} S; #define Add(x,y) (son[E]=(y),frm[E]=(x),nxt[E]=lnk[x],lnk[x]=E++) void Dfs(int x,int pre=-1){ for (int j=(vis[x]=true,fa[x]=pre,lnk[x]);~j;j=nxt[j]) if ((j^1)!=pre) if (!vis[son[j]]) Dfs(son[j],j); else if (!val[j>>1]) for (int k=(K++,j);k!=fa[son[j]];k=fa[frm[k]]) val[k>>1]^=1<<K-1; } inline bool Insert(data &a,int x){ for (int j=maxk;~j&&x;j--) if (x>>j&1) if (!a.s[j]) return a.s[j]=x,true; else x^=a.s[j];return false; } inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} void Solve(int st,data s,int now=1){ if (st>m) return AMOD(ans,now);Solve(st+1,s,now);if (!Insert(s,val[st])) return; Solve(st+1,s,(LL)now*cnt[st]%MOD); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d",&n,&m);m+=n-1;memset(lnk,255,sizeof(lnk)); for (int i=0,x,y;i<m;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);Dfs(1);sort(val,val+m); int tem=m;cnt[m=0]=1;for (int i=1;i<tem;i++) val[i]>val[i-1]?(val[++m]=val[i],cnt[m]=…

[二分+随机+斯坦纳树+思维]LOJ2977(THUSCH 2017)【巧克力】题解
type: item
date: 2019-02-28T09:52:55+08:00
description: 题目概述给出一个 $n\times m$ 的巧克力，每个位置有形状和美味值，求一个个数最小的连通块满足形状数 $\ge K$ ，且在个数最小的前提下，美味值的中位数也要最小。解题报告人类智慧题QAQ，首先第一问和这道题是一样的，用随机+斯坦纳树就可以解决。但是第二问是什么鬼？首先我们可以二分中位数，然后就可以把美味值分成两种，大于中位数和小于等于中位数。由于先要满足个数最小，所以我们可以这样……将小于等于中位数的值设为 $9999$ ，大于中位数的设为 $10001$ ……因为 $K$ 个不同形状连通，至多需要选 $5(233+233)\approx2500$ 个（肯定比这个值小），只要把新的权值设置的比 $2500$ 大，权值最小就等价于个数最少了！ 而且这样我们还可以通过权值 $ans$ 来求出个数 $\lfloor{ans+2500\over10000}\rfloor$ ，从而进行二分验证：满足的条件是小于等于中位数的个数大于等于大于中位数的个数，即 $ans\le 10000\lfloor{ans+2500\over10000}\rfloor$ 。示例程序#include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; const int maxn=233,maxk=5,maxc=maxn*maxn,maxs=1<<maxk,INF=1061109567; const int dif[4][2]={{-1,0},{1,0},{0,1},{0,-1}}; int te,n,m,K,c[maxn+5][maxn+5],a[maxn+5][maxn+5],p[maxn+5][maxn+5],C[maxc+5],ha[maxc+5]; int f[maxn+5][maxn+5][maxs];pair<int,int> que[maxc+5]; int Head,Tail;bool vis[maxn+5][maxn+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline bool Fmin(int &x,int y) {return y<x?(x=y,true):false;} #define AM(x) ((x)<maxc?(x)+1:0) inline void Spfa(int s){ while (Head!=Tail){ pair<int,int> now=que[Head=AM(Head)];int x=now.fr,y=now.sc;vis[x][y]=false; for (int t=0;t<4;t++){ int xx=x+dif[t][0],yy=y+dif[t][1];if (xx<1||xx>n||yy<1||yy>m||c[xx][yy]<0) continue; if (Fmin(f[xx][yy][s],f[x][y][s]+p[xx][yy])&&!vis[xx][yy]) que[Tail=AM(Tail)]=mp(xx,yy),vis[xx][yy]=true; } } } inline int DP(int mid,int ans=INF){ for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) p[i][j]=(a[i][j]<=mid?9999:10001); for (int t=1;t<=150;t++){ random_shuffle(C+1,C+1+C[0]);for (int i=1;…

[FWT+快速乘]Codeforces453D【Little Pony and Elements of Harmony】题解
type: item
date: 2019-02-27T20:44:04+08:00
description: 题目概述$a_{t}[i]=\sum_{j}a_{t-1}[j]b[count(i\ xor\ j)]$ ，其中 $count(i)$ 表示 $i$ 二进制下 $1$ 的个数。给出 $a_0,b$ ，求 $a_t$ 。解题报告令 $c[i]=b[count(i)]$ ，那么 $a_{t}=a_{t-1}*c$ （ $*$ 表示异或卷积），FWT裸题？但是模数可能是偶数？WTF？我们可以先将模数扩大 $n$ 倍，然后就可以在FWT的最后直接除以 $n$（考虑到模其实是减法，所以肯定有 $n​$ 这个因子）。但是这样会爆long long，所以要快速（慢速）乘。示例程序#include<cstdio> #include<cctype> using namespace std; typedef long long LL;typedef long double DB; const int maxm=20,maxn=1<<20; int n;LL t,MOD,a[maxn+5],b[maxm+5],c[maxn+5],cnt[maxn+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void AMOD(LL &x,LL tem) {if ((x+=tem)>=MOD) x-=MOD;} inline LL Mul(LL x,LL y) {return (x*y+MOD-(LL)((DB)x/MOD*y)*MOD)%MOD;} inline LL Pow(LL w,LL b) {LL s;for (s=1;b;w=Mul(w,w),b>>=1) if (b&1) s=Mul(s,w);return s;} inline void FWT(LL *a,int n,int f){ for (int k=1;k<n;k<<=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++) {LL x=a[i+j],y=a[i+j+k];AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);} if (f<0) for (int i=0;i<=n;i++) a[i]/=n; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);readi(t);readi(MOD);MOD*=(1<<n); for (int i=0;i<(1<<n);i++) readi(a[i]),a[i]%=MOD;for (int i=0;i<=n;i++) readi(b[i]),b[i]%=MOD; n=1<<n;for (int i=0;i<n;i++) c[i]=b[cnt[i]=cnt[i>>1]+(i&1)];FWT(a,n,1);FWT(c,n,1); for (int i=0;i<n;i++) a[i]=Mul(a[i],Pow(c[i],t));FWT(a,n,-1); for (int i=0;i<n;i++) printf("%lld\n",a[i]);return 0; }

[斯坦纳树+随机]HHHOJ200【稗田的梦中之梦】题解
type: item
date: 2019-02-27T15:01:00+08:00
description: 解题报告题目里要我们找出的实际上是一个满足条件的连通块，又因为数据范围这么小，所以想到斯坦纳树来做这种连通块最小值问题。令 $f_{i,j,s}$ 表示 $i,j$ 这个点与 $s$ 这些颜色连通的最优解，最后枚举大小为 $K$ 的集合更新答案。然而……颜色数有250种，根本不可能存下状态，但是 $K$ 却非常小，于是可以乱搞：随机把每种颜色映射到 $[1,K]$ 中，然后做斯坦纳树，这样复杂度就正常了。考虑答案正确的概率，假设最优解选取的颜色集合为 $C$ ，则 $C$ 中的 $K$ 个点不能重复，也就是一个 $K$ 的排列，所以概率为 ${K!\over K^K}\approx0.006119899$ ，那么随机个 $400$ 次，概率就变成 $90\%$ 了，如果你的代码常数小，可以考虑随机 $800$ 次，这样概率就变成 $99\%$ 了。其实还可以映射到 $[1,K+c]$（ $c$ 是个小常数），这样正确概率会大一些，但是时间复杂度也会多个常数。示例程序#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; const int maxn=15,maxt=maxn*maxn,maxc=250,maxk=7,maxs=1<<maxk; const int dif[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int n,m,K,c[maxn+5][maxn+5],p[maxn+5][maxn+5],C[maxc+5],ha[maxc+5]; int f[maxn+5][maxn+5][maxs],INF,ans;pair<int,int> que[maxt+5]; int Head,Tail;bool vis[maxn+5][maxn+5]; inline bool Fmin(int &x,int y) {return y<x?(x=y,true):false;} #define AM(x) ((x)<maxt?(x)+1:0) inline void Spfa(int s){ while (Head!=Tail){ pair<int,int> now=que[Head=AM(Head)];int x=now.fr,y=now.sc;vis[x][y]=false; for (int t=0;t<4;t++){ int xx=x+dif[t][0],yy=y+dif[t][1];if (xx<1||xx>n||yy<1||yy>m||c[xx][yy]<0) continue; if (Fmin(f[xx][yy][s],f[x][y][s]+p[xx][yy])&&!vis[xx][yy]) que[Tail=AM(Tail)]=mp(xx,yy),vis[xx][yy]=true; } } } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); srand(759405);scanf("%d%d%d",&n,&m,&K);int X,Y; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&c[i][j]); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&p[i][j]); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (c[i][j]>0) C[++C[0]]=c[i][j]; sort(C+1,C+1+C[0]);C[0]=unique(C+1,C+1+C[0])-C-1;ans=2e9; for (int t=1;t<=400;t++){ random_shuffle(C+1,C+1+C[0]);for (int i=1;i<=C[0];i++) ha[C[i]]=i%K; memset(f,63,sizeof(f));INF=f[0][0][0]; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) c[i][j]>0?f[i][j][1<<ha[c[i][j]]]=p[i][j]:0; for (int s=1;s<(1<<K);Spfa(s++),Head=Tail=0) for (int i=1;i<=n;i++…

[斯坦纳树]BZOJ2595(Wc2008)【游览计划】题解
type: item
date: 2019-02-27T10:37:00+08:00
description: 题目概述在 $n\times m$ 的网格上有 $k$ 个景点，选取每个网格都有代价，求最小代价使得景点之间全部连通。解题报告感觉这个东西好mogical啊……定义 $f_{i,j,s}$ 表示当 $i,j$ 与 $s$ 这些景点连通时的最优解，那么有两种方法转移：通过子集转移：$f_{i,j,t}+f_{i,j,s-t}-cost_{i,j}\to f_{i,j,s}$ ，减去 $cost_{i,j}$ 是因为算重复了。通过相邻点转移：$f_{x,y,s}+cost_{i,j}\to f_{i,j,s}$ 。但是这个DP后效性已经飞天了，由于第二种转移和最短路长得很像，所以考虑用Spfa（没错就是SpfaQAQ）进行，每次先用第一种转移处理出 $f_{i,j,s}$ ，然后把 $f_{i,j,s}$ 加进队列，对每个 $s$ 都做一遍Spfa。复杂度……可能是 $O(n^23^n+n^22^n)=O(n^23^n)$ ？至于为什么叫这个名字，我怎么知道。示例程序#include<cstdio> #include<cstring> using namespace std; const int maxn=10,maxk=10,maxs=1<<maxk,maxt=maxn*maxn; const int dif[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int n,m,K,pic[maxn+5][maxn+5],f[maxn+5][maxn+5][maxs]; struct data {int i,j,s;} fa[maxn+5][maxn+5][maxs],que[maxt+5]; int INF,Head,Tail;bool vis[maxn+5][maxn+5]; inline bool Fix(int &x,int y) {if (y<x) return x=y,true;return false;} #define AM(x) ((x)<maxt?(x)+1:0) inline void Spfa(int s){ while (Head!=Tail){ data now=que[Head=AM(Head)];int x=now.i,y=now.j;vis[x][y]=false; for (int t=0;t<4;t++){ int xx=x+dif[t][0],yy=y+dif[t][1];if (xx<1||xx>n||yy<1||yy>m) continue; if (Fix(f[xx][yy][s],f[x][y][s]+pic[xx][yy])){ fa[xx][yy][s]=(data){x,y,s};if (vis[xx][yy]) continue; que[Tail=AM(Tail)]=(data){xx,yy,s};vis[xx][yy]=true; } } } } void Path(int x,int y,int s){ if (!x&&!y) return;data now=fa[x][y][s];int i=now.i,j=now.j,t=now.s; vis[x][y]=true;Path(i,j,t);if (x==i&&y==j) Path(i,j,s^t); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d",&n,&m);memset(f,63,sizeof(f));INF=f[0][0][0];int X,Y; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&pic[i][j]),pic[i][j]?0:f[X=i][Y=j][1<<K++]=0; for (int s=1;s<(1<<K);Spfa(s),s++,Head=Tail=0){ for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){ for (int t=(s-1)&s;t;t=(t-1)&s) if (Fix(f[i][j][s],f[i][j][t]+f[i][j][s^t]-pic[i][j])) fa[i][j][s]=(data){i,j,t}; if (f[i][j][s]<INF) que[Tail=AM(Tail)]=(data){i,j,s},vis[i][j]=true; } }printf("%d\n",f[X][Y][(1<<K)-1]);Path(X,Y,(1<<K)-1); for (int i=1;i<=n;i++,put…

[期望的线性性+概率DP]TopCoder【RockPaperScissors】题解
type: item
date: 2019-02-26T21:56:42+08:00
description: 题目概述有 $n$ 个骰子，每个骰子投出剪刀、石头、布的概率已知。现在每次随机拿出剩余骰子中的一个进行投掷（并不知道这个骰子的概率分布），投完后扔掉。你要出 $n$ 次剪刀石头布，赢了得 $3$ 分，平了得 $1$ 分，输了不得分，求最大期望得分。解题报告网上题解讲的都好简略啊（我太菜了）……我翻了一篇英文题解才看懂做法……根据期望的线性性，我们可以对每次分别求最大贡献，所以我们需要知道第 $i$ 次投 $j$ 这个骰子的概率。不难发现第 $i​$ 次的概率只和之前投出的剪刀、石头、布的数量有关，所以我们可以定义 $f_{t,i,r,p,s}​$ 表示前 $t​$ 个骰子，第 $i​$ 个骰子还没有用掉，投出了 $r​$ 个石头，$p​$ 个布，$s​$ 个剪刀的概率。$f_t$ 可以从 $f_{t-1}$ 转移，考虑这次投的是 $t$ 这个骰子，那么需要讨论：$i=t$ ：不能投 $t$ ，所以直接继承 $f_{t-1}$ ，概率为 $1-{r+p+s\over t}$ ，即之前没有任何一个投了 $t$ 这个骰子。$i\not=t$ ：首先可以继承 $f_{t-1}$ ，然后 $t$ 可能投出剪刀、石头、布，概率为 ${r+p+s\over t}$ 乘上 $t$ 骰子对应的概率。这样时空复杂度都是 $O(n^5)$ 的，空间凉凉了，但是由于转移是个类似背包的东西，所以可以去掉一维（滚动数组也MLE）。做完这个之后，我们枚举 $r,p,s$ ，然后枚举这次投出的骰子 $i$ ，计算好概率之后求一下3种情况的最大值就行了。示例程序#include<cstdio> #include<vector> #define pb push_back using namespace std; typedef double DB; const int maxn=50; int n;DB a[maxn+5][3],f[maxn+1][maxn+1][maxn+1][maxn+1],ans; class RockPaperScissors{ public: inline DB bestScore(vector<int> R,vector<int> P,vector<int> S){ for (int i=(n=R.size(),1);i<=n;i++) a[i][0]=(DB)R[i-1]/300,a[i][1]=(DB)P[i-1]/300,a[i][2]=(DB)S[i-1]/300; for (int i=1;i<=n;i++) f[i][0][0][0]=1;ans=0; for (int t=1;t<=n;t++) for (int i=1;i<=n;i++) for (int r=t;~r;r--) for (int p=t-r;~p;p--) for (int s=t-r-p;~s;s--){ DB P=(DB)(r+p+s)/t;f[i][r][p][s]*=1-P;if (i==t) continue; if (r) f[i][r][p][s]+=f[i][r-1][p][s]*P*a[t][0]; if (p) f[i][r][p][s]+=f[i][r][p-1][s]*P*a[t][1]; if (s) f[i][r][p][s]+=f[i][r][p][s-1]*P*a[t][2]; } for (int r=0;r<n;r++) for (int p=0;p+r<n;p++) for (int s=0;r+p+s<n;s++){ int num=n-(r+p+s);DB R=0,P=0,S=0; for (int i=1;i<=n;i++){ R+=f[i][r][p][s]*a[i][0]; P+=f[i][r][p][s]*a[i][1]; S+=f[i][r][p][s]*a[i][2]; }R/=num;P/=num;S/=num; ans+=max(3*S+R,max(3*R+P,3*P+S)); } return ans; } };

[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
type: item
date: 2019-02-26T18:27:00+08:00
description: 题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问，每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。解题报告SAM+LCT什么的好大啊，所以我们来乱搞吧QAQ。把串倒过来，那么就是求后缀的最长公共前缀，这是后缀数组Height数组经典问题，如果询问 $[L,R]$ 满足 $x\in\{rank_i|L\le i\le R\}$ 且 $x-1\in\{rank_i|L\le i\le R\}$ 那么 $Height_x$ 就可以修正这个询问。因此把询问离线之后，通过合并Height数组（大的Height可以合并到相邻的小的Height），我们就可以得到一个 $O(nm)$ 算法。考虑从大到小枚举Height数组，这样我们就可以做到每个询问只修正一次，但是对于 $x$ 要怎么快速找到合法的询问？吃我bitset啦！我们先处理出 $S_i$ 表示符合 $i$ 的询问集合（差分），然后每次通过bitset的&操作就可以快速得到满足条件且还没有被修正过的询问集合，这样复杂度就变成了 $O({nm\over\omega})$ 。还有个黑科技，由于 $m=10^5$ 的时候会MLE，所以我们……做两次 $m=5\cdot10^4$ QAQ！示例程序#include<cstdio> #include<bitset> #include<algorithm> using namespace std; typedef unsigned long long ULL; const int maxn=100000,maxm=50000,maxt=784; int n,Q,SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5],h[maxn+5]; char s[maxn+5];int ID[maxn+5],Lg[23333],ans[maxm+5],fat[maxn+5]; #define pw(i) ((ULL)1<<(i)) struct Bitset{ ULL s[maxt];inline void Clear() {for (int i=0;i<maxt;i++) s[i]=0;} inline void Set(int i) {s[i/64]|=pw(i%64);} inline void Unset(int i) {Set(i);s[i/64]^=pw(i%64);} inline void operator &= (const Bitset &a){ for (int i=0;i<maxt;i+=4) s[i]&=a.s[i],s[i+1]&=a.s[i+1],s[i+2]&=a.s[i+2],s[i+3]&=a.s[i+3]; } inline void operator |= (const Bitset &a){ for (int i=0;i<maxt;i+=4) s[i]|=a.s[i],s[i+1]|=a.s[i+1],s[i+2]|=a.s[i+2],s[i+3]|=a.s[i+3]; } inline void operator ^= (const Bitset &a){ for (int i=0;i<maxt;i+=4) s[i]^=a.s[i],s[i+1]^=a.s[i+1],s[i+2]^=a.s[i+2],s[i+3]^=a.s[i+3]; } inline int Next(int x){ int A=x/64,B=x%64;ULL now;if (B<63&&(now=s[A]&~(pw(B+1)-1))) return A*64+Lg[(now&-now)%23333]; for (int i=A+1;i<maxt;i++) if (s[i]) return i*64+Lg[(s[i]&-s[i])%23333];return 2e9; } }q[maxn+5]; inline void Sort(int n,int m){ for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++; for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i]; } inline void Make(char *s,int n){ int m=255;for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i;Sort(n,m); for (int p=0,k=1;p<n;k<<=1,m=p){ p=0;for (int i=n-k+1…

[霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解
type: item
date: 2019-02-25T23:12:00+08:00
description: 解题报告题解里有个很厉害的 $O((n+s)log_2n)​$ 做法，但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题，我们可以把每项工作 $K_i$ 看成 $K_i$ 个点，然后如果 $L_j\le K_i\le R_j$ 那么 $j$ 这个宠物就向工作 $i$ 连边，我们要验证是否对于所有工作的集合 $S$ ，都有 $|E(S)|\ge |S|$ 。考虑DP，将工作排序之后，定义 $f_i$ 表示前 $i$ 个工作 $i$ 必选时 $|E(S)|-|S|$ 的最小值，如果 $\exists i,f_i<0$ 就凉了。转移时我们需要枚举 $j$ 表示上一次选的工作，这次多出来的 $E(S)$ 就是 $L_j\in(K_j,K_i],R_j\in[K_i,n]$ 的 $j$ ，可以通过主席树预处理，而多出来的 $S$ 就是 $K_i$ 。这样DP时间复杂度为 $O(m^2log_2n)$ ，这非常的凉凉。我们发现 $K_i$ 相同的工作可以合并起来（因为 $E(S)$ 是一样的），所以可以将 $K_i$ 排序去重，又因为 $\sum K_i\le n$（否则显然无解） ，所以只会剩下 $O(\sqrt n)$ 种不同的 $K_i$ ！就可以把复杂度降到 $O(s\sqrt nlog_2n)$ 啦。因为这个复杂度还是很危险，需要搞点预处理之类的QAQ……示例程序#include<cstdio> #include<cctype> #include<vector> #include<algorithm> #define pb push_back using namespace std; const int maxn=500000,maxm=200000,maxt=1e7; int n,te,si,ro[maxn+5],ls[maxt+5],rs[maxt+5],sum[maxt+5]; vector<int> a[maxn+5];int m,K[maxm+5],cnt[2005][2005],val[maxm+5],f[maxm+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } int Insert(int p,int pos,int l=1,int r=n){ int now=++si;ls[now]=ls[p];rs[now]=rs[p];sum[now]=sum[p]+1;if (l==r) return now;int mid=l+(r-l>>1); if (pos<=mid) ls[now]=Insert(ls[p],pos,l,mid); else rs[now]=Insert(rs[p],pos,mid+1,r);return now; } int Ask(int p,int L,int R,int l=1,int r=n){ if (!p) return 0;if (L==l&&r==R) return sum[p];int mid=l+(r-l>>1); if (R<=mid) return Ask(ls[p],L,R,l,mid); else if (L>mid) return Ask(rs[p],L,R,mid+1,r); else return Ask(ls[p],L,mid,l,mid)+Ask(rs[p],mid+1,R,mid+1,r); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d",&n);for (int i=1,L,R;i<=n;i++) readi(L),readi(R),a[R].pb(L); for (int i=n;i;i--) {ro[i]=r…

[单调栈+DP]Codeforces1131G【Most Dangerous Shark】题解
type: item
date: 2019-02-25T18:34:17+08:00
description: 题目概述有 $n$ 个骨牌，每个骨牌有高度和推倒代价，骨牌可以往左往右推倒，如果两个骨牌的距离小于推倒骨牌高度那么就会向同一个方向倒下，求最小代价使得所有骨牌都倒下。解题报告不难想到 $O(n^2)$ DP，就是对于每个骨牌，考虑往左推倒或者往右推倒：$$ f_i=min\{min\{f_{j-1}+c_j|r_j\ge i\},f_{l_i-1}+c_i\} $$其中 $l_i,r_i$ 表示 $i$ 往左往右能够到达的地方，可以 $O(n)$ 单调栈求出。我们需要优化这个DP，由于从 $f_{l_i-1}$ 转移是 $O(1)$ 的，所以我们需要优化的部分是骨牌向右推的情况，考虑骨牌向右推的性质：如果向右推倒骨牌 $i$ 会导致骨牌 $j(j>i)$ 被推倒，且 $f_j\ge f_i$ ，那么 $j$ 肯定没有用了。所以这可以用单调栈优化，维护一个递减的单调栈，每次先把 $r_j<i$ 的 $j$ 弹出栈，取出栈顶修正 $f_i$ ，然后看 $f_i$ 能否加入栈中就行了。示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxm=250000,maxn=10000000; int m,n,te,K[maxm+5],a[maxm+5],b[maxm+5],h[maxn+5],l[maxn+5],r[maxn+5]; LL c[maxn+5],f[maxn+5];int top,stk[maxn+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } #define F(x) (f[(x)-1]+c[x]) int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(m);readi(n);n=0; for (int i=1;i<=m;i++){ readi(K[i]);K[i]+=K[i-1]; for (int j=K[i-1]+1;j<=K[i];j++) readi(a[j]); for (int j=K[i-1]+1;j<=K[i];j++) readi(b[j]); } for (readi(te);te;te--){ int ID,x;readi(ID);readi(x); for (int i=K[ID-1]+1;i<=K[ID];i++) h[++n]=a[i],c[n]=(LL)b[i]*x; } for (int i=(top=0,1);i<=n;i++){ l[i]=i;while (top&&i-stk[top]<h[i]) l[i]=l[stk[top--]]; while (top&&l[stk[top l[i]) top--;stk[++top]=i; } for (int i=(top=0,n);i;i--){ r[i]=i;while (top&&stk[top]-i<h[i]) r[i]=r[stk[top--]]; while (top&&r[stk[top]]<r[i]) top--;stk[++top]=i; } for (int i=1;i<=n;i++){ f[i]=f[l[i]-1]+c[i];while (top&&r[stk[top]]<i) top--; if (top) f[i]=min(f[i],F(stk[top])); if (!top||F(stk[top])>F(i)) stk[++top]=i; }printf("%lld\n",f[n]);return 0; }