给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K。
点分治：先建树，然后分两步：
如何求当前点所在子树中符合条件的点对数呢？先通过dfs求出从当前节点到所在子树各节点的距离，然后用排序+两头计算法计算出从某节点到当前节点再到另一节点的距离满足条件的点对。但是，这样做是有缺陷的：如图，当前节点为2，就可能求出4-5-2-5-6这样不存在的情况，怎么办呢？
设此点对数为x。我们可以对每个子节点进行这样的计算：将该子节点的初始距离数组d[x]置为当前节点到该子节点的距离，求出该子节点到其所在子树所有点的距离，然后用与刚才类似的方法算出与该子节点相关的点对数设为yi。将x减掉所有子节点的yi得到的值就是真实的点对数。刚才计算子节点的操作实际上求得的就是经过该子节点的不存在的点对数（如中间经过5-2-5的点对）。前面述说的两个操作类似，可以合并成一个函数getdis，前者操作就是把当前节点的初始距离数组d[x]置为0。具体看代码。
选哪个节点作为根节点？引入一个概念：树的重心：找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。很明显，我们找根就要找树的重心。怎么求树的重心呢？用dfs求出当前节点所在子树的每个节点最大子树的最小值即可，注意树的形态是不一定的，所以除了逻辑上的儿子sz[i]还有sm-sz[x]。
同时还有一些细节，比如vis数组，使搜索时不要搜到想搜的子树之外的节点。时间复杂度？work执行n次，calc执行O(log2n)次（因为根为树的重心），getroot和getdis总共执行了O(nlog2n)次，所以总复杂度为O(nlog2n)（其实我也不知道为什么复杂度是这个，但它就是这个……）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3fffffff
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define visit(i,j) for(int i=g[j];i!=-1;i=es[i].n)
#define N 40010
using namespace std;
int n,k,ans;
struct e{int t,w,n;}; e es[N*2]; int ess,g[N];
inline void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess; es[++ess]=(e){f,w,g[t]}; g[t]=ess;}
int root,sm,mn,szs,d[N],sz[N],data[N]; bool vis[N];
void getroot(int x,int fa){
sz[x]=1; int mx=0;
visit(i,x)if(! vis[es[i].t]&&es[i].t!=fa){getroot(es[i].t,x); sz[x]+=sz[es[i].t]; mx=max(mx,sz[es[i].t]);}
mx=max(mx,sm-sz[x]); if(mx<mn)root=x,mn=mx;
}
void getdis(int x,int fa){
data[++szs]=d[x];
visit(i,x)if(! vis[es[i].t]&&es[i].t!=fa){d[es[i].t]=d[x]+es[i].w; getdis(es[i].t,x);}
}
int calc(int x,int st){
d[x]=st; szs=0; getdis(x,-1); sort(data+1,data+szs+1); int l=1,r=szs,a=0;
while(l<r){if(data[l]+data[r]<=k)a+=(r-l),l++;else r--;}
return a;
}
void work(int x){
ans+=calc(x,0); vis[x]=1;
visit(i,x)if(!vis[es[i].t]){ans-=calc(es[i].t,es[i].w); root=es[i].t; sm=sz[es[i].t]; mn=INF; getroot(es[i].t,x); work(root);}
}
int main(){
scanf("%d",&n); ess=0; memset(g,-1,sizeof(g));
inc(i,1,n-1){int a,b,c; scanf("%d%d%d",&a,&b,&c); pe(a,b,c);} scanf("%d",&k);
memset(vis,0,sizeof(vis)); root=1; mn=INF; getroot(1,-1); ans=0; work(root); printf("%d\n",ans);
return 0;
}给定有权树，支持单边权修改，路径边权取相反数，路径边权求和，路径边权求最大最小值。
用link-cut tree（lct）。link-cut tree与树链剖分有些类似，都是用某种数据结构维护树链。但也有很大差异：树链剖分是依据子树节点数确定轻重边，一经确定，不能更改，所以用相对静态的线段树维护，常数也较小。而link-cut tree是用来求解动态树问题的，它的链随时可以改变，因此也只能用动态的splay来维护，常数较大。
注意：本数据结构中splay是以节点在lct中的深度为关键字确定顺序的。lct中节点的fa有两个意思，当它不为自己所在splay的根结点时，fa表示其在splay中的父节点，当它为splay中的根节点时，fa表示这整条树链在lct中的父亲节点。
lct有三个基础操作：
可是有了这些怎么得到或更新任意两点间的信息呢？我们知道，求两点间的信息一般都要求lca，lct怎么会没这个功能呢？求u,v的lca：先access(u)，再access(v)，后者在执行的时候最后得到那个t（见程序）就是lca，因为之前x已经和根节点相连了。两次access后，再splay(u)，就形成一条从u连到lca且以u为根的树链，此时将u的信息与lca的右子节点信息合并即可。
吐槽：我是傻叉，rotate顺序写乱了，导致fa信息出错死循环re了3发，然后又因为两次access后没有splay又wa了2发，大样例调不出，自己的小样例又测不出错误，花了3h……
发现一个技巧，要让gdb在满足条件时停下来，可以if(条件满足)函数();然后在函数里设断点，就能准确中断了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 20010
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
//general
int n,m;
void debug(){
n=n;
}
//edge
struct e{int t,w,n;}; e es[N*2]; int ess,g[N];
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess; es[++ess]=(e){f,w,g[t]}; g[t]=ess;}
//splay
int fa[N]/*点的父亲，包括在splay中的父亲和所在splay的父亲*/,c[N][2]/*splay中的儿子节点*/;
int sm[N],mx[N],mn[N],v[N],/*区间维护信息*/dt[N],dts/*中间过程用*/; bool tg[N]/*标记*/;
inline bool is_root(int x){return fa[x]==0||(c[fa[x]][0]!=x&&c[fa[x]][1]!=x);}//判断是否为所在splay的根节点
void pushdown(int x){//标记下传。注：本程序中的标记表明本节点已更新子孙未更新
if(x==0)return;
if(tg[x]){
int l=c[x][0],r=c[x][1]; tg[x]^=1;
if(l){tg[l]^=1; v[l]=-v[l]; sm[l]=-sm[l]; int t=mx[l]; mx[l]=-mn[l]; mn[l]=-t;}
if(r){tg[r]^=1; v[r]=-v[r]; sm[r]=-sm[r]; int t=mx[r]; mx[r]=-mn[r]; mn[r]=-t;}
}
}
void update(int x){
if(x==0)return;
int l=c[x][0],r=c[x][1]; sm[x]=v[x]+sm[l]+sm[r]; mx[x]=max(v[x],max(mx[l],mx[r])); mn[x]=min(v[x],min(mn[l],mn[r]));
}
void rotate(int x){//旋转
if(x==0||is_root(x))return;
int a=fa[x],b=fa[fa[x]]; bool d=c[a][1]==x,e=c[b][1]==a;
if(! is_root(a))c[b][e]=x;//注意在调用is_root前不能动参数的fa[a]和c[fa[a]][0]c[fa[a]][1]，不然会导致错误结果
if(c[x][!d])fa[c[x][!d]]=a;//注意别漏
fa[x]=b; fa[a]=x; c[a][d]=c[x][!d]; c[x][!d]=a;//注意修改的相对顺序
update(a); update(x); if(! is_root(x))update(b);
}
void splay(int x){//伸展
if(x==0)return;
dts=0; int t=x;
while(! is_root(t))dt[++dts]=t,t=fa[t]; dt[++dts]=t;//将根结点到x的所有标记一次下传
while(dts)pushdown(dt[dts]),dts--;
while(! is_root(x)){
if(!is_root(fa[x])) (c[fa[x]][1]==x)^(c[fa[fa[x]]][1]==fa[x])?rotate(x):rotate(fa[x]);
rotate(x);
}
}
//lct
int access(int x){//lct基本操作，使节点到根节点连成一条链，并把链上的分支断开
if(x==0)return 0;
int t=0;
while(x){
splay(x); c[x][1]=t; if(t)fa[t]=x;
update(x); t=x; x=fa[x];
}
debug();
return t;
}
void link(int x,int y){//lct基本操作，本程序不用
if(x==0||y==0)return;
access(x); splay(x); fa[x]=y;
}
void cut(int x){//lct基本操作，本程序不用
if(x==0)return;
access(x); splay(x); if(c[x][0])fa[c[x][0]]=0; c[x][0]=0; update(x);
}
//command
//注意修改时要根据题目要求将修改查询边权变为程序中的修改查询点权
void change(int x,int val){//更新权值
splay(x); v[x]=val; update(x);
}
void rever(int x,int y){//反转
access(x); int a=access(y); /*别*/splay(x);/*漏！下同*/
if(x==a){
int r=c[x][1]; tg[r]^=1; v[r]=-v[r]; sm[r]=-sm[r]; int t=mx[r]; mx[r]=-mn[r]; mn[r]=-t; update(x);
}else{
tg[x]^=1; v[x]=-v[x]; sm[x]=-sm[x]; int t=mx[x]; mx[x]=-mn[x]; mn[x]=-t;
int r=c[a][1]; tg[r]^=1; v[r]=-v[r]; sm[r]=-sm[r]; t=mx[r]; mx[r]=-mn[r]; mn[r]=-t;
update(a);
}
}
int querysum(int x,int y){//求和
access(x); int a=access(y); splay(x);
if(x==a)return sm[c[x][1]];else return sm[x]+sm[c[a][1]];
}
int querymax(int x,int y){//求最大值
access(x); int a=access(y); splay(x);
if(x==a)return mx[c[x][1]];else return max(mx[x],mx[c[a][1]]);
}
int querymin(int x,int y){//求最小值
access(x); int a=access(y); splay(x);
if(x==a)return mn[c[x][1]];else return min(mn[x],mn[c[a][1]]);
}
int num[N];
void dfs(int x){//建树，并将边权转为点权 ，本程序用边的终点点权表示这条边的边权
for(int i=g[x];i!=-1;i=es[i].n)if(es[i].t!=fa[x]){
fa[es[i].t]=x; v[es[i].t]=sm[es[i].t]=mx[es[i].t]=mn[es[i].t]=es[i].w; dfs(es[i].t);
}
}
int main(){
//freopen("big.txt","r",stdin); freopen("big.out","w",stdout);
memset(num,0,sizeof(num)); ess=0; memset(g,-1,sizeof(g)); memset(fa,0,sizeof(fa));
scanf("%d",&n); inc(i,1,n-1){int a,b,c; scanf("%d%d%d",&a,&b,&c); pe(a+1,b+1,c); num[i]=b+1;}
dfs(1);
memset(c,0,sizeof(c)); memset(tg,0,sizeof(tg)); mn[0]=INF; mx[0]=-INF; scanf("%d",&m); char s[10];
inc(i,1,m){
int a,b; scanf("%s%d%d",s,&a,&b);
if(s[0]=='C')change(num[a],b);
if(s[0]=='N')a++,b++,rever(a,b);
if(s[0]=='S')a++,b++,printf("%d\n",querysum(a,b));
if(s[1]=='A')a++,b++,printf("%d\n",querymax(a,b));
if(s[1]=='I')a++,b++,printf("%d\n",querymin(a,b));
}
return 0;
}用树链剖分重写一下本题。树链剖分主要分3个步骤：
如何求lca(u,v)？不停循环这样一个过程：u和v哪个深度大，就让它向上爬一条重链再爬一条轻边，直到两个所在链头节点相等（即在同一条树链）。此时，深度小的那个就是lca。
如何维护（查询）(u,v)之间信息？求lca(u,v)，然后对u不停循环这个过程：维护u到所在树链头的信息，接着u爬一条重链再一条轻边，直到树链头深度小于lca（此时u与lca在同一条树链），然后维护u到lca的信息。对v重复相同操作。
程序中我之所以存了每个节点的重儿子，是因为题意求边权，根据我的程序中边权与点权的转换方式，lca的权值不能被维护（查询），所以“维护u到lca的信息”就变成“维护u到lca重儿子的信息（如果此时u=lca，不能执行此操作）”
吐槽：线段树真耗空间，开的数组大小必须是点数的4倍！因为这个我re了5发。同时线段树的pushdown是边查询（修改）边执行的，需要注意。
对比链剖和link-cut tree，发现lct完胜！？不管在代码长度还是时间空间复杂度上都是lct更优。不是说线段树的常数比splay小得多吗？个人认为链剖输在一下几个方面：
总结：本题数据不是很大，链剖的适用范围应该是数据比较大的题，因为此时对程序本身常数的要求要高过空间引起的常数。
根本原因：我太弱了，肯定是我链剖写残才会这么慢！
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 20010
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
//gerneral
int n,m;
//edge
struct e{int t,w,n;}; e es[N*2]; int ess,g[N];
inline void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess; es[++ess]=(e){f,w,g[t]}; g[t]=ess;}
//segment tree
int sm[N*4],mx[N*4],mn[N*4]/*节点信息*/,v[N][2]/*中间数组*/,l[N*4],r[N*4]/*区间*/;
int lc[N*4],rc[N*4]/*左右儿子*/; bool tg[N*4]/*标记*/;
void update(int x){
if(x==0)return;
sm[x]=sm[lc[x]]+sm[rc[x]]; mx[x]=max(mx[lc[x]],mx[rc[x]]); mn[x]=min(mn[lc[x]],mn[rc[x]]);
}
void pushdown(int x){//标记意义同lct
if(x==0||!tg[x])return; int L=lc[x],R=rc[x]; tg[x]^=1;
if(L){tg[L]^=1; sm[L]=-sm[L]; int t=mx[L]; mx[L]=-mn[L]; mn[L]=-t;}
if(R){tg[R]^=1; sm[R]=-sm[R]; int t=mx[R]; mx[R]=-mn[R]; mn[R]=-t;}
}
void build(int x,int L,int R){//建线段树
l[x]=L; r[x]=R;
if(L==R)sm[x]=mx[x]=mn[x]=v[L][1],lc[x]=rc[x]=tg[x]=0;else{
int M=(L+R)>>1; lc[x]=x<<1; rc[x]=x<<1|1; build(lc[x],L,M); build(rc[x],M+1,R); tg[x]=0; update(x);
}
}
void change(int x,int nod,int val){//线段树点修改
pushdown(x);
if(l[x]==r[x])sm[x]=mx[x]=mn[x]=val;else{
int M=(l[x]+r[x])>>1; nod<=M?change(lc[x],nod,val):change(rc[x],nod,val); update(x);
}
}
void rever(int x,int ql,int qr){//线段树区间修改
pushdown(x);
int M=(l[x]+r[x])>>1; if(ql<=l[x]&&r[x]<=qr){tg[x]^=1; sm[x]=-sm[x]; int t=mx[x]; mx[x]=-mn[x]; mn[x]=-t; return;}
if(ql<=M)rever(lc[x],ql,qr); if(qr>M)rever(rc[x],ql,qr); update(x);
}
int querysum(int x,int ql,int qr){//线段树求和
pushdown(x);
int ret=0,M=(l[x]+r[x])>>1; if(ql<=l[x]&&r[x]<=qr)return sm[x];
if(ql<=M)ret+=querysum(lc[x],ql,qr); if(qr>M)ret+=querysum(rc[x],ql,qr);
return ret;
}
int querymax(int x,int ql,int qr){//线段树求最大值
pushdown(x);
int ret=-INF,M=(l[x]+r[x])>>1; if(ql<=l[x]&&r[x]<=qr)return mx[x];
if(ql<=M)ret=max(ret,querymax(lc[x],ql,qr)); if(qr>M)ret=max(ret,querymax(rc[x],ql,qr));
return ret;
}
int querymin(int x,int ql,int qr){//线段树求最小值
pushdown(x);
int ret=INF,M=(l[x]+r[x])>>1; if(ql<=l[x]&&r[x]<=qr)return mn[x];
if(ql<=M)ret=min(ret,querymin(lc[x],ql,qr)); if(qr>M)ret=min(ret,querymin(rc[x],ql,qr));
return ret;
}
//tree chain apart
int pos[N]/*点在线段树中位置*/,top[N]/*树链头节点*/,fa[N],sz[N]/*子树大小*/,sgs,dep[N]/*深度*/,ps[N]/*重儿子*/;
void dfs(int x){//得到节点的父亲、子树大小、权值、深度
sz[x]=1;
for(int i=g[x];i!=0;i=es[i].n)if(es[i].t!=fa[x]){
fa[es[i].t]=x; dep[es[i].t]=dep[x]+1; v[es[i].t][0]=es[i].w; dfs(es[i].t); sz[x]+=sz[es[i].t];
}
}
void buildchain(int x,int tp/*当前节点所在树链头*/){//通过子树大小构造树链
pos[x]=++sgs; v[sgs][1]=v[x][0]; top[x]=tp; ps[x]=0;
for(int i=g[x];i!=0;i=es[i].n)if(es[i].t!=fa[x]){
if(sz[es[i].t]>sz[ps[x]])ps[x]=es[i].t;
}
if(ps[x]==0)return;
buildchain(ps[x],tp);
for(int i=g[x];i!=0;i=es[i].n)if(es[i].t!=fa[x]){
if(es[i].t!=ps[x])buildchain(es[i].t,es[i].t);
}
}
void init(){
memset(fa,0,sizeof(fa)); dep[1]=1; dfs(1);
sgs=0; mx[0]=-INF; mn[0]=INF; sz[0]=0; buildchain(1,1); build(1,1,sgs);
}
int lca(int x,int y){
for(;top[x]!=top[y];x=fa[top[x]]){if(dep[top[x]]<dep[top[y]])swap(x,y);}
return dep[x]<dep[y]?x:y;
}
void solvechange(int x,int val){change(1,pos[x],val);}
void solverever(int x,int y){
if(x==y)return; int a=lca(x,y);
while(dep[top[x]]>dep[a])rever(1,pos[top[x]],pos[x])/*注意参数顺序，下同*/,x=fa[top[x]];
if(a!=x)rever(1,pos[ps[a]],pos[x]);
while(dep[top[y]]>dep[a])rever(1,pos[top[y]],pos[y]),y=fa[top[y]];
if(a!=y)rever(1,pos[ps[a]],pos[y]);
}
int solvesum(int x,int y){
if(x==y)return 0; int a=lca(x,y),ans=0;
while(dep[top[x]]>dep[a])ans+=querysum(1,pos[top[x]],pos[x]),x=fa[top[x]];
if(a!=x)ans+=querysum(1,pos[ps[a]],pos[x]);
while(dep[top[y]]>dep[a])ans+=querysum(1,pos[top[y]],pos[y]),y=fa[top[y]];
if(a!=y)ans+=querysum(1,pos[ps[a]],pos[y]);
return ans;
}
int solvemax(int x,int y){
if(x==y)return 0; int a=lca(x,y),ans=-INF;
while(dep[top[x]]>dep[a])ans=max(ans,querymax(1,pos[top[x]],pos[x])),x=fa[top[x]];
if(a!=x)ans=max(ans,querymax(1,pos[ps[a]],pos[x]));
while(dep[top[y]]>dep[a])ans=max(ans,querymax(1,pos[top[y]],pos[y])),y=fa[top[y]];
if(a!=y)ans=max(ans,querymax(1,pos[ps[a]],pos[y]));
return ans;
}
int solvemin(int x,int y){
if(x==y)return 0; int a=lca(x,y),ans=INF;
while(dep[top[x]]>dep[a])ans=min(ans,querymin(1,pos[top[x]],pos[x])),x=fa[top[x]];
if(a!=x)ans=min(ans,querymin(1,pos[ps[a]],pos[x]));
while(dep[top[y]]>dep[a])ans=min(ans,querymin(1,pos[top[y]],pos[y])),y=fa[top[y]];
if(a!=y)ans=min(ans,querymin(1,pos[ps[a]],pos[y]));
return ans;
}
//main
int num[N];
int main(){
//freopen("zs.txt","r",stdin); freopen("zs.out","w",stdout);
scanf("%d",&n); memset(g,0,sizeof(g)); ess=0;
inc(i,1,n-1){int a,b,c; scanf("%d%d%d",&a,&b,&c); a++; b++; pe(a,b,c); num[i]=b;}
init(); scanf("%d",&m); char s[10];
inc(i,1,m){
int a,b; scanf("%s%d%d",s,&a,&b);
if(s[0]=='C')solvechange(num[a],b);
if(s[0]=='N')a++,b++,solverever(a,b);
if(s[0]=='S')a++,b++,printf("%d\n",solvesum(a,b));
if(s[1]=='A')a++,b++,printf("%d\n",solvemax(a,b));
if(s[1]=='I')a++,b++,printf("%d\n",solvemin(a,b));
}
return 0;
}n*m网格，每个格子可能为狼、羊或空格。现在要在一些格子边界篱笆使羊狼分开，求最短篱笆。n，m≤100
最小割问题，建一个超级源和超级汇，然后从源点向每只羊之间连边，容量为正无穷；每只狼向汇点连边，容量为正无穷，相邻格子之间连边，容量为1，再跑一次最大流就是结果。因为每一条同时经过羊和狼的路径都需要堵住，但又不能堵连向源点和汇点的边，所以堵住的边必定是将羊和狼分隔开的边。
dicnic：求解网络流的一种算法：先用bfs构建层次图，然后用dfs沿着层次增广，当dfs无法增广时再重复上述过程，知道源点和汇点不连通。速度比传统的EK法要快得多，但比ISAP慢，因为ISAP无法增广时是直接修改层次，同时还能用gap优化，但dicnic很好写，简洁易懂。CZL大爷说dicnic在计算本来就有一定层次的图（如二分图）时速度快，ISAP在计算一般图速度快，涨姿势了！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0xfffffff
#define g(b) g[b.x][b.y]
#define h(b) h[b.x][b.y]
#define maxn 110
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
//edge
struct p{int x,y;}; struct e{p t;int c,n;}; e es[200000*2]; int ess,g[maxn][maxn];
void pe(p f,p t,int c){
es[++ess]=(e){t,c,g(f)}; g(f)=ess;
es[++ess]=(e){f,0,g(t)}; g(t)=ess;
}
//maxflow
queue <p> q; int h[maxn][maxn];
bool bfs(p s,p t){//构建层次图
while(! q.empty())q.pop(); memset(h,-1,sizeof(h)); h(s)=0; q.push(s);
while(! q.empty()){
p now=q.front(); q.pop();
for(int i=g(now);i!=-1;i=es[i].n)if(h(es[i].t)==-1&&es[i].c>0){
h(es[i].t)=h(now)+1; q.push(es[i].t);
}
}
return (h(t)==-1)?0:1;
}
int dfs(p x,p t,int flow){//找增广路并增广
if(x.x==t.x&&x.y==t.y)return flow;
int used=0;
for(int i=g(x);i!=-1;i=es[i].n)if(es[i].c>0&&h(es[i].t)==h(x)+1){
int w=dfs(es[i].t,t,min(flow,es[i].c));
es[i].c-=w; es[i^1].c+=w; used+=w; flow-=w; if(flow==0)return used;
}
if(! used)h(x)=-1; return used;
}
int dicnic(p s,p t){int flow=0; while(bfs(s,t))flow+=dfs(s,t,INF); return flow;}
//main
int n,m,graph[maxn][maxn];
int main(){
//freopen("zs.txt","r",stdin);
scanf("%d%d",&n,&m);
inc(i,1,n)inc(j,1,m)scanf("%d",&graph[i][j]);
memset(g,-1,sizeof(g)); ess=-1;
inc(i,1,n)inc(j,1,m){
if(graph[i][j]==2)pe((p){0,0},(p){i,j},INF);
if(graph[i][j]==1)pe((p){i,j},(p){n+1,m+1},INF);
if(i-1>0)pe((p){i,j},(p){i-1,j},1);
if(i+1<=n)pe((p){i,j},(p){i+1,j},1);
if(j-1>0)pe((p){i,j},(p){i,j-1},1);
if(j+1<=m)pe((p){i,j},(p){i,j+1},1);
}
printf("%d",dicnic((p){0,0},(p){n+1,m+1}));
return 0;
}N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色。
给每个颜色建一个链表。先预处理出答案，然后每次修改颜色时将两个链表合并，同时将修改后颜色对答案的贡献重新计算（如果两个节点的位置相差大于1说明中间有一段颜色，将贡献+1）。链表合并时用启发式合并（就是将小的拆了依次插入到大的里面），复杂度O(nlogn)（均摊复杂度，玄学）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define M 1000010
#define N 100010
using namespace std;
int ans,head[M],last[N],next[N],comb[M],sz[M],n,m;
int main(){
scanf("%d",&n); scanf("%d",&m); int a,b=0; ans=0;
memset(sz,0,sizeof(sz)); memset(comb,0,sizeof(comb)); memset(head,0,sizeof(head));
inc(i,1,n){
scanf("%d",&a); if(a!=b)ans++,comb[a]++;
next[i]=head[a]; last[head[a]]=i; head[a]=i; sz[a]++; b=a;
}
inc(i,1,m){
int a1; scanf("%d",&a1); if(a1==2)printf("%d\n",ans);
if(a1==1){
int a2,a3; scanf("%d%d",&a2,&a3); if(a2==a3)continue;
if(head[a2]==0)continue;
else if(head[a3]==0)head[a3]=head[a2],sz[a3]=sz[a2],comb[a3]=comb[a2],head[a2]=sz[a2]=comb[a2]=0;
else{
if(sz[a2]<sz[a3]){
int a4=head[a2],a6=head[a3];
while(a4){
int a5=next[a4];
for(;a4<a6&&next[a6]>0;a6=next[a6]);
if(a4<a6)next[a6]=a4,last[a4]=a6,next[a4]=0;
else if(last[a6]==0)last[a4]=0,next[a4]=a6,last[a6]=a4,head[a3]=a4;
else next[last[a6]]=a4,last[a4]=last[a6],next[a4]=a6,last[a6]=a4;
sz[a3]++; a4=a5;
}
sz[a2]=head[a2]=0;
}else{
int a4=head[a3],a6=head[a2];
while(a4){
int a5=next[a4];
for(;a4<a6&&next[a6]>0;a6=next[a6]);
if(a4<a6)next[a6]=a4,last[a4]=a6,next[a4]=0;
else if(last[a6]==0)last[a4]=0,next[a4]=a6,last[a6]=a4,head[a2]=a4;
else next[last[a6]]=a4,last[a4]=last[a6],next[a4]=a6,last[a6]=a4;
sz[a2]++; a4=a5;
}
head[a3]=head[a2],sz[a3]=sz[a2],head[a2]=sz[a2]=0;
}
ans-=comb[a2]; ans-=comb[a3]; comb[a2]=comb[a3]=0;
for(int i=head[a3];i;i=next[i])if(i==head[a3]||i!=last[i]-1)comb[a3]++;
ans+=comb[a3];
}
}
}
return 0;
}n个人，拆成若干个队。设x等于队里每个人战斗力之和，则这个队战斗力为ax2+bx+c（a,b,c已知）。求所有队战斗力总和最大多少。
方程：
\[ f[i]=max\{f[j]+a\times(sum[i]-sum[j])^2+b\times(sum[i]-sum[j])+c\},1\le j<i \]
将方程化简可以得到只要
\[ \frac{f[j]-f[k]+a\times(sum[j]^2-sum[k]^2)+b\times(sum[k]-sum[j])}{2\times a\times(sum[j]-sum[k])}>sum[i] \]
则说明用j递推比用k递推更优。同时这个式子是一个分式，可以看成一条线段的斜率，而斜率又满足这样一个性质：若线段AB斜率<线段BC斜率<线段CD斜率，则线段AB斜率＜AC斜率＜AD斜率。于是我们可以用一个单调队列，满足每两项的
\[ \frac{f[j]-f[k]+a\times(sum[j]^2-sum[k]^2)2+b\times(sum[k]-sum[j])}{2\times a\times(sum[j]-sum[k])} \]
单调递增，每次用队头更新（因为队头到其他点的斜率肯定大于sum[i]，最优）。注意单调队列的队头是l那一边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(long long i=j;i<=k;i++)
using namespace std;
long long n,a,b,c,l,r,q[1000010],sum[1000010],f[1000010];
inline long long sqr(long long a){return a*a;}
inline double calc(long long a1,long long a2){
return (double)(f[a1]-f[a2]+a*sqr(sum[a1])-a*sqr(sum[a2])+b*(sum[a2]-sum[a1]))/(double)(2*a*(sum[a1]-sum[a2]));
}
int main(){
scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
sum[0]=0; inc(i,1,n){long long a1;scanf("%lld",&a1); sum[i]=sum[i-1]+a1;}
l=r=1;
inc(i,1,n){
while(l<r&&calc(q[l],q[l+1])<sum[i])l++;
long long a1=q[l]; f[i]=f[a1]+sqr(sum[i]-sum[a1])*a+(sum[i]-sum[a1])*b+c;
while(l<r&&calc(q[r-1],q[r])>calc(q[r],i))r--; q[++r]=i;
}
printf("%lld",f[n]);
return 0;
}试卷上n道选择题，每道分别有ai个选项。某人全做对了，但第i道题的答案写在了第i+1道题的位置，第n道题答案写在第1题的位置。求期望能对几道。n≤10000000
水题，然而我不会。第i题与第i+1题答案一样的概率是\(\frac{1}{max(a_{i},a_{i+1})}\)
#include <cstdio>
#include <algorithm>
using namespace std;
int a[10000010],n,A,B,C;
int main(){
scanf("%d%d%d%d%d",&n,&A,&B,&C,&a[1]);
for(int i=2;i<=n;i++)a[i]=((long long)a[i-1] * A + B)%100000001;
for(int i=1;i<=n;i++)a[i]=a[i]%C+1; double ans=0;
for(int i=1;i<=n;i++)ans+=(1/(double)max(a[i],a[i%n+1]));
printf("%.3lf",ans);
}有个装置，左侧有上下两条管道分别有n个和m个不同颜色的两种球，右侧一条空管道。每次可以选左侧的一条管道将最右侧的球推到右侧管道，经过n+m次操作，右侧管道从右到左形成一个输出序列。求不同种类的输出序列的产生方式数的平方之和。n，m≤500
将题目转化成两个人同时取，取出来的序列相同的可能性有多少种。于是做dp。方程见代码。f[i][j][k][l]表示第一个人取了i个Aj个B第二个人取了k个Al个B。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define mod 1024523
using namespace std;
int f1[600][600],f2[600][600],n,m; char s1[600],s2[600];
int main(){
scanf("%d%d",&n,&m); scanf("%s%s",s1,s2);
inc(i,0,n)inc(j,0,n)f1[i][j]=1;
inc(i,1,n+m){
memset(f2,0,sizeof(f2));
dec(j,min(i,n),0)dec(k,min(i,n),0){
int a1=i-j,a2=i-k; if(a1>m||a2>m)continue;
if(j!=0&&k!=0&&s1[j-1]==s1[k-1])f2[j][k]=(f2[j][k]+f1[j-1][k-1])%mod;
if(j!=0&&a2!=0&&s1[j-1]==s2[a2-1])f2[j][k]=(f2[j][k]+f1[j-1][k])%mod;
if(k!=0&&a1!=0&&s2[a1-1]==s1[k-1])f2[j][k]=(f2[j][k]+f1[j][k-1])%mod;
if(a1!=0&&a2!=0&&s2[a1-1]==s2[a2-1])f2[j][k]=(f2[j][k]+f1[j][k])%mod;
}
swap(f1,f2);
}
int ans=0; inc(i,1,n)inc(j,1,n)ans=(ans+f1[i][j])%mod; printf("%d",ans);
}一种加密办法是把需要加密的信息排成一圈，显然，它们有很多种不同的读法。把它们按照字符串的大小排序，读出最后一列字符，就是加密后的字符串。给出原字符串，求加密后的字符串。
将原字符串重复后接在后面，然后求后缀数组，注意求完后要取那些长度大于原字符串长度a2的后缀的第a2个字符。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
char s[300000],s2[300000];int sa[300000],x[300000],y[300000],c[300000];
void make(char *str){
int len=strlen(str),m=0;memset(c,0,sizeof(c));inc(i,0,len-1)c[x[i]=str[i]]++,m=max(m,(int)str[i]);
inc(i,1,m)c[i]+=c[i-1]; dec(i,len-1,0)sa[--c[x[i]]]=i; m++;
for(int i=1;i<=len;i<<=1){
int p=0; inc(j,len-i,len-1)y[p++]=j;
inc(j,0,len-1)if(sa[j]>=i)y[p++]=sa[j]-i;
memset(c,0,sizeof(c)); inc(j,0,len-1)c[x[y[j]]]++;
inc(j,1,m-1)c[j]+=c[j-1];
dec(j,len-1,0)sa[--c[x[y[j]]]]=y[j];
swap(x,y);
p=1; x[sa[0]]=0;
inc(j,1,len-1)x[sa[j]]=y[sa[j-1]]==y[sa[j]]&&y[sa[j-1]+i]==y[sa[j]+i]?p-1:p++;
if(p>=len)break; m=p;
}
}
int main(){
scanf("%s",s); int a1=strlen(s); inc(i,0,a1-1)s[a1+i]=s[i]; s[2*a1]='\0';
make(s); int a2=0; inc(i,0,a1*2-1)if(sa[i]<a1)s2[a2++]=s[sa[i]+a1-1]; s2[a2]='\0';
printf("%s",s2);
}一排小孩坐着玩游戏。就座的方案满足如下条件：对于任意连续的一段，男孩与女孩的数目之差不超过k。给出男孩数，女孩数和k，求就座方案数除以12345678的余数。
dp方程见程序，i1i2表示当前选了几男几女，i3i4分别表示当前男比女多几个和女比男多几个。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define mod 12345678
using namespace std;
int f[160][160][30][30];
int main(){
int n,m,k; scanf("%d%d%d",&n,&m,&k);
f[0][0][0][0]=1;
inc(i1,0,n)inc(i2,0,m)inc(i3,0,k)inc(i4,0,k){
if(i1!=n&&i3!=k)f[i1+1][i2][i3+1][max(i4-1,0)]=(f[i1+1][i2][i3+1][max(i4-1,0)]+f[i1][i2][i3][i4])%mod;
if(i2!=m&&i4!=k)f[i1][i2+1][max(i3-1,0)][i4+1]=(f[i1][i2+1][max(i3-1,0)][i4+1]+f[i1][i2][i3][i4])%mod;
}
int ans=0;
inc(i1,0,k)inc(i2,0,k)ans=(ans+f[n][m][i1][i2])%mod;
printf("%d",ans);
}高一一班的座位表是个n*m的矩阵。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而相邻两个同学如果能同时选文科或者理科，那么他们又将收获一些喜悦值。求全班的喜悦值总和的最大值。
题解太难写，转黄学长的吧（我太弱）
利用最小割考虑。 对于原图中所有相邻的两个人A，B，我们建边： s->A:cost[A文]+c[文][A][B]/2,s->B:cost[B文]+c[文][A][B]/2; A->t:cost[A理]+c[理][A][B]/2,B->t:costB[理]+c[理][A][B]/2; A<–>B:c[文][A][B]/2+c[理][A][B]/2
注意里面的AB之间的无向边是一门玄学，当它满载时表示AB分属不同集合，而且无向边不需要反向边（要反向边也行），用的是普通图的插边方式。还有那些除以2只要将cost*2，然后最后求出来的最小割除以2就行。最后答案是所有收益和减最小割。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define visit(i,j) for(int i=g[j];i!=-1;i=es[i].n)
#define INF 0x3fffffff
using namespace std;
struct e{int t,c,n;}; e es[500000]; int ess,g[20000];
inline void pe(int f,int t,int c){es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;}
inline void pe2(int f,int t,int c){es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,c,g[t]}; g[t]=ess;}
inline void init(){ess=-1; memset(g,-1,sizeof(g));}
queue <int> q; int h[20000];
bool bfs(int s,int t){
while(! q.empty())q.pop(); memset(h,-1,sizeof(h)); q.push(s); h[s]=0;
while(! q.empty()){
int x=q.front(); q.pop();
visit(i,x)if(es[i].c&&h[es[i].t]==-1){h[es[i].t]=h[x]+1; q.push(es[i].t);}
}
if(h[t]==-1)return 0;else return 1;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=0;
visit(i,x)if(es[i].c&&h[es[i].t]==h[x]+1){
int w=dfs(es[i].t,t,min(f,es[i].c));
f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(f==0)return u;
}
if(!u)h[x]=-1; return u;
}
int dinic(int s,int t){int f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f;}
int a1[200][200],a2[200][200],tot,n,m,s,t;
inline int cg(int x,int y){return (x-1)*m+y;}
int main(){
scanf("%d%d",&n,&m); tot=0;
inc(i,1,n)inc(j,1,m)scanf("%d",&a1[i][j]),tot+=a1[i][j],a1[i][j]<<=1;
inc(i,1,n)inc(j,1,m)scanf("%d",&a2[i][j]),tot+=a2[i][j],a2[i][j]<<=1;
s=0; t=n*m+1; init();
inc(i,1,n-1)inc(j,1,m){
int x; scanf("%d",&x); a1[i][j]+=x; a1[i+1][j]+=x; tot+=x; pe2(cg(i,j),cg(i+1,j),x);
}
inc(i,1,n-1)inc(j,1,m){
int x; scanf("%d",&x); a2[i][j]+=x; a2[i+1][j]+=x; tot+=x; pe2(cg(i,j),cg(i+1,j),x);
}
inc(i,1,n)inc(j,1,m-1){
int x; scanf("%d",&x); a1[i][j]+=x; a1[i][j+1]+=x; tot+=x; pe2(cg(i,j),cg(i,j+1),x);
}
inc(i,1,n)inc(j,1,m-1){
int x; scanf("%d",&x); a2[i][j]+=x; a2[i][j+1]+=x; tot+=x; pe2(cg(i,j),cg(i,j+1),x);
}
inc(i,1,n)inc(j,1,m){pe(s,cg(i,j),a1[i][j]); pe(cg(i,j),t,a2[i][j]);}
printf("%d",tot-(dinic(s,t)>>1));
return 0;
}一块土地可以纵横划分为N×M块小区域。于第i行第j列的区域，建造商业区将得到Aij收益，建造工业区将得到Bij收益。而如果区域(i,j)相邻（相邻是指两个格子有公共边）有K块（显然K不超过4）类型不同于(i,j)的区域，则这块区域能增加k×Cij收益。已知收益矩阵A,B,C，求收益最大值。
因为附加收益不是两两之间的，所以不用考虑除以2的问题。由于需要两块土地属性不同，所以对整个棋盘进行黑白染色。如果一块土地A为黑色，则s->A :c[A商] A->T:c[A工]，如果为白色则反之s->A:c[A工] A->T:c[A商]，对于相邻的AB A<->B c[A合]+c[B合]。最后答案是所有收益和减最小割。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define visit(i,j) for(int i=g[j];i!=-1;i=es[i].n)
#define INF 0x3fffffff
using namespace std;
struct e{int t,c,n;}; e es[500000]; int ess,g[20000];
inline void pe(int f,int t,int c){es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;}
inline void pe2(int f,int t,int c){es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,c,g[t]}; g[t]=ess;}
inline void init(){ess=-1; memset(g,-1,sizeof(g));}
queue <int> q; int h[20000];
bool bfs(int s,int t){
while(! q.empty())q.pop(); memset(h,-1,sizeof(h)); q.push(s); h[s]=0;
while(! q.empty()){
int x=q.front(); q.pop();
visit(i,x)if(es[i].c&&h[es[i].t]==-1){h[es[i].t]=h[x]+1; q.push(es[i].t);}
}
if(h[t]==-1)return 0;else return 1;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=0;
visit(i,x)if(es[i].c&&h[es[i].t]==h[x]+1){
int w=dfs(es[i].t,t,min(f,es[i].c));
f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(f==0)return u;
}
if(!u)h[x]=-1; return u;
}
int dinic(int s,int t){int f=0; while(bfs(s,t))f+=dfs(s,t,INF); return f;}
int a1[200][200],a2[200][200],a3[200][200],tot,n,m,s,t; bool col[200][200];
inline int cg(int x,int y){return (x-1)*m+y;}
int main(){
scanf("%d%d",&n,&m); tot=0;
inc(i,1,n)inc(j,1,m)scanf("%d",&a1[i][j]),tot+=a1[i][j];
inc(i,1,n)inc(j,1,m)scanf("%d",&a2[i][j]),tot+=a2[i][j];
inc(i,1,n)inc(j,1,m)scanf("%d",&a3[i][j]);
s=0; t=n*m+1; init();inc(i,1,n)inc(j,1,m){col[i][j]=(i+j)&1;}
inc(i,1,n)inc(j,1,m){
if(col[i][j])pe(s,cg(i,j),a1[i][j]),pe(cg(i,j),t,a2[i][j]);else pe(s,cg(i,j),a2[i][j]),pe(cg(i,j),t,a1[i][j]);
if(i!=n)pe2(cg(i,j),cg(i+1,j),a3[i][j]+a3[i+1][j]),tot+=(a3[i][j]+a3[i+1][j]);
if(j!=m)pe2(cg(i,j),cg(i,j+1),a3[i][j]+a3[i][j+1]),tot+=(a3[i][j]+a3[i][j+1]);
}
printf("%d",tot-dinic(s,t));
return 0;
}在一个n*n的网格中，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这 个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，且不能走出整个n*n的网格。游戏开始时，你可以自由选定机器人的初始位置。已知一段时间内，鼹鼠出现的时间和地点，求机器人在这一段时间内最多打死多少鼹鼠。
一道类似求最长公共子串的题，枚举打一只地鼠前是打完哪只地鼠后到达的，因为数据弱使用不用加奇怪优化。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int f[20000],t[20000],x[20000],y[20000];
int main(){
int n,m; scanf("%d%d",&n,&m); int ans=0;
inc(i,1,m){
scanf("%d%d%d",&t[i],&x[i],&y[i]); int mx=0;
inc(j,1,i-1)if(t[i]-t[j]>=abs(x[i]-x[j])+abs(y[i]-y[j]))mx=max(mx,f[j]);
f[i]=mx+1; ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}有一个n×2的棋盘，第一列里面某些格子是雷，而第二列没有雷。由于第一列的雷可能有多种方案满足第二列的信息的限制，求根据第二列的信息第一列雷有多少种摆放方案。
水题，因为每个第一行的格子可以根据前一个第二行的格子里的信息唯一确定是否有雷，所以只要枚举第一个格子有没有雷就行。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int a[20000],b[10000];
int main(){
int n; scanf("%d",&n); inc(i,1,n)scanf("%d",&a[i]),b[i]=a[i];
int ans=0;
b[1]--; b[2]--;
inc(i,2,n){
if(b[i-1]<0||b[i]<0)break;
if(b[i-1]>1)break;else if(b[i-1]==1)b[i-1]--,b[i]--,i!=n?b[i+1]--:i;
if(i==n&&b[i]==0)ans++;
}
inc(i,2,n){
if(a[i-1]<0||a[i]<0)break;
if(a[i-1]>1)break;else if(a[i-1]==1)a[i-1]--,a[i]--,i!=n?a[i+1]--:i;
if(i==n&&a[i]==0)ans++;
}
printf("%d",ans);
return 0;
}超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R，其美妙度为包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。现需创作一首由k个不同的超级和弦组成的乐曲。定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。求能够创作出来的乐曲美妙度最大值是多少。
乍一看很难，实际上是可做的。题目实际上是求前k大的区间。设计状态(x,l,r,y,z)表示左端点为x，右端点在l到r之间的区间最大值为y且最大的区间右端点为z。预处理求出所有(i,i+L-1,i+R-1)的状态放入按y排的优先队列。枚举k次，每次从优先队列中取出最大的累加它的y，然后这个区间不能取了，所以求(x,l,z-1)和(x,z+1,r)再放入优先队列。怎么求这些状态？因为做端点是固定的，所以求区间s[l..r]的RMQ就行了，预处理时顺便求出f数组以便于求RMQ的时候用倍增。反思：我觉得RMQ的倍增和LCA的倍增是一样的，所以就用了求LCA的倍增写法，过倒是能过，速度不知道会不会慢一点。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
using namespace std;
struct node{
int f,l,r,a1,a2;
bool operator < (const node&a)const{
return a1<a.a1;
}
};
int n,k,l,r,f1[600000][20],f2[600000][20],s[600000];
priority_queue <node> q;
void add(int f,int l,int r){
if(l==r){q.push((node){f,l,r,s[l]-s[f-1],l}); return;}
if(l>r)return;
int a1=r-l,a2=-INF,a3,a4=l;
for(int i=0;(1<<i)<=a1;i++)if(a1&(1<<i)){
if(f1[a4][i]>a2)a2=f1[a4][i],a3=f2[a4][i]; a4+=(1<<i);
}
q.push((node){f,l,r,a2-s[f-1],a3});
}
int main(){
scanf("%d%d%d%d",&n,&k,&l,&r);
s[0]=0; inc(i,1,n){int a; scanf("%d",&a); s[i]=s[i-1]+a;}
inc(i,1,n-1)f1[i][0]=max(s[i],s[i+1]),f2[i][0]=s[i]>s[i+1]?i:i+1;
for(int j=1;(1<<j)<=n;j++)inc(i,1,n)if(i+(1<<j)<=n){
f1[i][j]=max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
f2[i][j]=s[f2[i][j-1]]>s[f2[i+(1<<(j-1))][j-1]]?f2[i][j-1]:f2[i+(1<<(j-1))][j-1];
}
inc(i,1,n)add(i,i+l-1,min(i+r-1,n)); long long ans=0;
inc(i,1,k){
node now=q.top(); q.pop(); ans=ans+(long long)now.a1; add(now.f,now.l,now.a2-1); add(now.f,now.a2+1,now.r);
}
printf("%lld",ans);
return 0;
}在N×N的棋盘里面放K个国王，使他们互不攻击，求共有多少种摆放方案。国王能攻击到它上下左右及左上左下右上右下八个方向上附近的一个格子，共8个格子。
状压dp。我的做法是像插头dp那样保存当前列右侧的上一行和当前列左侧的当前行的情况，同时加一列存左上角的状态，逐格递推，滚动掉行列的状态表示。过倒是过了然而是状态版上的倒数第一。我状压dp递推的时候不知道怎么省状态，可能写记忆化搜索会快一些，但就不能滚动了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
long long x[100][10000],y[100][10000],n,k;
inline bool bit(int x,int y){return x&(1<<(y-1));}
inline int set(int x,int y,bool z){
if(z)return x|(1<<(y-1));else return x&((1<<(n+1))-1-(1<<(y-1)));
}
int main(){
scanf("%d%d",&n,&k); x[k][0]=1;
inc(i1,1,n)inc(j1,1,n){
inc(i2,0,k)inc(j2,0,(1<<(n+1))-1)y[i2][j2]=0;
inc(i2,0,k)inc(j2,0,(1<<(n+1))-1){
if(i2&&(j1==1||(! bit(j2,j1-1)))&&(i1==1||(! bit(j2,j1)))&&(i1==1||j1==1||(! bit(j2,n+1)))&&(j1==n||(! bit(j2,j1+1))))
y[i2-1][set(set(j2,n+1,bit(j2,j1)),j1,1)]+=x[i2][j2];
y[i2][set(set(j2,n+1,bit(j2,j1)),j1,0)]+=x[i2][j2];
}swap(x,y);
}
long long ans=0; inc(i,0,(1<<(n+1))-1)ans+=x[0][i]; printf("%lld",ans);
return 0;
}