有n个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。求最小死人数和最大死人数。n≤1000000。
最小死人数：先找到所有入度为1的点放入队列，让它们活，接下来它们杀人，之后又出现入度为1的点，将其放入队列，重复上述操作。直到最后剩一些环，每个环的死人数是(sz[i]+1)/2。
最大死人数：求出联通块，对于一个联通块，如果它只有一个点，那么杀死此人；如果它没有入度为0的点，死人数为sz[i]-1；否则死人数为sz[i]-入度为0的点数。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1000010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,tar[maxn];
struct solve1{
queue<int>q; int cnt[maxn],ans,sz[maxn]; bool die[maxn],ok[maxn];
void dfs(int x){
sz[x]=1; if(!sz[tar[x]])dfs(tar[x]),sz[x]+=sz[tar[x]];
}
void solve(){
inc(i,1,n)cnt[tar[i]]++; inc(i,1,n)if(!cnt[i])q.push(i);
while(!q.empty()){
int x=q.front(); q.pop(); ok[x]=1;
if(!die[tar[x]]){
die[tar[x]]=1; ans++; ok[tar[x]]=1;
if(!die[tar[tar[x]]]&&cnt[tar[tar[x]]]){
cnt[tar[tar[x]]]--; if(!cnt[tar[tar[x]]])q.push(tar[tar[x]]);
}
}
}
inc(i,1,n)if(!ok[i]&&!sz[i])dfs(i),ans+=(sz[i]+1)/2;
printf("%d ",ans);
}
}solve1;
struct solve2{
int cnt[maxn],ans,sz[maxn],g[maxn],ess,tot; struct e{int t,n;}es[maxn*2];
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess;}
void dfs(int x){
sz[x]=1; if(!cnt[x])tot++;
for(int i=g[x];i;i=es[i].n)if(!sz[es[i].t])dfs(es[i].t),sz[x]+=sz[es[i].t];
}
void solve(){
inc(i,1,n)cnt[tar[i]]++; inc(i,1,n){pe(i,tar[i]); pe(tar[i],i);}
inc(i,1,n)if(!sz[i]){
tot=0; dfs(i); if(sz[i]==1)ans+=1;else if(!tot)ans+=sz[i]-1;else ans+=sz[i]-tot;
}
printf("%d",ans);
}
}solve2;
int main(){
n=read(); inc(i,1,n)tar[i]=read(); solve1.solve(); solve2.solve(); return 0;
}有一个奶牛队列。每次可以在原来队列的首端或是尾端牵出一头奶牛，把她安排到新队列的尾部，然后对剩余的奶牛队列重复以上的操作，直到所有奶牛都被插到了新的队列里。这样得到的队列，就是FJ拉去登记的最终的奶牛队列。 求对于给定的奶牛们的初始位置，计算出可能得到的字典序最小的队列。队列大小≤30000。
有一个结论：如果当前队列中的队首元素不等于队尾元素，则选小的那一边；否则选以右端点为下标的前缀和以左端点为下标的后缀中较小的那边。对于比较前缀后缀，正解是后缀数组，然而本弱偷懒写了个哈希，比较两个字符串的大小只要二分LCP，然后比较LCP的下一个字符即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 30010
#define ll unsigned long long
#define num 233
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
ll hash1[maxn],hash2[maxn],mi[maxn]; int l,r,n,tot; char name1[maxn],name2[maxn],ans[maxn];
bool cmp(int x,int y){
int l=1,r=min(n-x+1,y),z=0;
while(l<=r){
int mid=(l+r)>>1;
if(hash1[x+mid-1]-hash1[x-1]*mi[mid]==hash2[n-y+1+mid-1]-hash2[(n-y+1)-1]*mi[mid])z=mid,l=mid+1;else r=mid-1;
}
return name1[x+z]<=name2[n-y+1+z];
}
int main(){
n=read(); inc(i,1,n)scanf("%s",name1+i); inc(i,1,n)name2[i]=name1[n-i+1]; mi[0]=1;
inc(i,1,n)hash1[i]=hash1[i-1]*num+name1[i],hash2[i]=hash2[i-1]*num+name2[i],mi[i]=mi[i-1]*num;
l=1; r=n;
while(l<r){
if(name1[l]<name1[r])ans[++tot]=name1[l],l++;
else if(name1[l]>name1[r])ans[++tot]=name1[r],r--;
else if(cmp(l,r))ans[++tot]=name1[l],l++;
else ans[++tot]=name1[r],r--;
}
ans[++tot]=name1[l]; inc(i,1,tot){printf("%c",ans[i]); if(i%80==0)puts("");} return 0;
}John记录了n天的牛奶质量值。他想知道最长的出现了至少k次的模式（即一个连续子串）的长度。n≤20000。
求一个总哈希值，二分模式长度，枚举每个模式开始端点，获得它的哈希值，然后排序比较有没有至少k个相等。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 20010
#define ll unsigned long long
#define yyl 2333
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
ll hash[maxn],mi[maxn],calc[maxn],pat[maxn]; int n,k,l,r,ans,tot;
int main(){
n=read(); k=read(); inc(i,1,n)pat[i]=read(); mi[0]=1;
inc(i,1,n)hash[i]=hash[i-1]*yyl+pat[i],mi[i]=mi[i-1]*yyl; l=1; r=n;
while(l<=r){
int mid=(l+r)>>1; tot=0; inc(i,mid,n)calc[++tot]=hash[i]-hash[i-mid]*mi[mid];
sort(calc+1,calc+tot+1); int x=0,y=0;
inc(i,1,tot){if(!x||calc[i]!=calc[x])x=i; y=max(y,i-x+1);}
if(y>=k)ans=mid,l=mid+1;else r=mid-1;
}
printf("%d",ans); return 0;
}在一个树上求三个点两两距离相等的方案数。n≤5000。
枚举每个点作为中心点，求出每个子树的深度为i的节点大小，则目标是求某个深度的答案和。
设第i个子树在某个深度的节点数为dep[i]，令\(a1[i]=\sum_{j=1}^{i}{dep[j]}\)；则取两个节点的答案a2[i]=dep[i]*a1[i-1]，取三个节点的答案为a3[i]=dep[i]*a2[i-1]为所求，故递推求即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 5010
#define ll long long
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct e{int t,n;}es[maxn*2]; int g[maxn],ess;
void pe(int f,int t){
es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;
}
int n,dep[maxn]; ll a1[maxn],a2[maxn],a3[maxn],ans;
void dfs(int x,int fa,int d){
dep[d]++; for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa)dfs(es[i].t,x,d+1);
}
int main(){
n=read(); inc(i,1,n-1){int x=read(),y=read(); pe(x,y);}
inc(i,1,n){
int tot=0; memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2)); memset(a3,0,sizeof(a3));
for(int j=g[i];j;j=es[j].n){
memset(dep,0,sizeof(dep)); dfs(es[j].t,i,1); tot++;
inc(k,1,n){
if(tot>=3){a3[k]+=a2[k]*dep[k]; a2[k]+=a1[k]*dep[k]; a1[k]+=dep[k];}
if(tot==2){a2[k]+=a1[k]*dep[k]; a1[k]+=dep[k];}
if(tot==1)a1[k]+=dep[k];
}
}
inc(j,1,n)ans+=a3[j];
}
printf("%lld",ans); return 0;
}给出一个序列，m个询问，每次问一个序列是否为所给序列的子序列（可以不连续）。n≤1000000，m≤1000000，询问序列总长度≤1000000。
以元素的值为第一关键字，位置为第二关键字排序。接着对于每次询问，二分查找询问序列中元素在给出序列的最早出现次数，如果后一个数的最早出现次数大于等于前一个则输出NIE。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1000010
#define INF 0x3fffffff
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct nd{int v,id;}nds[maxn]; bool cmp(nd a,nd b){return a.v==b.v?a.id<b.id:a.v<b.v;}
int n,l,m;
int main(){
n=read(); inc(i,1,n)nds[i].v=read(),nds[i].id=i; sort(nds+1,nds+1+n,cmp); m=read(); nds[n+1].v=INF;
inc(i,1,m){
l=read(); int pos=0; bool f=0;
inc(j,1,l){
int x=read(); if(!f){
int y=lower_bound(nds+1,nds+n+2,(nd){x,pos},cmp)-nds;
if(nds[y].v!=x){puts("NIE"); f=1;} pos=nds[y].id+1;
}
}
if(!f)puts("TAK");
}
return 0;
}给一个图染色，要求每个图必须染上某个色同时与另外一个色的点有边相连，问可否满足要求。n≤200000。
直接上结论：除非有点没有与别的点相连，否则肯定能满足要求。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 200010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
bool f[maxn]; int n,m;
int main(){
n=read(); m=read(); inc(i,1,m){int x=read(),y=read(); f[x]=f[y]=1;}
inc(i,1,n)if(!f[i]){puts("NIE"); goto end;} puts("TAK");
end: return 0;
}Jasio有n个不同的玩具，它们都被放在了很高的架子上，地板上不会有超过k个玩具。当Jasio想玩地板上的其他玩具时，他会自己去拿，如果他想玩的玩具在架子上,他的妈妈则会帮他去拿,当她拿玩具的时候,顺便也会将一个地板上的玩具放上架子使得地板上有足够的空间。他的妈妈知道孩子的p个请求，求通过决定每次换玩具时换下哪个所能使他妈妈架子上拿玩具的次数的最小值。k≤100000，p≤500000。bzoj1826中的玩具种类需离散化。
首先求出每个请求的下一次对同种类玩具的请求的位置。之后维护一个优先队列求当前地板上玩具的下次请求位置，每次换玩具时把下次请求位置最大的弹出。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 500010
#define INF 0x3fffffff
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct nd{
int v,id; bool operator < (const nd&a)const{return v<a.v;}
};
priority_queue<nd>q;
int n,k,p,a[maxn],next[maxn],tot,ans,last[maxn]; bool zsye[maxn];
int main(){
n=read(); k=read(); p=read(); inc(i,1,p)a[i]=read();
inc(i,1,n)last[i]=p+1; for(int i=p;i>=1;i--)next[i]=last[a[i]],last[a[i]]=i;
inc(i,1,p){
if(!zsye[a[i]]){
if(tot<k){
zsye[a[i]]=1; ans++; tot++;
if(next[i])q.push((nd){next[i],a[i]});else q.push((nd){p+1,a[i]});
}else{
zsye[a[i]]=1; ans++; nd x=q.top(); q.pop(); zsye[x.id]=0;
if(next[i])q.push((nd){next[i],a[i]});else q.push((nd){p+1,a[i]});
}
}else{
q.push((nd){next[i],a[i]});
}
}
printf("%d",ans); return 0;
}给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。n≤200000。
结论：按某维坐标排序后，只有相邻两个点的距离才可能是这两个点的最小距离。故本题只要对所有点先按横坐标排序，将相邻的点连边，再对所有点按纵坐标排序，将相邻的点连边，之后求一次最短路即可。注意，本题数据大，spfa不能过（加了SLF也不行）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 200010
#define INF 10000000000000000
#define ll long long
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,x[maxn],y[maxn],id[maxn]; struct e{int t; ll w; int n;}es[maxn*4]; int ess,g[maxn];
void pe(int f,int t,ll w){
es[++ess]=(e){t,w,g[f]}; g[f]=ess; es[++ess]=(e){f,w,g[t]}; g[t]=ess;
}
bool cmp1(int a,int b){return x[a]<x[b];} bool cmp2(int a,int b){return y[a]<y[b];}
struct hn{int u; ll d; bool operator < (const hn&a)const{return d>a.d;}};
ll d[maxn]; bool vis[maxn]; priority_queue<hn>q;
ll dijkstra(){
inc(i,1,n)d[i]=INF; d[1]=0; q.push((hn){1,0});
while(!q.empty()){
int x; while(!q.empty()&&vis[x=q.top().u])q.pop(); if(vis[x])break; vis[x]=1;
for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){
d[es[i].t]=d[x]+es[i].w; q.push((hn){es[i].t,d[es[i].t]});
}
}
return d[n];
}
int main(){
n=read(); inc(i,1,n)x[i]=read(),y[i]=read(); inc(i,1,n)id[i]=i;
sort(id+1,id+n+1,cmp1); inc(i,1,n-1)pe(id[i],id[i+1],abs(x[id[i+1]]-x[id[i]]));
sort(id+1,id+n+1,cmp2); inc(i,1,n-1)pe(id[i],id[i+1],abs(y[id[i+1]]-y[id[i]]));
printf("%lld",dijkstra()); return 0;
}在一棵树中选最少的点建塔，使得每个点都有塔或相邻点有塔。n≤10000。
贪心。dfs时对于每个当前点，在dfs完它的所有子节点后如果它以及它的儿子以及它的父亲没塔，则在它父亲处建塔。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct e{int t,n;}es[2*maxn]; int ess,g[maxn];
void pe(int f,int t){
es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;
}
int n,ans; bool cov[maxn];
void dfs(int x,int fa){
bool f=0;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa){
dfs(es[i].t,x); if(cov[es[i].t])f=1;
}
if(!f&&!cov[x]&&!cov[fa])ans++,cov[fa]=1;
}
int main(){
n=read(); inc(i,1,n-1){int x=read(),y=read(); pe(x,y);} dfs(1,0); printf("%d",ans); return 0;
}折叠的定义如下：1. 一个字符串可以看成它自身的折叠。记作S。2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)。注意括号可以嵌套。给出字符串，求折叠后字符串的最短长度。
字符串长度≤100。
区间dp。f[i][j]=min(f[i][k]+f[k+1][j],f[i][k]+len(getnum(i,k,i,j)))。f[i][j]表示i到j的最短折叠长度。getnum(i,k,i,j)表示字符串[i..k]在字符串[i..j]中出现了几次（如果后者不是前者重复组成的返回正无穷），这个可以用哈希求。len表示一个数的长度，注意正无穷的长度为正无穷。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 110
#define ll unsigned long long
#define zsye 2333
#define INF 0x3fffffff
using namespace std;
int f[maxn][maxn],n; ll hash[maxn],mi[maxn];
char str[maxn];
ll get(int l,int r){
return hash[r]-hash[l-1]*mi[r-l+1];
}
int getnum(int l1,int r1,int l2,int r2){
if((r2-l2+1)%(r1-l1+1)!=0)return INF; ll orzzs=get(l1,r1);
inc(i,1,(r2-l2+1)/(r1-l1+1))if(orzzs!=get(l2+(i-1)*(r1-l1+1),l2+i*(r1-l1+1)-1))return INF;
return (r2-l2+1)/(r1-l1+1);
}
int numlen(int x){if(x==INF)return INF; int tot=0; while(x)x/=10,tot++; return tot;}
void dfs(int l,int r){
if(f[l][r]!=-1)return; inc(i,l,r-1)dfs(l,i),dfs(i+1,r); f[l][r]=INF;
inc(i,l,r-1)f[l][r]=min(f[l][r],f[l][i]+f[i+1][r]);
inc(i,l,r)f[l][r]=min(f[l][r],f[l][i]+2+numlen(getnum(l,i,l,r)));
}
int main(){
scanf("%s",str+1); n=strlen(str+1); mi[0]=1;
inc(i,1,n)hash[i]=hash[i-1]*zsye+str[i],mi[i]=mi[i-1]*zsye;
memset(f,-1,sizeof(f)); inc(i,1,n)f[i][i]=1;
dfs(1,n); printf("%d",f[1][n]); return 0;
}n头奶牛，每头牛会一些语言，总共有m种语言。求需让某些奶牛学会的最小语言数使得任意两只奶牛直接或间接可以用同种语言聊天（比如a会语言1，b会语言1和2，c会语言2和3，d会语言3则他们两两可以交流）。n≤10000，m≤30000。
如果一头奶牛会某种语言，则将这头奶牛与这种语言连边，最后答案为所得图联通块数-1。求联通块我用的是并查集。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 40010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int fa[maxn],n,m,ans; bool calced[maxn];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){int xx=find(x),yy=find(y); if(xx!=yy)fa[xx]=yy;}
int main(){
n=read(); m=read(); inc(i,1,n+m)fa[i]=i;
inc(i,1,n){
int x=read(); inc(j,1,x){int y=read(); merge(i,n+y);}
}
inc(i,1,n){int x=find(i); if(!calced[x])ans++,calced[x]=1;}
printf("%d",ans-1); return 0;
}有n张卡片在桌上一字排开，每张卡片上有两个数，第i张卡片上，正面的数为a[i]，反面的数为b[i]。有m个操作，第i个操作会交换c[i]和d[i]两个位置上的卡片。每次操作后，你都需要判断，通过任意翻转卡片（把正面变为反面或把反面变成正面，但不能改变卡片的位置），能否让卡片正面上的数从左到右单调不降。n≤200000，m≤1000000。
线段树每个节点维护对应区间若第一张卡片为较小一面得到的最后一张卡片的最小值以及若第一张卡片为较大一面得到的最后一张卡片的最小值（如果无法则为-1）。操作就对于普通线段树的单点修改。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 200010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int a[maxn],b[maxn],l[maxn*3],r[maxn*3],mn[maxn*3],mx[maxn*3],n,m;
void update(int x){
int lc=x<<1,rc=x<<1|1;
if(mn[lc]!=-1&&mn[rc]!=-1&&mn[lc]<=a[l[rc]])mn[x]=mn[rc];
else if(mn[lc]!=-1&&mx[rc]!=-1&&mn[lc]<=b[l[rc]])mn[x]=mx[rc];else mn[x]=-1;
if(mx[lc]!=-1&&mn[rc]!=-1&&mx[lc]<=a[l[rc]])mx[x]=mn[rc];
else if(mx[lc]!=-1&&mx[rc]!=-1&&mx[lc]<=b[l[rc]])mx[x]=mx[rc];else mx[x]=-1;
}
void build(int x,int bl,int br){
l[x]=bl; r[x]=br; if(bl==br){mn[x]=a[bl]; mx[x]=b[bl]; return;}
int mid=(bl+br)>>1; build(x<<1,bl,mid); build(x<<1|1,mid+1,br); update(x);
}
void modify(int x,int pos){
if(l[x]==r[x]){mn[x]=a[pos]; mx[x]=b[pos]; return;} int mid=(l[x]+r[x])>>1;
if(pos<=mid)modify(x<<1,pos);else modify(x<<1|1,pos); update(x);
}
int main(){
n=read(); inc(i,1,n){a[i]=read(); b[i]=read(); if(a[i]>b[i])swap(a[i],b[i]);}
build(1,1,n); m=read();
inc(i,1,m){
int c=read(),d=read(); int t1=a[c],t2=b[c];
a[c]=a[d]; b[c]=b[d]; modify(1,c); a[d]=t1; b[d]=t2; modify(1,d);
if(mn[1]==-1&&mx[1]==-1)puts("NIE");else puts("TAK");
}
return 0;
}给出一个矩阵，求这个矩阵中权值和第k小的长在xmin到n之间，宽在ymin到m之间的子矩阵。n，m≤1000，k≤250000。
首先求出长为xmin，宽为ymin的子矩阵放入优先队列，每次取出时如果该矩阵之前没有出现过（用set判重），则将其扩展并放入优先队列，输出第k个不重复的（这里指位置不重复的，权值可以相等）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int sum[maxn][maxn],n,m,xmin,ymin,k,tot;
struct nd{
int x,y,l,c,v;
bool operator < (const nd &a)const{
if(v!=a.v)return v>a.v; if(x!=a.x)return x<a.x; if(y!=a.y)return y<a.y;
if(l!=a.l)return l<a.l; return c<a.c;
};
};
priority_queue<nd>q; set<nd>st;
int main(){
n=read(); m=read(); xmin=read(); ymin=read(); k=read();
inc(i,1,n)inc(j,1,m){int x=read(); sum[i][j]=sum[i-1][j]-sum[i-1][j-1]+sum[i][j-1]+x;}
inc(i,1,n-xmin+1)inc(j,1,m-ymin+1){
q.push((nd){i,j,xmin,ymin,sum[i+xmin-1][j+ymin-1]-sum[i+xmin-1][j-1]-sum[i-1][j+ymin-1]+sum[i-1][j-1]});
}
while(!q.empty()){
nd x=q.top(); q.pop(); if(st.find(x)!=st.end())continue;
tot++; if(tot==k){printf("%d",x.v+1); break;} st.insert(x);
if(x.x+x.l<=n)
q.push((nd){x.x,x.y,x.l+1,x.c,sum[x.x+x.l][x.y+x.c-1]-sum[x.x+x.l][x.y-1]-sum[x.x-1][x.y+x.c-1]+sum[x.x-1][x.y-1]});
if(x.y+x.c<=m)
q.push((nd){x.x,x.y,x.l,x.c+1,sum[x.x+x.l-1][x.y+x.c]-sum[x.x+x.l-1][x.y-1]-sum[x.x-1][x.y+x.c]+sum[x.x-1][x.y-1]});
if(x.x+x.l<=n&&x.y+x.c<=m)
q.push((nd){x.x,x.y,x.l+1,x.c+1,sum[x.x+x.l][x.y+x.c]-sum[x.x+x.l][x.y-1]-sum[x.x-1][x.y+x.c]+sum[x.x-1][x.y-1]});
}
return 0;
}匪徒准备从一个车站转移毒品到另一个车站，警方准备进行布控。对于每个车站进行布控都需要一定的代价，现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后，匪徒无法从原定的初始点到达目标点。n≤200。
每个点拆成两个点，边权为点权，原图中的边边权为正无穷，然后跑最小割。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 60010
#define INF 0x3fffffff
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct e{int t,c,n;}es[maxn*2]; int g[maxn],ess;
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;
}
int h[maxn]; queue<int>q;
bool bfs(int s,int t){
memset(h,-1,sizeof(h)); while(!q.empty())q.pop(); h[s]=0; q.push(s);
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i;i=es[i].n)if(es[i].c&&h[es[i].t]==-1)h[es[i].t]=h[x]+1,q.push(es[i].t);
}
return h[t]!=-1;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=0,w;
for(int i=g[x];i;i=es[i].n)if(es[i].c&&h[es[i].t]==h[x]+1){
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)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 n,m,s,t;
int main(){
n=read(); m=read(); s=read(); t=n+read(); ess=1; inc(i,1,n){int x=read(); pe(i,n+i,x);}
inc(i,1,m){int x=read(),y=read(); pe(n+x,y,INF); pe(n+y,x,INF);} printf("%d",dinic(s,t)); return 0;
}给出一个n个数的序列，问有多少个长度为m的区间满足该区间的最大值与最小值的差≤一个定值。n≤1000000。
两个单调队列，一个维护区间最大值，一个维护区间最小值。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct nd{int v,pos;};
struct dddl{
deque<nd>mx; deque<nd>mn;
void insert(int x,int y){
while(!mx.empty()&&x>=mx.back().v)mx.pop_back(); mx.push_back((nd){x,y});
while(!mn.empty()&&x<=mn.back().v)mn.pop_back(); mn.push_back((nd){x,y});
}
void erase(int x){
while(!mx.empty()&&x>=mx.front().pos)mx.pop_front();
while(!mn.empty()&&x>=mn.front().pos)mn.pop_front();
}
}dddl;
int n,m,c,a[maxn]; bool f;
int main(){
n=read(); m=read(); c=read(); inc(i,1,m){int x=read(); dddl.insert(x,i);} f=0;
if(dddl.mx.front().v-dddl.mn.front().v<=c)printf("%d\n",1),f=1;
inc(i,m+1,n){
dddl.erase(i-m); int x=read(); dddl.insert(x,i);
if(dddl.mx.front().v-dddl.mn.front().v<=c)printf("%d\n",i-m+1),f=1;
}
if(!f)puts("NONE"); return 0;
}给出一个由“\”“/”组成的电路图，长为n，宽为m，求最少将几个“"改成”/“或将”/“改成”"使左上角和左下角联通。n,m<=500
如果某格是/，则左上角和右下角连边，长度为0，左下角和右上角连边，长度为1；如果某格是，则左上角和右下角连边，长度为1，左下角和右上角连边，长度为0，然后求最短路即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 300010
#define INF 0x3fffffff
using namespace std;
char str[maxn]; struct e{int t,w,n;}es[maxn*4]; int g[maxn],ess;
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 n,m;
struct nd{int d,u; bool operator < (const nd &a)const{return d>a.d;}};
int d[maxn]; bool vis[maxn]; priority_queue<nd>q;
void dijkstra(int s,int t){
inc(i,s,t)d[i]=INF; d[s]=0; q.push((nd){0,s});
while(!q.empty()){
int x; while(!q.empty()&&vis[x=q.top().u])q.pop(); if(vis[x])break; vis[x]=1;
for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){
d[es[i].t]=d[x]+es[i].w; q.push((nd){d[es[i].t],es[i].t});
}
}
}
int main(){
scanf("%d",&n); scanf("%d",&m);
inc(i,1,n){
scanf("%s",str+1);
inc(j,1,m){
if(str[j]=='\\')pe((i-1)*(m+1)+j,i*(m+1)+j+1,0),pe((i-1)*(m+1)+j+1,i*(m+1)+j,1);
else pe((i-1)*(m+1)+j,i*(m+1)+j+1,1),pe((i-1)*(m+1)+j+1,i*(m+1)+j,0);
}
}
dijkstra(1,(n+1)*(m+1));
d[(n+1)*(m+1)]==INF?printf("NO SOLUTION"):printf("%d",d[(n+1)*(m+1)]); return 0;
}给一棵树，问去掉哪个点后可以使剩下的每个子树大小都小于等于节点总数的一半。n≤10000。
dfs的时候求一下子树大小，以当前节点的父节点为根节点的子树大小为n-以当前节点为根节点的子树大小。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct e{int t,n;}es[maxn*2]; int ess,g[maxn];
void pe(int f,int t){
es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;
}
int sz[maxn],n,ans[maxn],tot;
void dfs(int x,int fa){
int mx=0; sz[x]=1; for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa){
dfs(es[i].t,x); sz[x]+=sz[es[i].t]; mx=max(mx,sz[es[i].t]);
}
mx=max(mx,n-sz[x]); if(mx<=n/2)ans[++tot]=x;
}
int main(){
n=read(); inc(i,1,n-1){int x=read(),y=read(); pe(x,y);} dfs(1,0);
if(!tot){printf("NONE"); return 0;}
sort(ans+1,ans+1+tot); inc(i,1,tot)printf("%d\n",ans[i]); return 0;
}给个有向图，每个点有个点权，有些点有酒吧。现在求一个人从任意一点出发获得点权的最大和。要求每个点的点权只能获得一次，且路径最后必须在酒吧结束，可以重复经过点和边。n，m≤500000。
tarjan缩点之后跑spfa，注意不能用dijkstra，因为求正权边的最长路相当于求最短路时有负权边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 500010
#define INF 0x3fffffff
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct e{int t,n;}es[2][maxn]; int g[2][maxn],ess[2];
void pe(int f,int t,bool o){es[o][++ess[o]]=(e){t,g[o][f]}; g[o][f]=ess[o];}
int v[2][maxn],scc[maxn],tot,n,m,s,p,ans;
bool ins[maxn]; int tim,low[maxn],dfn[maxn]; stack<int>st;
void tarjan(int x){
ins[x]=1; low[x]=dfn[x]=++tim; st.push(x);
for(int i=g[0][x];i;i=es[0][i].n){
if(!dfn[es[0][i].t])tarjan(es[0][i].t),low[x]=min(low[x],low[es[0][i].t]);
else if(ins[es[0][i].t])low[x]=min(low[x],dfn[es[0][i].t]);
}
if(low[x]==dfn[x]){
tot++;
while(!st.empty()){
int y=st.top(); st.pop(); ins[y]=0; scc[y]=tot;
v[1][tot]+=v[0][y]; if(x==y)break;
}
}
}
int d[maxn]; bool inq[maxn]; deque<int>q;
void spfa(int s){
inc(i,1,tot)d[i]=-1; d[s]=v[1][s]; inq[s]=1; q.push_back(s);
while(!q.empty()){
int x=q.front(); q.pop_front(); inq[x]=0;
for(int i=g[1][x];i;i=es[1][i].n)if(d[es[1][i].t]<d[x]+v[1][es[1][i].t]){
d[es[1][i].t]=d[x]+v[1][es[1][i].t];
if(!inq[es[1][i].t]){
if(!q.empty()&&d[es[1][i].t]<d[q.front()])q.push_front(es[1][i].t);else q.push_back(es[1][i].t);
inq[es[1][i].t]=1;
}
}
}
}
int main(){
n=read(); m=read(); inc(i,1,m){int x=read(),y=read(); pe(x,y,0);} inc(i,1,n)v[0][i]=read();
s=read(); p=read(); inc(i,1,n)if(!dfn[i])tarjan(i);
inc(i,1,n){
for(int j=g[0][i];j;j=es[0][j].n)
if(scc[i]!=scc[es[0][j].t])pe(scc[i],scc[es[0][j].t],1);
}
spfa(scc[s]); inc(i,1,p){int x=read(); if(d[scc[x]]!=-1)ans=max(ans,d[scc[x]]);}
printf("%d",ans); return 0;
}给出一个序列，有两个元素ai、bi，要求将一个序列分成几段，每段的bi和不能超过l，每段的代价为该段最大的ai，求一个方案使代价和最小。n≤100000。
首先方程为f[i]=f[j]+mx[j+1..i],sum[i]-sum[j]<=l。但这样会T。令g[j]=mx[j+1..i]，则g[j]关于j单调不上升，故每次转移时bi只会修改到前面几个g[j]。所以可以把相同的g[j]合并为一块，记录这一块的头节点和尾节点，用一个set维护f[j]+g[j]和一个队列维护所有的块，每次看队列头的块的头节点是否不满足sum[i]-sum[j]<=l，如果不满足则删头结点，在删头节点时如果把尾节点也删了说明整个块都被删，出队列，接着用bi去更新队尾的比它小的g[j]块，将它们合并，而f[i]就是当前set里面的最小值，注意要开long long。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#define ll long long
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
multiset<ll>st;
int n,l,h[maxn],ql,qr; ll sm[maxn],f[maxn]; struct nd{int f,t;}q[maxn];
int main(){
n=read(); l=read(); ql=1; qr=0;
inc(i,1,n){
h[i]=read(); int w=read(); sm[i]=sm[i-1]+w; int x=i;
while(ql<=qr&&h[i]>=h[q[qr].t]){
st.erase(st.find(f[q[qr].f-1]+h[q[qr].t])); x=q[qr].f; qr--;
}
q[++qr]=(nd){x,i}; st.insert(f[q[qr].f-1]+h[i]);
while(ql<=qr&&sm[i]-sm[q[ql].f-1]>l){
st.erase(st.find(f[q[ql].f-1]+h[q[ql].t])); q[ql].f++;
if(q[ql].f>q[ql].t)ql++;else st.insert(f[q[ql].f-1]+h[q[ql].t]);
}
f[i]=*st.begin();
}
printf("%lld",f[n]); return 0;
}给一个有向图，每个点对答案的贡献为该点可达的点个数，求答案。n≤2000，m≤4000000。
听说暴力可过QAQ不过为了练tanjan还是写了常规写法。
先缩点，接着对每个入度为0的点做dp，每个点维护一个bitset。对于当前点，先将该点对应bitset的该点位置置为1，之后将这个bitset与该点所有子节点的bitset合并，然后枚举每个点，如果该点对应在bitset位置为1，则答案加上当前点的在原图中代表的点个数*该点在原图中代表的点个数。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <bitset>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 2010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct e{int t,n;}es[2][maxn*maxn]; int ess[2],g[2][maxn];
void pe(int f,int t,bool o){
es[o][++ess[o]]=(e){t,g[o][f]}; g[o][f]=ess[o];
}
int dfn[maxn],low[maxn],tim,scc[maxn],sz[maxn],tot,ans,n; bool ins[maxn],not0[maxn]; stack<int>st;
void tarjan(int x){
dfn[x]=low[x]=++tim; ins[x]=1; st.push(x);
for(int i=g[0][x];i;i=es[0][i].n){
if(!dfn[es[0][i].t])tarjan(es[0][i].t),low[x]=min(low[x],low[es[0][i].t]);
else if(ins[es[0][i].t])low[x]=min(low[x],dfn[es[0][i].t]);
}
if(dfn[x]==low[x]){
tot++; while(1){int y=st.top(); st.pop(); ins[y]=0; scc[y]=tot; sz[tot]++; if(x==y)break;}
}
}
bitset<maxn>bs[maxn]; bool vis[maxn];
void dfs(int x){
vis[x]=1; bs[x][x]=1;
for(int i=g[1][x];i;i=es[1][i].n){if(!vis[es[1][i].t])dfs(es[1][i].t); bs[x]|=bs[es[1][i].t];}
inc(i,1,tot)if(bs[x][i])ans+=sz[x]*sz[i];
}
char s[maxn];
int main(){
n=read(); inc(i,1,n){scanf("%s",s+1); inc(j,1,n)if(s[j]-'0')pe(i,j,0);} inc(i,1,n)if(!dfn[i])tarjan(i);
inc(i,1,n)
for(int j=g[0][i];j;j=es[0][j].n)
if(scc[i]!=scc[es[0][j].t])pe(scc[i],scc[es[0][j].t],1),not0[scc[es[0][j].t]]=1;
inc(i,1,tot)if(!not0[i])dfs(i); printf("%d",ans); return 0;
}一个瓶子有n个节，每个节有一个宽度。现在要从上往下扔m个盘子，如果盘子的下一个位置宽度比该盘子的宽度小则盘子会停在这个位置。问最后一个盘子会停在那个位置。n，m≤300000。
首先利用单调栈去掉那些没用的节，之后对于每个盘子，二分大于等于它宽度的第一个节，尝试它能否再往下掉到无用的节，具体看代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 300010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int st[maxn],stn[maxn],top,n,m,sz[maxn];
int main(){
n=read(); m=read(); inc(i,1,n)sz[i]=read();
for(int i=n;i>=1;i--){while(top&&sz[i]<st[top])top--; st[++top]=sz[i]; stn[top]=n-i+1;}
int now=1;
inc(i,1,m){
int x=read(); int pos=lower_bound(st+now,st+top+1,x)-st;
if(pos>top){printf("%d",0); return 0;}
if(i==m)printf("%d",n-(stn[pos]-stn[pos-1]>1?stn[pos-1]+1:stn[pos])+1);
if(stn[pos]-stn[pos-1]>1)now=pos,stn[pos-1]++;else now=pos+1;
}
return 0;
}给一个无向图，k个询问求节点a到节点b最长边的最小值。n，k≤15000。
”最长边的最小值“经常可以用最小生成树解决，因为生成树里的每一条边都是可取的最小边，求完生成树之后就是经典的倍增应用：求lca的时候顺便维护一下边权最大值即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 30010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct abc{int f,t,w;}abcd[maxn]; bool cmp(abc a,abc b){return a.w<b.w;}
struct e{int t,w,n;}es[maxn*2]; int g[maxn],ess;
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 n,m,k,p[maxn],fa[20][maxn],mx[20][maxn],tot,dep[maxn];
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
void dfs(int x){
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[0][x])
fa[0][es[i].t]=x,mx[0][es[i].t]=es[i].w,dep[es[i].t]=dep[x]+1,dfs(es[i].t);
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y); int t=dep[x]-dep[y],ans=0;
for(int i=0;(1<<i)<=n;i++)if(t&(1<<i))ans=max(ans,mx[i][x]),x=fa[i][x];
for(int i=19;i>=0;i--)if(fa[i][x]!=fa[i][y])
ans=max(ans,mx[i][x]),ans=max(ans,mx[i][y]),x=fa[i][x],y=fa[i][y];
if(x==y)return ans;else{ans=max(ans,mx[0][x]); ans=max(ans,mx[0][y]); return ans;}
}
int main(){
n=read(); m=read(); k=read(); inc(i,1,n)p[i]=i;
inc(i,1,m){int x=read(),y=read(),z=read(); abcd[i]=(abc){x,y,z};} sort(abcd+1,abcd+m+1,cmp);
inc(i,1,m){
int x=find(abcd[i].f),y=find(abcd[i].t); if(x!=y)pe(x,y,abcd[i].w),p[x]=y,tot++; if(tot==n-1)break;
}
dfs(1);
for(int i=1;(1<<i)<=n;i++)inc(j,1,n)
fa[i][j]=fa[i-1][fa[i-1][j]],mx[i][j]=max(mx[i-1][j],mx[i-1][fa[i-1][j]]);
inc(i,1,k){int x=read(),y=read(); printf("%d\n",lca(x,y));}
return 0;
}n个农场，有k群牛要从一个农场到另一个农场（每群由一只或几只奶牛组成）飞机白天从农场1到农场n，晚上从农场n到农场1，上面有c个座位，问最多可以满足多少只牛的要求。n≤10000，k≤50000，c≤100。
用类似贪心的方法做，现将每个农场出发的牛组织成链表。先求早上：当飞机到达每个农场时，先让到达的奶牛下机，接着如果飞机未满，则将其填满，之后枚举剩下的奶牛，如果它们的目的地比坐在飞机上面的奶牛目的地近，就将其替换为当前奶牛，这一过程可以用multiset维护。晚上所有过程都倒过来再做一次即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
multiset<int,greater<int> >st1;
multiset<int>st2;
int n,m,k,now,ans; struct nd{int t,w,n;}nds[2][maxn*5]; int ess[2],g[2][maxn];
int main(){
n=read(); m=read(); k=read();
inc(i,1,n){
int x=read(),y=read(),z=read();
if(x<y)nds[0][++ess[0]]=(nd){y,z,g[0][x]},g[0][x]=ess[0];
else nds[1][++ess[1]]=(nd){y,z,g[1][x]},g[1][x]=ess[1];
}
now=0;
inc(i,1,m){
if(st1.find(i)!=st1.end()){int x=st1.erase(i); ans+=x; now-=x;}
for(int j=g[0][i];j;j=nds[0][j].n){
while(now<k&&nds[0][j].w)st1.insert(nds[0][j].t),nds[0][j].w--,now++;
if(now==k){
while(*st1.begin()>nds[0][j].t&&nds[0][j].w)
st1.erase(st1.begin()),st1.insert(nds[0][j].t),nds[0][j].w--;
}
}
}
now=0;
for(int i=m;i>=1;i--){
if(st2.find(i)!=st2.end()){int x=st2.erase(i); ans+=x; now-=x;}
for(int j=g[1][i];j;j=nds[1][j].n){
while(now<k&&nds[1][j].w)st2.insert(nds[1][j].t),nds[1][j].w--,now++;
if(now==k){
while(*st2.begin()<nds[1][j].t&&nds[1][j].w)
st2.erase(st2.begin()),st2.insert(nds[1][j].t),nds[1][j].w--;
}
}
}
printf("%d",ans); return 0;
}FJ有n头奶牛。FJ提供n种不同的技能供奶牛们学习，每头奶牛只能学习一门技能，每门技能都要有奶牛学习。 第i头奶牛学习第j门技能，FJ得到的分数S[i][j]。此外还有b个奖励，第i个奖励的格式是： Pi 、Ki 、Ai，表示的意义是：如果学习完前Ki门技能后的总得分（包括额外的奖励得分）不少于Pi，那么FJ还会得到额外的Ai分。求通过安排奶牛学习技能，所能取得的最高总得分。n，b≤20。
状压dp。f[i][S]表示当前考虑第i个技能，奶牛是否学习技能的状态为S，则f[i][S]=max(f[i-1][S&((1<<n)-1-(1<<(l-1)))]+s[l][i])然而这样可能会T因为复杂度是O(n^2*2^n)，所以可以先预处理出所有S中1的个数，之后在转移时只有bit[S]==i时才能发生转移。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 30
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,b,s[maxn][maxn],f[2][1500000],bit[1500000]; bool x,y;
struct nd{int p,a,n;}nds[maxn]; int g[maxn],tot;
int main(){
n=read(); b=read();
inc(i,1,b){int x=read(); nds[i].p=read(); nds[i].a=read(); nds[i].n=g[x]; g[x]=i;}
inc(i,1,n)inc(j,1,n)s[i][j]=read(); x=0; y=1;
inc(i,0,(1<<n)-1){bit[i]=0; inc(j,0,n-1)if(i&(1<<j))bit[i]++;}
inc(i,1,n){
inc(j,0,(1<<n)-1)if(bit[j]==i){
inc(l,1,n)if(j&(1<<(l-1)))f[y][j]=max(f[y][j],f[x][j&((1<<n)-1-(1<<(l-1)))]+s[l][i]);
for(int l=g[i];l;l=nds[l].n)if(f[y][j]>=nds[l].p)f[y][j]+=nds[l].a;
}
swap(x,y);
}
printf("%d",f[x][(1<<n)-1]); return 0;
}n只奶牛，第i只听力为vi，坐标为xi，两只奶牛聊天时音量是max(vi,vj)*abs(xi-xj)。求n(n-1)/2对奶牛的音量和。n≤20000。
首先所有奶牛按x排序，记录其位置，接着再按它们音量升序排序依次插入树状数组。维护两个树状数组，一个用来求位置比某奶牛大的坐标和和奶牛数，另一个用来求位置比某奶牛小的坐标和和奶牛数。对于每个插入的奶牛i，对答案的贡献是vi*位置比它大的坐标和与奶牛数*该奶牛的坐标的差，加上vi*位置比它小的坐标和与奶牛数*该奶牛的坐标的差的相反数。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 20010
#define ll long long
#define lb(x) x&-x
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct nd{int d,sz;}nds1[maxn],nds2[maxn]; int n; ll ans;
struct abc{int v,x,id;}abcd[maxn];
bool cmp1(abc a,abc b){return a.x<b.x;} bool cmp2(abc a,abc b){return a.v<b.v;}
void update1(int x,int y){while(x<=n)nds1[x].d+=y,nds1[x].sz++,x+=lb(x);}
void update2(int x,int y){while(x)nds2[x].d+=y,nds2[x].sz++,x-=lb(x);}
nd query1(int x){nd q=(nd){0,0}; while(x>=1)q.d+=nds1[x].d,q.sz+=nds1[x].sz,x-=lb(x); return q;}
nd query2(int x){nd q=(nd){0,0}; while(x<=n)q.d+=nds2[x].d,q.sz+=nds2[x].sz,x+=lb(x); return q;}
int main(){
n=read(); inc(i,1,n)abcd[i].v=read(),abcd[i].x=read(); sort(abcd+1,abcd+n+1,cmp1);
inc(i,1,n)abcd[i].id=i; sort(abcd+1,abcd+n+1,cmp2);
inc(i,1,n){
nd a=query1(abcd[i].id-1); ans+=(ll)abcd[i].v*(abcd[i].x*a.sz-a.d);
a=query2(abcd[i].id+1); ans+=(ll)abcd[i].v*(a.d-abcd[i].x*a.sz);
update1(abcd[i].id,abcd[i].x); update2(abcd[i].id,abcd[i].x);
}
printf("%lld",ans); return 0;
}n只奶牛，每只支持两个球队中的一个，它们依次上车，上到一定程度可以开走这辆车并换下一辆继续上。要求一辆车上支持不同球队的奶牛数的差≤I，或者这辆车上只有支持同一球队的牛。问通过安排换车时机所能得到的车数的最小值。n≤2500。
f[i]=f[j]+1,abs(sum[0][i]-sum[0][j]-sum[1][i]+sum[1][j])<=I||sum[0][i]==sum[0][j]||sum[1][i]==sum[1][j]。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 2510
#define INF 0x3fffffff
using namespace std;
inline int read(){
char ch=getchar(); int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return f*x;
}
int n,k,sum[2][maxn],f[maxn]; char s[3];
int main(){
n=read(); k=read();
inc(i,1,n){
scanf("%s",s); sum[0][i]=sum[0][i-1]; sum[1][i]=sum[1][i-1];
if(s[0]=='J')sum[0][i]++;else sum[1][i]++;
}
inc(i,1,n){
f[i]=INF;
inc(j,0,i-1)if(abs(sum[0][i]-sum[0][j]-sum[1][i]+sum[1][j])<=k||sum[0][i]-sum[0][j]==0||sum[1][i]-sum[1][j]==0)
f[i]=min(f[i],f[j]+1);
}
printf("%d",f[n]); return 0;
}