有一个S串和一大堆T串，不断地在S串里找最早出现的T串，然后将其删除。S串≤100000，T串总长度≤100000。
对所有T串建AC自动机，然后同bzoj3942。注意，本题的AC自动机必须利用所有fail函数建成一个大的状态图，否则会超时。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
using namespace std;
char str[maxn],word[maxn],st1[maxn]; int ch[maxn][26],val[maxn],n,fail[maxn],top,pos,len,st2[maxn],tot;
inline void insert(char *str){
int j=0,len=strlen(str+1);
inc(i,1,len){if(!ch[j][str[i]-'a'])ch[j][str[i]-'a']=++tot; j=ch[j][str[i]-'a'];} val[j]=len;
}
queue <int> q;
void getfail(){
inc(i,0,25)if(ch[0][i])q.push(ch[0][i]);
while(!q.empty()){
int x=q.front(); q.pop();
inc(i,0,25){
int j=ch[fail[x]][i];
if(ch[x][i]){fail[ch[x][i]]=j; q.push(ch[x][i]);}else{ch[x][i]=j;}
}
}
}
int main(){
scanf("%s",str+1); len=strlen(str+1); scanf("%d",&n);
inc(i,1,n){scanf("%s",word+1); insert(word);} getfail(); top=0; pos=0;
inc(i,1,len){
st1[++top]=str[i]; pos=ch[pos][str[i]-'a']; st2[top]=pos; if(val[pos])top-=val[pos],pos=st2[top];
}
inc(i,1,top)printf("%c",st1[i]); return 0;
}把A串中所有字母替换成该字母在B串中的位置，如果有相同字母，则按从左到右的顺序一一对应，之后求逆序对个数即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1000010
#define lb(x) x&-x
using namespace std;
char a[maxn],b[maxn]; int n,p[maxn],id[maxn],sm[maxn]; long long ans;
queue <int> q[26];
int query(int x){int q=0; while(x){q+=sm[x],x-=lb(x);} return q;}
void add(int x,int v){while(x<=n)sm[x]+=v,x+=lb(x);}
int main(){
scanf("%d",&n); scanf("%s",a+1); scanf("%s",b+1); inc(i,1,n)q[b[i]-'A'].push(i);
inc(i,1,n)p[i]=q[a[i]-'A'].front(),q[a[i]-'A'].pop(); inc(i,1,n)id[p[i]]=i;
for(int i=n;i>=1;i--)ans+=query(id[i]-1),add(id[i],1); printf("%lld",ans); return 0;
}n只奶牛各有一个目的地。它们按顺序从根节点到达自己的目的地，如果当前奶牛经过了其它已经到达的奶牛的目的地，就要放慢一次脚步。求每只奶牛要放慢多少次脚步。n≤100000。
对树dfs，求每个节点的进栈时间和出栈时间，然后当每只奶牛到目的地时，将目的地的进栈时间对应数组元素+1，出栈时间对应数组元素-1。每只奶牛的放慢脚步次数就是它出发前它的目的地进栈时间对应数组元素的前缀和。这一过程用树状数组维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
#define inc(i,j,k) for(int i=j;i<=k;i++)
#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;
}
int l[maxn],r[maxn],ho[maxn],sm[maxn*2],n,tot;
struct e{int t,n;}; e 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;}
void dfs(int x,int fa){l[x]=++tot; for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa)dfs(es[i].t,x); r[x]=++tot;}
int query(int x){int q=0; while(x)q+=sm[x],x-=lb(x); return q;}
void add(int x,int v){while(x<=tot)sm[x]+=v,x+=lb(x);}
int main(){
n=read(); inc(i,1,n-1)pe(read(),read()); inc(i,1,n)ho[i]=read(); dfs(1,0);
inc(i,1,n){printf("%d\n",query(l[ho[i]])); add(l[ho[i]],1); add(r[ho[i]],-1);} return 0;
}给个集合，求所有子集的元素和的异或和。集合元素个数≤1000，整个集合的元素和≤2000000
用bitset维护每个子集元素和的个数是奇数还是偶数。每次读入一个元素，则bs^=bs<<a[i]，意思是将之前所有的子集和加上这个新的元素，然后与已有的子集和异或判断奇偶。最后ans为所有存在个数为奇数的子集和的异或和。注意本题数据有误，不能快速读入，必须用scanf否则会RE……
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
bitset<2000010>bs; int sm,ans,n;
int main(){
scanf("%d",&n); bs[0]=1; inc(i,1,n){int x; scanf("%d",&x); sm+=x; bs^=(bs<<x);}
inc(i,1,sm)if(bs[i])ans^=i; printf("%d",ans); return 0;
}n个地方，在其中找k对地方，每个地方只属于一对。定义一对的费用为两个地方的距离，求最小费用总和。
把所有相邻地方距离放入一个集合中，每次取出最小的那个距离x，然后将相邻两边的距离l，r合并成l+r-x。如果这个x缺一边相邻，则将剩下那一边的距离去掉，如果缺两边相邻，则不用去掉。这个找相邻的过程用链表维护，同时找最小距离以及删距离的操作用set维护（好像也可以用手写堆，然而我不会）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
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,a[maxn]; long long ans;
struct sn{
int pos,v;
bool operator < (const sn &x)const{return v!=x.v?v<x.v:pos<x.pos;}
};
set<sn>s;
struct nd{int v,l,r;}; nd nds[maxn];
int main(){
n=read(); k=read(); int st=read(); inc(i,1,n-1){int x=read(); a[i]=x-st; st=x;} n--;
inc(i,1,n){s.insert((sn){i,a[i]}); nds[i]=(nd){a[i],i-1,i+1>n?0:i+1};}
inc(i,1,k){
set<sn>::iterator xx=s.begin(); int x=xx->pos; ans+=xx->v; s.erase(xx);
if(!nds[x].l&&!nds[x].r)continue;
else if(!nds[x].r){
xx=s.find((sn){nds[x].l,nds[nds[x].l].v}); s.erase(xx); nds[nds[nds[x].l].l].r=0;
}else if(!nds[x].l){
xx=s.find((sn){nds[x].r,nds[nds[x].r].v}); s.erase(xx); nds[nds[nds[x].r].r].l=0;
}else{
nds[x].v=nds[nds[x].l].v+nds[nds[x].r].v-nds[x].v;
xx=s.find((sn){nds[x].l,nds[nds[x].l].v}); s.erase(xx);
xx=s.find((sn){nds[x].r,nds[nds[x].r].v}); s.erase(xx);
s.insert((sn){x,nds[x].v});
nds[x].l=nds[nds[x].l].l; nds[x].r=nds[nds[x].r].r; nds[nds[x].l].r=x; nds[nds[x].r].l=x;
}
}
printf("%lld",ans); return 0;
}给一个序列，求不超过m个连续的部分，使元素和最大。序列大小≤100000
先把连续的正数和负数合并起来，接着如果正数个数小于m则全选，否则需要确定去掉那个正数或合并哪个正数。初始ans设为所有正数和，将所有的数按绝对值大小放入堆中，然后重复m-正数个数操作：每次选取绝对值最小的数，如果是负数且它在边界处则重新选，否则将这个数删除并将两边的数合并，同时ans-=该数绝对值。该操作的意义在于：如果删去的是正数表示不选它，否则表示选这个负数以将左右的的正数合并起来。类似于1150，我用链表和STLset维护这个过程。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
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,m,a[maxn],b[maxn],tot,ans;
struct sn{
int pos,v;
bool operator < (const sn &x)const{return v!=x.v?v<x.v:pos<x.pos;}
};
set<sn>s;
struct nd{int v,l,r; bool bit;}; nd nds[maxn];
int main(){
n=read(); m=read(); inc(i,1,n)b[i]=read();
int last=0; inc(i,1,n){
if(b[i]==0)continue; if(!last||(last>0^b[i]>0))a[++tot]=b[i];else a[tot]+=b[i]; last=b[i];
}
n=tot; tot=0; inc(i,1,n)if(a[i]>0)tot++,ans+=a[i];
if(tot>m){
inc(i,1,n){s.insert((sn){i,abs(a[i])}); nds[i]=(nd){abs(a[i]),i-1,i+1>n?0:i+1,a[i]>0};}
inc(i,1,tot-m){
set<sn>::iterator xx; int x;
while(1){
xx=s.begin(); x=xx->pos; s.erase(xx);
if((!nds[x].l||!nds[x].r)&&!nds[x].bit){
if(!nds[x].l)nds[nds[x].r].l=0; if(!nds[x].r)nds[nds[x].l].r=0;
}else break;
}
ans-=nds[x].v;
if(!nds[x].l&&!nds[x].r)continue;
else if(!nds[x].r)nds[nds[x].l].r=0;
else if(!nds[x].l)nds[nds[x].r].l=0;
else{
nds[x].v=nds[nds[x].l].v+nds[nds[x].r].v-nds[x].v; nds[x].bit=nds[nds[x].l].bit;
xx=s.find((sn){nds[x].l,nds[nds[x].l].v}); s.erase(xx);
xx=s.find((sn){nds[x].r,nds[nds[x].r].v}); s.erase(xx);
s.insert((sn){x,nds[x].v});
nds[x].l=nds[nds[x].l].l; nds[x].r=nds[nds[x].r].r; nds[nds[x].l].r=x; nds[nds[x].r].l=x;
}
}
}
printf("%d",ans); return 0;
}给出n，m，求用除了第i（1≤i≤n）个之外的物品填满容量为j（1≤j≤m）的背包的方法数。n，m≤2000。
令f[n][j]为所有物品可用填满j的方案数，F[i][j]为题目所求，则当j<a[i]时F[i][j]=f[n][j]，否则F[i][j]=f[n][j]-F[i][j-a[i]]。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 2001
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 f[maxn],c[maxn][maxn],n,m,a[maxn];
int main(){
n=read(); m=read(); inc(i,1,n)a[i]=read(); f[0]=1;
inc(i,1,n)for(int j=m;j>=a[i];j--)f[j]=(f[j]+f[j-a[i]])%10;
inc(i,1,n){
c[i][0]=1;
inc(j,1,m){if(j<a[i])c[i][j]=f[j];else c[i][j]=(f[j]+10-c[i][j-a[i]])%10; printf("%d",c[i][j]);}
puts("");
}
return 0;
}求一个≤10^16的数，使这个数包含123456789且为x的倍数。x≤1000000。
16-6刚好等于10。因此我们可以直接让所求的数的前10位为1234567890，则只要求出1234567890000000加上什么≤1000000的数可以为x的倍数即可，而这个可以很容易求出。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const long long a=1LL*1234567890*1000000;
int t; long long b;
int main(){
scanf("%d",&t); inc(i,1,t){scanf("%lld",&b); if(b)printf("%lld\n",a+b-a%b);else puts("-1");} return 0;
}求一个字符串中有多少个“luvletter”（不包括引号）。字符串长度≤100000。
连kmp都不用……
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
using namespace std;
char s[maxn]; char t[20]="luvletter";
int main(){
int T; scanf("%d\n",&T);
inc(i,1,T){
fgets(s+1,maxn,stdin); int len=strlen(s+1),now=0,ans=0;
inc(i,1,len){if(s[i]==t[now])now++; if(now==9)ans++,now=0;} printf("%d\n",ans);
}
return 0;
}有向图，每条边长度为1或2，求1到n最短路。点数≤100000，边数≤1000000。
有人说spfa会T，所以我用了dijkstra。不过这不是正解，神犇ZS告诉我正解应该是把所有边长度为2的边拆成两条，orz……
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#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,m,d[maxn]; bool vis[maxn];
struct e{int t,w,n;}; e es[maxn*10]; int ess,g[maxn];
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
struct hn{int u,w; bool operator <(const hn &a)const{return w>a.w;}}; priority_queue<hn>q;
int dijkstra(){
inc(i,1,n)d[i]=INF; d[1]=0; q.push((hn){1,0});
while(!q.empty()){
int x=q.top().u; while(!q.empty()&&vis[x])q.pop(),x=q.top().u; if(q.empty()&&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(); m=read(); inc(i,1,m){int a=read(),b=read(),c=read(); pe(a,b,c);}
printf("%d",dijkstra()); return 0;
}平面上n个点，求一个点使得离它最近的点和最远的点离它的曼哈顿距离差最小（若选的点处已有点，则改点不算）。n≤500000
第一次写kd树，感觉眼睛又瞎了（玄学复杂度）。首先先把所有点横坐标和纵坐标轮流为关键字排序建一个平衡树，维护每棵子树里的横纵坐标最大最小值。在树上查询时就启发式搜索，比如说正在查询里某点最远的点，则如果当前子树的横纵坐标最大最小值与某点的曼哈顿距离小于答案，就返回，否则对左右子树估价，那边越可能得到最优解就先往哪边走。这么暴力的操作，却可以证明，单次查询均摊复杂度为O(sqrt(n))。好神奇（不过常数应该不小）。
对应于本题，先将所有点建成kd树，然后有奇怪性质：所求点一定是这些点中的一个，所以枚举所有点，查询离这个点最远最近的点的与它的曼哈顿距离差，寻找最小的一个输出。估价函数具体见代码，注意求最远点和求最近点的估价函数不一样。
#include <cstdio>
#include <cstring>
#include <algorithm>
#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;
}
int n,f,rt,mxans,mnans;
struct p{int pos[2]; bool operator < (const p &a)const{return pos[f]<a.pos[f];}}ps[maxn];
struct nd{p pos; int mx[2],mn[2],lc,rc;}nds[maxn];
int dis(p a,p b){return abs(a.pos[0]-b.pos[0])+abs(a.pos[1]-b.pos[1]);}
void update(int x){
inc(i,0,1){
if(nds[x].lc)
nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].lc].mx[i]),
nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].lc].mn[i]);
if(nds[x].rc)
nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].rc].mx[i]),
nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].rc].mn[i]);
}
}
int build(int l,int r,int now){
f=now; int mid=(l+r)>>1; nth_element(ps+l,ps+mid,ps+r+1);
inc(i,0,1)nds[mid].mx[i]=nds[mid].mn[i]=ps[mid].pos[i]; nds[mid].pos=ps[mid];
if(l<mid)nds[mid].lc=build(l,mid-1,now^1); if(mid<r)nds[mid].rc=build(mid+1,r,now^1);
update(mid); return mid;
}
int getmax(int x,p a){
int q=0; inc(i,0,1)q+=max(abs(a.pos[i]-nds[x].mx[i]),abs(a.pos[i]-nds[x].mn[i])); return q;
}
int getmin(int x,p a){
int q=0; inc(i,0,1)q+=max(a.pos[i]-nds[x].mx[i],0),q+=max(nds[x].mn[i]-a.pos[i],0); return q;
}
void querymax(int x,p a){
mxans=max(mxans,dis(a,nds[x].pos)); int dl=0,dr=0;
if(nds[x].lc)dl=getmax(nds[x].lc,a); if(nds[x].rc)dr=getmax(nds[x].rc,a);
if(dl>dr){
if(mxans<dl)querymax(nds[x].lc,a); if(mxans<dr)querymax(nds[x].rc,a);
}else{
if(mxans<dr)querymax(nds[x].rc,a); if(mxans<dl)querymax(nds[x].lc,a);
}
}
void querymin(int x,p a){
if(dis(a,nds[x].pos))mnans=min(mnans,dis(a,nds[x].pos)); int dl=INF,dr=INF;
if(nds[x].lc)dl=getmin(nds[x].lc,a); if(nds[x].rc)dr=getmin(nds[x].rc,a);
if(dl<dr){
if(mnans>dl)querymin(nds[x].lc,a); if(mnans>dr)querymin(nds[x].rc,a);
}else{
if(mnans>dr)querymin(nds[x].rc,a); if(mnans>dl)querymin(nds[x].lc,a);
}
}
int query(p a){
mxans=0; querymax(rt,a); mnans=INF; querymin(rt,a); return mxans-mnans;
}
int main(){
n=read(); inc(i,1,n)ps[i].pos[0]=read(),ps[i].pos[1]=read(); rt=build(1,n,0);
int ans=INF; inc(i,1,n)ans=min(ans,query(ps[i])); printf("%d",ans); return 0;
}棋盘上有n个棋子，现在有m个操作，一种是加棋子，一种是查询离某个点最近的棋子。n，m≤500000。
先将已有的棋子建kd树，然后加棋子就直接向kd树插入节点。因为本题数据弱，所以直接插节点不会T，如果是一些数据比较强的题目，需要在插入一定量节点后重构整棵树。
#include <cstdio>
#include <cstring>
#include <algorithm>
#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;
}
int n,m,f,rt,ans;
struct p{int pos[2]; bool operator < (const p &a)const{return pos[f]<a.pos[f];}}ps[maxn];
struct nd{p pos; int mx[2],mn[2],lc,rc;}nds[maxn*2];
int dis(p a,p b){return abs(a.pos[0]-b.pos[0])+abs(a.pos[1]-b.pos[1]);}
void update(int x){
inc(i,0,1){
if(nds[x].lc)
nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].lc].mx[i]),
nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].lc].mn[i]);
if(nds[x].rc)
nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].rc].mx[i]),
nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].rc].mn[i]);
}
}
int build(int l,int r,int now){
f=now; int mid=(l+r)>>1; nth_element(ps+l,ps+mid,ps+r+1);
inc(i,0,1)nds[mid].mx[i]=nds[mid].mn[i]=ps[mid].pos[i]; nds[mid].pos=ps[mid];
if(l<mid)nds[mid].lc=build(l,mid-1,now^1); if(mid<r)nds[mid].rc=build(mid+1,r,now^1);
update(mid); return mid;
}
void insert(int &x,p a,int now){
if(!x){x=++n; inc(i,0,1)nds[x].mx[i]=nds[x].mn[i]=a.pos[i]; nds[x].pos=a; return;}
f=now; if(a<nds[x].pos)insert(nds[x].lc,a,now^1);else insert(nds[x].rc,a,now^1); update(x);
}
int get(int x,p a){
int q=0; inc(i,0,1)q+=max(a.pos[i]-nds[x].mx[i],0),q+=max(nds[x].mn[i]-a.pos[i],0); return q;
}
void query(int x,p a){
ans=min(ans,dis(a,nds[x].pos)); int dl=INF-1,dr=INF-1;
if(nds[x].lc)dl=get(nds[x].lc,a); if(nds[x].rc)dr=get(nds[x].rc,a);
if(dl<dr){
if(ans>dl)query(nds[x].lc,a); if(ans>dr)query(nds[x].rc,a);
}else{
if(ans>dr)query(nds[x].rc,a); if(ans>dl)query(nds[x].lc,a);
}
}
int main(){
n=read(); m=read(); inc(i,1,n)ps[i].pos[0]=read(),ps[i].pos[1]=read(); rt=build(1,n,0);
inc(i,1,m){
int t=read(),x=read(),y=read();
if(t==1)insert(rt,(p){x,y},0);else ans=INF,query(rt,(p){x,y}),printf("%d\n",ans);
}
return 0;
}n个巧克力，每个有牛奶含量，可可含量和美味值。m个人，每个有三个权值a，b，c，如果某个巧克力的牛奶含量*a+可可含量*b<c就可以接受。问每个人能接受的巧克力美味值之和。n，m≤50000。
对所有巧克力建kd树，树上节点除了维护子树横纵坐标最大最小值还要维护子树美味值之和。在查询时如果估价得出这个子树的牛奶含量最大值乘a+可可含量最大值*b小于c则整棵子树都能接受，否则只要该子树可能有机会存在可接受巧克力就遍历这棵子树。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50010
#define ll long long
using namespace std;
inline ll read(){
char ch=getchar(); ll 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,m,f,rt; ll ans;
struct p{int pos[2],v; bool operator < (const p &a)const{return pos[f]<a.pos[f];}}ps[maxn];
struct nd{p pos; int mx[2],mn[2],lc,rc; ll sm;}nds[maxn];
bool check(int a,int b,ll c,ll d,ll e){return c*a+d*b<e;}
void update(int x){
inc(i,0,1){
if(nds[x].lc)
nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].lc].mx[i]),
nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].lc].mn[i]);
if(nds[x].rc)
nds[x].mx[i]=max(nds[x].mx[i],nds[nds[x].rc].mx[i]),
nds[x].mn[i]=min(nds[x].mn[i],nds[nds[x].rc].mn[i]);
}
if(nds[x].lc)nds[x].sm+=nds[nds[x].lc].sm;
if(nds[x].rc)nds[x].sm+=nds[nds[x].rc].sm;
}
int build(int l,int r,int now){
f=now; int mid=(l+r)>>1; nth_element(ps+l,ps+mid,ps+r+1);
inc(i,0,1)nds[mid].mx[i]=nds[mid].mn[i]=ps[mid].pos[i]; nds[mid].sm=ps[mid].v; nds[mid].pos=ps[mid];
if(l<mid)nds[mid].lc=build(l,mid-1,now^1); if(mid<r)nds[mid].rc=build(mid+1,r,now^1);
update(mid); return mid;
}
int get(int x,ll a,ll b,ll c){
int q=0;
q+=check(nds[x].mx[0],nds[x].mx[1],a,b,c); q+=check(nds[x].mx[0],nds[x].mn[1],a,b,c);
q+=check(nds[x].mn[0],nds[x].mx[1],a,b,c); q+=check(nds[x].mn[0],nds[x].mn[1],a,b,c);
return q;
}
void query(int x,ll a,ll b,ll c){
if(check(nds[x].pos.pos[0],nds[x].pos.pos[1],a,b,c))ans+=nds[x].pos.v; int dl=0,dr=0;
if(nds[x].lc)dl=get(nds[x].lc,a,b,c); if(nds[x].rc)dr=get(nds[x].rc,a,b,c);
if(dl==4)ans+=nds[nds[x].lc].sm;else if(dl)query(nds[x].lc,a,b,c);
if(dr==4)ans+=nds[nds[x].rc].sm;else if(dr)query(nds[x].rc,a,b,c);
}
int main(){
n=read(); m=read(); inc(i,1,n)ps[i].pos[0]=read(),ps[i].pos[1]=read(),ps[i].v=read(); rt=build(1,n,0);
inc(i,1,m){
ll x=read(),y=read(),z=read(); ans=0; query(rt,x,y,z); printf("%lld\n",ans);
}
return 0;
}给定一个长度为n的序列，序列里的数≤k，m个询问l,r：求\(\sum_{i=1}^k{c[i]^2}\)，c[i]为i在[l,r]的出现次数。n，m，k≤50000。
莫队算法直接上。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50010
#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 ask{int l,r,id;}asks[maxn]; int bel[maxn],n,sz,m,k,l,r; ll ans,a[maxn],c[maxn],p[maxn];
bool cmp(ask a,ask b){return bel[a.l]==bel[b.l]?a.r<b.r:bel[a.l]<bel[b.l];}
ll sqr(ll a){return a*a;}
int main(){
n=read(); m=read(); k=read(); inc(i,1,n)a[i]=read(); sz=(int)sqrt(n);
inc(i,1,n)bel[i]=(i-1)/sz+1; inc(i,1,m)asks[i]=(ask){read(),read(),i};
sort(asks+1,asks+m+1,cmp); ans=0; l=1; r=0;
inc(i,1,m){
while(asks[i].r>r)r++,ans-=sqr(c[a[r]]),c[a[r]]++,ans+=sqr(c[a[r]]);
while(asks[i].l<l)l--,ans-=sqr(c[a[l]]),c[a[l]]++,ans+=sqr(c[a[l]]);
while(asks[i].r<r)ans-=sqr(c[a[r]]),c[a[r]]--,ans+=sqr(c[a[r]]),r--;
while(asks[i].l>l)ans-=sqr(c[a[l]]),c[a[l]]--,ans+=sqr(c[a[l]]),l++;
p[asks[i].id]=ans;
}
inc(i,1,m)printf("%lld\n",p[i]); return 0;
}求无向图点1到n的次短路（长度严格小于最短路）。点数≤5000，边数≤100000。
求源点为1的单源最短路和源点为n的单源最短路。然后枚举每个点，如果某点到点1和点n的距离和不等于1到n的最短路距离且最小则答案为它。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 5010
#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 f,t,w,n;}es[maxn*40]; int g[maxn],ess,d[2][maxn],n,m; bool inq[maxn]; queue<int>q;
void pe(int f,int t,int w){es[++ess]=(e){f,t,w,g[f]}; g[f]=ess; es[++ess]=(e){t,f,w,g[t]}; g[t]=ess;}
void spfa(int s,bool a){
while(!q.empty())q.pop(); memset(inq,0,sizeof(inq)); inc(i,1,n)d[a][i]=INF;
q.push(s); inq[s]=1; d[a][s]=0;
while(!q.empty()){
int x=q.front(); q.pop(); inq[x]=0;
for(int i=g[x];i;i=es[i].n)if(d[a][es[i].t]>d[a][x]+es[i].w){
d[a][es[i].t]=d[a][x]+es[i].w;
if(!inq[es[i].t])q.push(es[i].t),inq[es[i].t]=1;
}
}
}
int main(){
n=read(); m=read(); inc(i,1,m){int a=read(),b=read(),c=read(); pe(a,b,c);}
spfa(1,0); spfa(n,1); int mn=INF;
inc(i,1,ess){
if(d[0][es[i].f]+es[i].w+d[1][es[i].t]<mn&&d[0][es[i].f]+es[i].w+d[1][es[i].t]!=d[0][n])
mn=d[0][es[i].f]+es[i].w+d[1][es[i].t];
}
printf("%d",mn); return 0;
}给棵树，要求如果取了某个节点就不能取与它相邻的节点，问最多可取几个节点。树的大小≤50000。
树形dp。令f[i][0]不取i节点，f[i][1]为取i节点，则方程为f[i][0]=sum(max(f[j][0],f[j][1]+1)),f[i][1]=sum(f[j][0])，j为i的子节点。最后答案为max(f[1][0],f[1][1]+1)。注意不要漏了那个“+1”。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50010
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,n,dp[maxn][2];
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;}
void dfs(int x,int fa){
dp[x][0]=dp[x][1]=0;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa){
dfs(es[i].t,x); dp[x][0]+=max(dp[es[i].t][1]+1,dp[es[i].t][0]); dp[x][1]+=dp[es[i].t][0];
}
}
int main(){
n=read(); inc(i,1,n-1){int a=read(),b=read(); pe(a,b);} dfs(1,0);
printf("%d",max(dp[1][0],dp[1][1]+1)); return 0;
}K个硬币，要按顺序买N个物品。当选定买的东西物品序列后，付出钱后，货主是不会找零钱的。现希望通过改变硬币的顺序使买完所需要的东西后，留下的钱越多越好，如果不能完成购买任务，输出-1。k≤16，n≤100000。
状压dp。f[S]表示用硬币集合S所能买的最大物品数量。转移则是f[S]=f[S/i]+g(i)],g(i)等于coin[i]从f[S/coin[i]]+1开始能买的最大数量物品，而这个可以用前缀和加二分快速求出。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
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 sm[maxn],coin[maxn],k,n,dp[maxn],ans;
void update(int x){
int y=0; inc(i,1,k)if(!(x&(1<<(i-1))))y+=coin[i]; ans=max(ans,y);
}
int dfs(int x){
if(dp[x]!=-1)return dp[x]; dp[x]=0;
inc(i,1,k)if(x&(1<<(i-1))){
int y=dfs(x^(1<<(i-1))); dp[x]=max(dp[x],upper_bound(sm+1,sm+1+n,sm[y]+coin[i])-sm-1);
}
if(dp[x]==n)update(x); return dp[x];
}
int main(){
k=read(); n=read(); inc(i,1,k)coin[i]=read(); inc(i,1,n)sm[i]=read(),sm[i]+=sm[i-1];
memset(dp,-1,sizeof(dp)); ans=-1; dfs((1<<k)-1); printf("%d",ans); return 0;
}求无环图的最大流。边数≤700。
管它有没有环。注意本题的节点标号既有大写字母，也有小写字母。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100
#define INF 0x3fffffff
using namespace std;
struct e{int t,c,n;}es[maxn*80]; 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;
es[++ess]=(e){f,c,g[t]}; g[t]=ess; es[++ess]=(e){t,0,g[f]}; g[f]=ess;
}
queue<int>q; int h[maxn];
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();
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;
for(int i=g[x];i;i=es[i].n)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==0)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 s,t,n;
int main(){
scanf("%d",&n); ess=1; s=0; t='Z'-'A';
inc(i,1,n){char x[3],y[3]; int z; scanf("%s%s%d",x,y,&z); pe(x[0]-'A',y[0]-'A',z);}
printf("%d",dinic(s,t)); return 0;
}n头奶牛，每头有一个编号，求有多少种排列顺序使得相邻两头奶牛的编号差不超过k。n≤16。
状压dp。f[i][S]表示已选状态为S，上一个选的是i，满足要求的方案数，则f[i][S]=sum(f[j][S|j]),abs(num[i]-num[j])≤k。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
#define INF 0x3fffffff
using namespace std;
ll dp[20][80000]; int n,k,s[20];
ll dfs(int x,int y){
if(!y)return 1; if(dp[x][y]!=-1)return dp[x][y]; dp[x][y]=0;
inc(i,1,n)if((y&(1<<(i-1)))&&abs(s[i]-s[x])>k)dp[x][y]+=dfs(i,y^(1<<(i-1)));
return dp[x][y];
}
int main(){
scanf("%d%d",&n,&k); inc(i,1,n)scanf("%d",&s[i]); memset(dp,-1,sizeof(dp));
s[0]=-INF; printf("%lld\n",dfs(0,(1<<n)-1)); return 0;
}n*m的土地，有的土地不能种草。求有多少种种草方案使得没有两块草地相邻。n，m≤12。
先预处理出存在草地左右相邻的不合法状态，然后状压dp。f[i][S]表示当前处理第i行上一行状态为S，则f[i][S]=sum(f[i+1][T]),T满足没有草种在不能种的地上且不与上一行上下相邻同时不存在左右相邻。本来按道理来说这种方法是会超时的，然而似乎本题数据弱。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define mod 100000000
using namespace std;
int f[2][5000],t[20],n,m,x,y,ans; bool bad[5000];
int main(){
scanf("%d%d",&n,&m); inc(i,1,n){t[i]=0; inc(j,1,m){int x; scanf("%d",&x); t[i]+=((!x)<<(j-1));}}
inc(i,0,(1<<m)-1){
inc(j,1,m-1)if((i&(1<<(j-1)))&&(i&(1<<j))){bad[i]=1; break;}
}
x=0; y=1; inc(i,0,(1<<m)-1)if(!(i&t[n])&&!bad[i])f[x][i]=1;
for(int i=n-1;i>=1;i--){
inc(j,0,(1<<m)-1){
f[y][j]=0; if(!(j&t[i])&&!bad[j]){inc(k,0,(1<<m)-1)if(!(k&j))f[y][j]=(f[y][j]+f[x][k])%mod;}
}
swap(x,y);
}
inc(i,0,(1<<m)-1)ans=(ans+f[x][i])%mod; printf("%d",ans); return 0;
}n*n个房间，奶牛初始在(1,1)，且只能在亮的房间里活动。每当奶牛经过一个房间，就可以打开这个房间里控制其它房间灯的开关。问奶牛最多可点亮多少个房间。n≤100。
因为只要一个房间灯亮了，它将一直亮着，所以可以做bfs，每次由队列中的节点扩展可以到的节点。然而这样做不行，因为可能之前尝试过不能到达的房间的灯可以在之后到达的房间里被打开。解决方法是不停做bfs，直到答案不再更新。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 110
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 x,y,n;}nds[maxn*200]; int g[maxn][maxn];
int n,m,ans; bool lg[maxn][maxn],vis[maxn][maxn]; queue<pair<int,int> >q;
void bfs(int x,int y){
while(!q.empty())q.pop(); memset(vis,0,sizeof(vis)); q.push(make_pair(x,y)); vis[x][y]=1;
for(int i=g[x][y];i;i=nds[i].n)if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;
while(!q.empty()){
int nowx=q.front().first,nowy=q.front().second; q.pop();
if(nowx>1&&lg[nowx-1][nowy]&&!vis[nowx-1][nowy]){
q.push(make_pair(nowx-1,nowy)); vis[nowx-1][nowy]=1;
for(int i=g[nowx-1][nowy];i;i=nds[i].n)
if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;
}
if(nowx<n&&lg[nowx+1][nowy]&&!vis[nowx+1][nowy]){
q.push(make_pair(nowx+1,nowy)); vis[nowx+1][nowy]=1;
for(int i=g[nowx+1][nowy];i;i=nds[i].n)
if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;
}
if(nowy>1&&lg[nowx][nowy-1]&&!vis[nowx][nowy-1]){
q.push(make_pair(nowx,nowy-1)); vis[nowx][nowy-1]=1;
for(int i=g[nowx][nowy-1];i;i=nds[i].n)
if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;
}
if(nowy<n&&lg[nowx][nowy+1]&&!vis[nowx][nowy+1]){
q.push(make_pair(nowx,nowy+1)); vis[nowx][nowy+1]=1;
for(int i=g[nowx][nowy+1];i;i=nds[i].n)
if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;
}
}
}
int main(){
n=read(); m=read();
inc(i,1,m){
int a=read(),b=read(),c=read(),d=read(); nds[i]=(nd){c,d,g[a][b]}; g[a][b]=i;
}
ans=1; lg[1][1]=1;
while(1){int x=ans; bfs(1,1); if(ans==x)break;} printf("%d",ans); return 0;
}一共有2n张牌，Alice有n张，Bob有n张，每一局点数大的赢。知道Bob的出牌顺序，求Alice最多能赢几局。n≤50000。
贪心。将Alice和Bob的牌按点数大小排序，然后如果Alice当前牌能赢Bob当前牌就ans++否则就不断调整Bob的当前牌直到Alice当前牌能赢Bob当前牌。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50010
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],ans,n,tot; bool c[maxn*2];
int main(){
n=read(); inc(i,1,n)a[i]=read(),c[a[i]]=1; inc(i,1,2*n)if(!c[i])b[++tot]=i; sort(a+1,a+n+1);
int p=1,q=1;
while(1){
while(p<=n&&b[p]<a[q])p++; if(p==n+1)break; ans++; p++; q++;
}
printf("%d",ans); return 0;
}给定一个长度为N的序列，每个位置上的数只可能是1，2，3中的一种。有Q次询问，每次给定两个数a,b，请分别输出区间[a,b]里数字1，2，3的个数。n≤100000，q≤100000。
裸前缀和。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
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 sm[4][maxn],n,q;
int main(){
n=read(); q=read(); inc(i,1,n){int x=read(); inc(j,1,3)sm[j][i]=sm[j][i-1]; sm[x][i]++;}
inc(i,1,q){
int l=read(),r=read(); printf("%d %d %d\n",sm[1][r]-sm[1][l-1],sm[2][r]-sm[2][l-1],sm[3][r]-sm[3][l-1]);
}
return 0;
}奶牛一开始饱胀值为0，上限为T。每个柠檬派提供a点饱胀值，每个橘子派提供b点饱胀值，有一次机会喝水，使得饱胀值div2。柠檬派和橘子派有无限个，求最大饱胀值。T≤5000000。
dfs。f[i][1/0]表示当前饱胀值为i，是/否喝过水的状态能否达到。则由f[i][1]可递推出f[i+a][1]、f[i+b][1]，由f[i][0]可递推出f[i+a][0]、f[i+b][0]、f[i/2][1]。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 5000010
using namespace std;
bool vis[maxn][2]; int n,a,b,ans;
void dfs(int x,int y){
if(vis[x][y])return; vis[x][y]=1; if(x+a<=n)dfs(x+a,y); if(x+b<=n)dfs(x+b,y);
if(!y)dfs(x/2,1); ans=max(ans,x);
}
int main(){
scanf("%d%d%d",&n,&a,&b); memset(vis,0,sizeof(vis)); dfs(0,0); printf("%d",ans); return 0;
}给定一棵有N个点的树，所有节点的权值都为0。有K次操作，每次指定两个点s,t，将s到t路径上所有点的权值都加一。请输出K次操作完毕后权值最大的那个点的权值。n≤50000，k≤100000。
先链剖把树变为链。然后用数组区间加的方式（即在数组区间左端点位置增加值，数组区间右端点+1位置增加这个值的相反数，最后扫一遍a[i]+=a[i-1]）累计权值。类似bzoj3631
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50010
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 sm[maxn],sz[maxn],dep[maxn],fa[maxn],top[maxn],pos[maxn],n,q,ans,tot;
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;}
void dfs1(int x,int f){
sz[x]=1;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=f){
fa[es[i].t]=x; dep[es[i].t]=dep[x]+1; dfs1(es[i].t,x); sz[x]+=sz[es[i].t];
}
}
void dfs2(int x,int f,int tp){
pos[x]=++tot; top[x]=tp; int mx1=0,mx2=0;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=f&&sz[es[i].t]>mx1)mx1=sz[es[i].t],mx2=es[i].t;
if(!mx2)return; dfs2(mx2,x,tp);
for(int i=g[x];i;i=es[i].n)if(es[i].t!=f&&es[i].t!=mx2)dfs2(es[i].t,x,es[i].t);
}
void solve(int x,int y){
for(;top[x]!=top[y];sm[pos[top[x]]]++,sm[pos[x]+1]--,x=fa[top[x]])if(dep[top[x]]<dep[top[y]])swap(x,y);
if(dep[x]>dep[y])swap(x,y); sm[pos[x]]++; sm[pos[y]+1]--;
}
int main(){
n=read(); q=read(); inc(i,1,n-1){int x=read(),y=read(); pe(x,y);} dfs1(1,0); dfs2(1,0,1);
inc(i,1,q){int x=read(),y=read(); solve(x,y);}
inc(i,1,n)sm[i]+=sm[i-1],ans=max(ans,sm[i]); printf("%d",ans); return 0;
}给一个长度为n的序列a。1≤a[i]≤n。m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。n，m≤500000。
先建主席树，之后在查找时，只走size值大于(r-l+1)/2的节点，如果两个儿子的size值都≤(r-l+1)/2则返回0否则返回最后走到的叶子节点。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 500010
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 tot,sz[maxn*23],ch[maxn*23][2],rt[maxn],n,a[maxn],m;
void build(int &x,int l,int r){
x=++tot; sz[x]=0; if(l==r)return; int mid=(l+r)>>1; build(ch[x][0],l,mid); build(ch[x][1],mid+1,r);
}
void insert(int &x,int l,int r,int v){
tot++; sz[tot]=sz[x]+1; ch[tot][0]=ch[x][0]; ch[tot][1]=ch[x][1]; x=tot; if(l==r)return;
int mid=(l+r)>>1; if(v<=mid)insert(ch[x][0],l,mid,v); if(v>mid)insert(ch[x][1],mid+1,r,v);
sz[x]=sz[ch[x][0]]+sz[ch[x][1]];
}
int query(int ql,int qr){
int x=(qr-ql+1)>>1,l=1,r=n,y=rt[qr],z=rt[ql-1];
while(1){
int mid=(l+r)>>1;
if(sz[ch[y][0]]-sz[ch[z][0]]>x)y=ch[y][0],z=ch[z][0],r=mid;
else if(sz[ch[y][1]]-sz[ch[z][1]]>x)y=ch[y][1],z=ch[z][1],l=mid+1;
else if(l==r)return l; else return 0;
}
}
int main(){
n=read(); m=read(); build(rt[0],1,n); inc(i,1,n)rt[i]=rt[i-1],insert(rt[i],1,n,read());
inc(i,1,m){
int l=read(),r=read(); printf("%d\n",query(l,r));
}
return 0;
}在一条无限长的跑道上有N头牛，每头牛有自己的初始位置及奔跑的速度。牛之间不能互相穿透。当一只牛追上另一只牛时，它不得不慢下来，成为一个群体。求T分钟后一共有几个群体。n≤100000，t≤1000000000
如果慢车经过t时间到达的位置大于快车t时间到达的位置，则这两只车成为一个群体。具体看代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
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 p[maxn],v[maxn],n,slow,ans,t;
int main(){
n=read(); t=read(); inc(i,1,n)p[i]=read(),v[i]=read(); slow=n; ans=1;
for(int i=n-1;i>=1;i--){
if(1LL*p[i]+1LL*v[i]*t<1LL*p[slow]+1LL*v[slow]*t)ans++,slow=i;
}
printf("%d",ans); return 0;
}在二维平面上有N个点，从(x1,y1)到(x2,y2)的代价为|x1-x2|+|y1-y2|。求从1号点出发，按从1到N的顺序依次到达每个点的最小总代价。你有K次机会可以跳过某个点，不允许跳过1号点或N号点。n≤500。
dp。f[i][j]表示当前在i个点，剩j次，则f[i][j]=min(f[i+1][j]+abs(x[i+1]-x[i])+abs(y[i+1]-y[i]),f[i+k+1][j-k]),i+k+1≤n,k≤j。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 510
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,x[maxn],y[maxn],dp[maxn][maxn];
int dfs(int a,int b){
if(a==n)return 0; if(dp[a][b]!=-1)return dp[a][b];
dp[a][b]=dfs(a+1,b)+abs(x[a]-x[a+1])+abs(y[a]-y[a+1]);
inc(i,1,min(b,n-a-1))dp[a][b]=min(dp[a][b],dfs(a+i+1,b-i)+abs(x[a]-x[a+i+1])+abs(y[a]-y[a+i+1]));
return dp[a][b];
}
int main(){
n=read(); k=read(); inc(i,1,n)x[i]=read(),y[i]=read(); memset(dp,-1,sizeof(dp));
printf("%d",dfs(1,k)); return 0;
}给定一个N个点M条边的无向图，其中Bessie在1号点，Elsie在2号点，它们的目的地为N号点。Bessie每经过一条边需要消耗B点能量，Elsie每经过一条边需要消耗E点能量。当它们相遇时，它们可以一起行走，此时它们每经过一条边需要消耗P点能量。求它们两个到达N号点时最少消耗多少能量。n，m≤40000。
先求出以1、2、n为源点的最短路（因为边权为1所以用bfs）。答案初始设为1到n的最短路*B+2到n的最短路*E。接着枚举每个点，让该点到1最短路*B+该点到2最短路*E+该点到n的最短路*P和答案比较。
#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;
}
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 n,m,b,e,p,d[3][maxn]; long long ans; queue<int>q; bool vis[maxn];
void bfs(int s,int o){
while(!q.empty())q.pop(); memset(vis,0,sizeof(vis));
q.push(s); vis[s]=1; d[o][s]=0;
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i;i=es[i].n)if(!vis[es[i].t]){
d[o][es[i].t]=d[o][x]+1; q.push(es[i].t); vis[es[i].t]=1;
}
}
}
int main(){
b=read(); e=read(); p=read(); n=read(); m=read(); inc(i,1,m){int x=read(),y=read(); pe(x,y);}
bfs(1,0); bfs(2,1); bfs(n,2); ans=1LL*d[0][n]*b+1LL*d[1][n]*e;
inc(i,1,n)if(1LL*d[0][i]*b+1LL*d[1][i]*e+1LL*d[2][i]*p<ans)ans=1LL*d[0][i]*b+1LL*d[1][i]*e+1LL*d[2][i]*p;
printf("%lld",ans); return 0;
}给你一个N个点的有向图，设定初始位置为1，结束位置为n。有两个GPS定位系统,分别认为经过边i的时间为Pi,和Qi.每走一条边的时候,如果一个系统认为走的这条边不是它认为的最短路,就会受到警告一次。如果走的这条边都不在两个系统认为的最短路范围内,就会受到2次警告。求最少需要受到多少次警告。n≤10000，边数≤50000
分别按两个GPS的边权求最短路，然后枚举每条边，把该边的边权变为其警告数，然后再求一次最短路。判断该边是不是最短路的条件是是否dis[es[i].f]+es[i].w==dis[es[i].t]。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
#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 f,t,w,n;}es[maxn*5]; int g[maxn],ess;
void pe(int f,int t,int w){es[++ess]=(e){f,t,w,g[f]}; g[f]=ess;}
int n,m,a[2][maxn*5],b[maxn*5],d[2][maxn]; queue<int>q; bool inq[maxn];
void spfa(int s,int o){
while(!q.empty())q.pop(); memset(inq,0,sizeof(inq)); inc(i,1,n)d[o][i]=INF;
q.push(s); inq[s]=1; d[o][s]=0;
while(!q.empty()){
int x=q.front(); q.pop(); inq[x]=0;
for(int i=g[x];i;i=es[i].n)if(d[o][x]+es[i].w<d[o][es[i].t]){
d[o][es[i].t]=d[o][x]+es[i].w; if(!inq[es[i].t])q.push(es[i].t),inq[es[i].t]=1;
}
}
}
int main(){
n=read(); m=read(); inc(i,1,m){int x=read(),y=read(),z=read(); pe(y,x,z); a[0][i]=z; a[1][i]=read();}
spfa(n,0); inc(i,1,m)es[i].w=a[1][i]; spfa(n,1);
inc(i,1,m){inc(j,0,1)if(d[j][es[i].f]+a[j][i]>d[j][es[i].t])b[i]++; es[i].w=b[i];}
spfa(n,0); printf("%d",d[0][1]); return 0;
}依次给出n只奶牛的产奶时间段，求最大的k使得前k只奶牛不存在一个时间段被另一个时间段完全覆盖的情况。n≤100000。
设当前在处理第i只奶牛，前i-1只奶牛都合法。那么如果前i-1只奶牛中时间段左端点小于且最接近第i只奶牛时间段左端点的奶牛右端点大于当前奶牛则不合法，且如果前i-1只奶牛中时间段左端点大于且最接近第i只奶牛时间段左端点的奶牛右端点小于第i只奶牛则不合法，这是一个贪心的过程，可以用STLset维护。注意set要先插入一个+INF和负INF以防边界炸。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define INF 0x3fffffff
#define sit set<nd>::iterator
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 l,r; bool operator <(const nd&a)const{return l==a.l?r<a.r:l<a.l;}};
set<nd>s; int n;
int main(){
n=read(); s.insert((nd){INF,0}); s.insert((nd){-INF,0});
inc(i,1,n){
int x=read(),y=read();
s.insert((nd){x,y}); sit a=s.find((nd){x,y});
sit b=--a; a++; sit c=++a; a--;
if(b->r>=y&&b->l!=-INF){printf("%d",i-1); return 0;}
if(c->r<=y&&c->l!=INF){printf("%d",i-1); return 0;}
}
printf("%d",n); return 0;
}给一个无向图，每一条边都有一个阈值，有一些点有草。牛从点1出发，每当它到达有草的点可以选择吃或不吃，如果吃的话体重加1。对于边如果它的阈值小于牛的体重，则此边不可通过。求牛走一圈回到点1的最大体重。有草节点数≤14。点数≤100，边数≤1000。
f[i][S]表示当前点为i，草状态为S的状态能否达到。具体看代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 110
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,w,n;}es[maxn*20]; 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;
}
bool vis[maxn][17000]; int ans,a[17000],n,m,k,b[maxn];
void dfs(int x,int y){
if(vis[x][y])return; vis[x][y]=1; if(x==1)ans=max(ans,a[y]);
if(b[x]&&(y&(1<<(b[x]-1))))dfs(x,y^(1<<(b[x]-1)));
for(int i=g[x];i;i=es[i].n)if(es[i].w>=a[y])dfs(es[i].t,y);
}
int main(){
n=read(); m=read(); k=read(); inc(i,1,k){int x=read(); b[x]=i;}
inc(i,1,m){int x=read(),y=read(),z=read(); pe(x,y,z);}
inc(i,0,(1<<k)-1){inc(j,0,k-1)if(!(i&(1<<j)))a[i]++;} dfs(1,(1<<k)-1); printf("%d",ans); return 0;
}RMQ问题。序列长度≤25000，问题数≤25000。
倍增。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 25100
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,m,lg[maxn],mn[maxn][20];
int main(){
n=read(); m=read(); inc(i,1,n)mn[i][0]=read();
for(int i=0;1<<i<=n;i++)lg[1<<i]=i; inc(i,1,n)if(!lg[i])lg[i]=lg[i-1];
for(int i=1;1<<i<=n;i++)inc(j,1,n)if(j+(1<<i)-1<=n)mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]);
inc(i,1,m){
int a=read(),b=read(),c=lg[b-a+1];
printf("%d\n",min(mn[a][c],mn[b-(1<<c)+1][c]));
}
return 0;
}n个点，求最远曼哈顿距离。n≤50000。
曼哈顿距离转切比雪夫距离（点(x,y)变为点(x+y,x-y)），然后输出最大横坐标-最小横坐标与最大纵坐标-最小纵坐标的较大值即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50010
#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 x[maxn],y[maxn],n,ans,mx,mn;
int main(){
n=read(); inc(i,1,n){int a=read(),b=read(); x[i]=a+b; y[i]=a-b;} ans=0;
mx=-INF; mn=INF; inc(i,1,n)mx=max(mx,x[i]),mn=min(mn,x[i]); ans=max(ans,mx-mn);
mx=-INF; mn=INF; inc(i,1,n)mx=max(mx,y[i]),mn=min(mn,y[i]); ans=max(ans,mx-mn);
printf("%d",ans); return 0;
}平面直角坐标系有n个点，从(0,0)出发，从一个点上可以跳到所有与它横纵坐标距离都≤2的点上，求最少步数使得纵坐标为T。
先用set存下所有的点。在做dp的时候把所有横纵坐标与当前节点距离≤2的节点都在set中查找，如果可以查到则可以转移到那个节点。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#define maxn 50010
#define inc(i,j,k) for(int i=j;i<=k;i++)
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 x[maxn],y[maxn],n,t,dis[maxn]; queue<int>q;
struct nd{
int x,y,id;
bool operator < (const nd &a)const{return x!=a.x?x<a.x:y<a.y;}
};
set<nd>st;
int main(){
n=read(); t=read(); inc(i,1,n)x[i]=read(),y[i]=read(),st.insert((nd){x[i],y[i],i});
q.push(0); dis[0]=0;
while(!q.empty()){
int z=q.front(); q.pop();
inc(i,-2,2)inc(j,-2,2){
set<nd>::iterator a=st.find((nd){x[z]+i,y[z]+j,0});
if(a!=st.end()){
dis[a->id]=dis[z]+1; q.push(a->id);
if(a->y==t){printf("%d",dis[a->id]); return 0;} st.erase(a);
}
}
}
printf("-1"); return 0;
}求比一个数大的最小的一半以上的数位相同的数。数位数≤100。
模拟题。从低位枚举到高位，对于每一位枚举比原数该位大的数，同时枚举这一位之后要由0和哪一个数组成，最后得到一个最小的数输出。具体看代码。
有点像NOIP的那道Jam的计数法。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 110
using namespace std;
char str[maxn]; int sm[10][maxn],num[maxn],n;
int main(){
scanf("%s",str+1); n=strlen(str+1);
inc(i,1,n){num[i]=str[i]-'0'; inc(j,0,9)sm[j][i]=sm[j][i-1]; sm[num[i]][i]++;}
inc(i,num[n],9){
inc(j,0,9)if(sm[j][n-1]+(i==j)>n/2){inc(k,1,n-1)printf("%d",num[k]); printf("%d",i); return 0;}
}
for(int i=n-1;i>=1;i--){
inc(j,num[i]+1,9){
int mn1=n-i+1,mn2;
inc(k,0,9)if(n/2+1-(sm[k][i-1]+(k==j))<mn1)mn1=n/2+1-(sm[k][i-1]+(k==j)),mn2=k;
if(mn1!=n-i+1){
inc(k,1,i-1)printf("%d",num[k]); printf("%d",j); inc(k,1,n-i-mn1)printf("0");
inc(k,1,mn1)printf("%d",mn2); return 0;
}
}
}
}从一个序列中选n个数，要求这些数中不能有超过k个数在原序列中位置是连续的。求最大的取数之和。n≤100000。
f[i]表示不选i，1到i-1可以得到的最大取数之和。则f[i]=max(f[j]+sum[i-1]-sum[j]),i-j≤k。j比k好当且仅当f[j]+sum[i-1]-sum[j]>f[k]+sum[i-1]-sum[k]，即f[j]-sum[j]＞f[k]-sum[k]。故只要用单调队列维护f[j]-sum[j]即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#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;
}
ll sm[maxn],q1[maxn],f[maxn]; int n,k,l,r,q2[maxn];
int main(){
n=read(); k=read(); inc(i,1,n)sm[i]=sm[i-1]+read();
l=1; r=2; q1[l]=q2[l]=0; q1[r]=-sm[1]; q2[r]=1;
inc(i,2,n+1){
while(l<=r&&q2[l]<i-k-1)l++; f[i]=q1[l]+sm[i-1];
while(l<=r&&f[i]-sm[i]>=q1[r])r--; q1[++r]=f[i]-sm[i]; q2[r]=i;
}
printf("%lld",f[n+1]); return 0;
}判一个图是否有负环。点数≤500，边数≤3000。（我看不懂原题，后来看了题解，就直接这样说了）
SPFA中如果一个点被更新了n次以上，那么这个图中存在负环。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 510
#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,w,n;}es[maxn*15]; int g[maxn],ess;
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
int f,n,m,w,d[maxn],cnt[maxn]; bool inq[maxn]; queue<int>q;
bool spfa(){
while(!q.empty())q.pop(); inc(i,1,n)d[i]=INF,cnt[i]=inq[i]=0; d[1]=0; inq[1]=1; q.push(1);
while(!q.empty()){
int x=q.front(); q.pop(); inq[x]=0;
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; cnt[es[i].t]++; if(cnt[es[i].t]>n)return 1;
if(!inq[es[i].t])q.push(es[i].t),inq[es[i].t]=1;
}
}
return 0;
}
int main(){
f=read();
while(f--){
n=read(); m=read(); w=read(); memset(g,0,sizeof(g)); ess=0;
inc(i,1,m){int x=read(),y=read(),z=read(); pe(x,y,z); pe(y,x,z);}
inc(i,1,w){int x=read(),y=read(),z=read(); pe(x,y,-z);}
if(spfa())puts("YES");else puts("NO");
}
return 0;
}n点树（有边权），q个询问求两个点之间的最短距离。n，q≤1000。
倍增求lca。
#include <cstdio>
#include <cstring>
#include <algorithm>
#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 f[15][maxn],h[15][maxn],n,q,k,dep[maxn];
struct e{int t,w,n;}es[maxn*2]; int ess,g[maxn];
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;}
void dfs(int x,int fa){
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa){
f[0][es[i].t]=x; h[0][es[i].t]=es[i].w; dep[es[i].t]=dep[x]+1; dfs(es[i].t,x);
}
}
void init(){
for(k=0;(1<<k)<=n;k++); k--;
inc(i,1,k)inc(j,1,n)f[i][j]=f[i-1][f[i-1][j]],h[i][j]=h[i-1][j]+h[i-1][f[i-1][j]];
}
int query(int x,int y){
if(dep[x]<dep[y])swap(x,y); int t=dep[x]-dep[y],q=0;
inc(i,0,k)if(t&(1<<i))q+=h[i][x],x=f[i][x];
for(int i=k;i>=0;i--)if(f[i][x]!=f[i][y])q+=(h[i][x]+h[i][y]),x=f[i][x],y=f[i][y];
if(x==y)return q;else return q+=(h[0][x]+h[0][y]);
}
int main(){
n=read(); q=read(); inc(i,1,n-1){int a=read(),b=read(),c=read(); pe(a,b,c);} dfs(1,0); init();
inc(i,1,q){int a=read(),b=read(); printf("%d\n",query(a,b));} return 0;
}贝茜进行N分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑Di米，并且她的疲劳度会增加 1。贝茜的疲劳度上限为M。如果贝茜选择休息，那么她的疲劳度就会每分钟减少1，但她必须休息到疲劳度恢复到0为止。在疲劳度为0时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为0。 还有，在N分钟的锻炼结束时，贝茜的疲劳度也必须恢复到0。求贝茜最多能跑多少米。n≤10000，m≤500。
dp。f[i][j]表示现在是第i分钟，疲劳度为j。具体看代码。注意当贝茜疲劳度为0时也可以休息，过渡到下一分钟且疲劳度不变。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 510
#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 f[maxn*20][maxn],d[maxn*20],n,m;
int main(){
n=read(); m=read(); inc(i,1,n)d[i]=read(); f[n+1][0]=0; inc(i,1,m)f[n+1][i]=-INF;
for(int i=n;i>=1;i--)
inc(j,0,m){
if(i+j>n+1)f[i][j]=-INF; else if(j==m)f[i][j]=f[i+j][0];
else if(j==0)f[i][j]=max(f[i+1][j+1]+d[i],f[i+1][0]);
else f[i][j]=max(f[i+1][j+1]+d[i],f[i+j][0]);
}
printf("%d",f[1][0]); return 0;
}一个01序列，初始全部元素为0，两种操作：l到r全部元素取反、询问l到r1的个数。序列长度≤100000，询问个数≤100000。
线段树维护区间和，区间修改就让区间和变为区间长度减原区间和。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 400010
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 sm[maxn],n,m,lr[maxn]; bool tg[maxn];
void update(int x){sm[x]=sm[x<<1]+sm[x<<1|1];}
void pushdown(int x){
if(tg[x]){
if(lr[x<<1])sm[x<<1]=lr[x<<1]-sm[x<<1],tg[x<<1]^=1;
if(lr[x<<1|1])sm[x<<1|1]=lr[x<<1|1]-sm[x<<1|1],tg[x<<1|1]^=1;
tg[x]^=1;
}
}
void build(int x,int l,int r){
lr[x]=r-l+1; if(l==r)return; int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r);
}
void modify(int x,int l,int r,int ql,int qr){
pushdown(x); if(ql<=l&&r<=qr){tg[x]^=1; sm[x]=lr[x]-sm[x]; return;} int mid=(l+r)>>1;
if(ql<=mid)modify(x<<1,l,mid,ql,qr); if(mid<qr)modify(x<<1|1,mid+1,r,ql,qr); update(x);
}
int query(int x,int l,int r,int ql,int qr){
pushdown(x); if(ql<=l&&r<=qr)return sm[x]; int mid=(l+r)>>1,q=0;
if(ql<=mid)q+=query(x<<1,l,mid,ql,qr); if(mid<qr)q+=query(x<<1|1,mid+1,r,ql,qr); return q;
}
int main(){
n=read(); m=read(); build(1,1,n);
inc(i,1,m){
int opt=read(),l=read(),r=read(); if(!opt)modify(1,1,n,l,r);else printf("%d\n",query(1,1,n,l,r));
}
return 0;
}三个不同的骰子，分别有S1,S2,S3个面。求出出现几率最大的和是多少。如果有很多种和出现的几率相同，那么就输出小的那一个。2≤S1≤20，2≤S2≤20，2≤S3≤40。
枚举。
#include <cstdio>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int a,b,c,cnt[100],mx1,mx2;
int main(){
scanf("%d%d%d",&a,&b,&c); inc(i,1,a)inc(j,1,b)inc(k,1,c)cnt[i+j+k]++;
mx1=0; inc(i,1,a+b+c)if(cnt[i]>mx1)mx1=cnt[i],mx2=i; printf("%d",mx2); return 0;
}给个树，每个边都有边权0和1。0表示两个端点同色，1表示两个端点不同色。点1为黑色，问点n哪种颜色（颜色只有两种：黑和白）。树大小≤1000。
dfs一发。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#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 g[maxn][maxn],n,ans[maxn];
void dfs(int x,int fa){
inc(i,1,n)if(i!=fa&&g[x][i]!=-1)ans[i]=ans[x]^g[x][i],dfs(i,x);
}
int main(){
n=read(); memset(g,-1,sizeof(g)); inc(i,1,n-1){int x=read(),y=read(),z=read(); g[x][y]=g[y][x]=z;}
dfs(1,0); printf("%d",ans[n]); return 0;
}给个网格，有m个流星，每个流星在ti时刻打在(xi,yi)的格子上，并把该格子和相邻的格子打烂。有个人从(0,0)出发，问最短逃离时间（格子被打烂之后就不能走）。
bfs一发，如果某格子被打烂的时间小于到达时间则不能到达，最后如果到达打烂时间为正无穷的格子即为成功逃出。注意网格的边界应该大于流星的边界，因为如果逃到那些地方也算安全地带。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 500
#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 m,vis[maxn][maxn],ear[maxn][maxn]; queue<pair<int,int> >q;
int bfs(){
q.push(make_pair(1,1)); if(!ear[1][1])return -1;
while(!q.empty()){
int x=q.front().first,y=q.front().second; q.pop();
if(x>1&&!vis[x-1][y]&&ear[x-1][y]>vis[x][y]+1){
vis[x-1][y]=vis[x][y]+1; if(ear[x-1][y]==INF)return vis[x-1][y]; q.push(make_pair(x-1,y));
}
if(!vis[x+1][y]&&ear[x+1][y]>vis[x][y]+1){
vis[x+1][y]=vis[x][y]+1; if(ear[x+1][y]==INF)return vis[x+1][y]; q.push(make_pair(x+1,y));
}
if(y>1&&!vis[x][y-1]&&ear[x][y-1]>vis[x][y]+1){
vis[x][y-1]=vis[x][y]+1; if(ear[x][y-1]==INF)return vis[x][y-1]; q.push(make_pair(x,y-1));
}
if(!vis[x][y+1]&&ear[x][y+1]>vis[x][y]+1){
vis[x][y+1]=vis[x][y]+1; if(ear[x][y+1]==INF)return vis[x][y+1]; q.push(make_pair(x,y+1));
}
}
return -1;
}
int main(){
m=read(); inc(i,0,400)inc(j,0,400)ear[i][j]=INF;
inc(i,1,m){
int x=read()+1,y=read()+1,z=read();
inc(i,-1,1)ear[x+i][y]=min(ear[x+i][y],z),ear[x][y+i]=min(ear[x][y+i],z);
}
printf("%d",bfs()); return 0;
}FJ需要n块木板，第i块木板长度为ai。但他只有一块长度为sigma(i,1,n)ai的木板。每切一次的代价为所切割木板的长度，问最小代价。n≤20000
等价于合并石子（把单块木板的长度看作石子）。故用一个优先队列，每次找最小的两个堆合并起来再放入优先队列，代价计入答案。
#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
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; ll ans;
struct nd{ll a; bool operator < (const nd &b)const{return a>b.a;}}; priority_queue<nd>q;
int main(){
n=read(); inc(i,1,n){int x=read(); q.push((nd){x});}
inc(i,1,n-1){ll x=q.top().a; q.pop(); ll y=q.top().a; q.pop(); q.push((nd){x+y}); ans+=x+y;}
printf("%lld",ans); return 0;
}n头牛在路上走，每当它们走到岔路，如果这些牛可以分为数量相差刚好为k的两群，那么它们就会分成这样的两群往前走，否则就会停下来吃草。问最后有多少群在吃草。n≤10^9，k≤1000。
暴力模拟。（好像实际上不管有多少只牛只要经过3、4个岔路后就会无法再分并停下来吃草）
#include <cstdio>
int n,k,ans;
void dfs(int n,int k){
if(n>k&&(!((n-k)&1)))dfs((n-k)/2,k),dfs((n-k)/2+k,k);else ans++;
}
int main(){
scanf("%d%d",&n,&k); dfs(n,k); printf("%d",ans); return 0;
}给出n个节点的带权图，第i个节点ci。现在你要在这个图中选出一棵树和一个起点，然后你要从起点出发到达所有的节点（不能跳点）再回到起点，经过边的时间为边权，每经过一个点就要花等同于点权的时间（即使这个点已经过）。问如何使时间最短。n≤10000。
每条边的边权为这条边原来的边权加两个端点的点权（因为每个点都要经过两次），然后做最小生成树。
#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 f,t,w;}es[maxn*10]; bool cmp(e a,e b){return a.w<b.w;} int c[maxn],n,m,mn,ans,tot,fa[maxn];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
n=read(); m=read(); inc(i,1,n)c[i]=read(); mn=0x3fffffff; inc(i,1,n)mn=min(mn,c[i]);
inc(i,1,m){int a=read(),b=read(),d=read(); es[i]=(e){a,b,d*2+c[a]+c[b]};}
inc(i,1,n)fa[i]=i; sort(es+1,es+1+m,cmp);
inc(i,1,m){
int x=find(es[i].f),y=find(es[i].t); if(x!=y)fa[x]=y,tot++,ans+=es[i].w; if(tot==n-1)break;
}
printf("%d",ans+mn); return 0;
}n个工作，每个需要的时间都为1，最晚完成时间为ti，价值为vi，问最多能得到的价值。n≤100000。
先把所有工作按最晚开始时间排序，然后把能做的工作先做掉（如果前面的工作时间有空隙可以填上），处理剩下的工作时，比较之前做的工作中价值最小的工作的价值和当前工作的价值，如果之前做的工作价值更小就把它踢掉，换成当前工作。这一过程用优先队列维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#define ll long long
using namespace std;
inline ll read(){
char ch=getchar(); ll 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{ll t,v; bool operator < (const nd &a)const{return v>a.v;}}nds[maxn]; priority_queue<nd>q;
bool cmp(nd a,nd b){return a.t<b.t;} int n; ll ans,tot;
int main(){
n=read(); inc(i,1,n){ll x=read(); ll y=read(); nds[i]=(nd){x-1,y};} sort(nds+1,nds+1+n,cmp);
inc(i,1,n){
if(tot<=nds[i].t)q.push(nds[i]),ans+=nds[i].v,tot++;else{
ll a=q.top().v; if(a<nds[i].v)q.pop(),q.push(nds[i]),ans-=a,ans+=nds[i].v;
}
}
printf("%lld",ans); return 0;
}n个名字，m个能量字符串，每个名字的能量为其中含有能量字符串的种数（含有指有一个不连续子串与能量字符串相等），问每个名字的能量。n≤1000，m≤100。
暴力可过（似乎数据弱）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1010
using namespace std;
char name[maxn][maxn],ener[maxn/10][maxn/10]; int n,m;
int main(){
scanf("%d%d",&n,&m); inc(i,1,n)scanf("%s",name[i]+1); inc(i,1,m)scanf("%s",ener[i]+1);
inc(i,1,n){
int len1=strlen(name[i]+1),ans=0;
inc(j,1,m){
int l=0,len2=strlen(ener[j]+1);
inc(k,1,len1){
if(tolower(name[i][k])==tolower(ener[j][l+1])){
l++; if(l==len2){ans++; break;}
}
}
}
printf("%d\n",ans);
}
return 0;
}n种物品，每种无限个，重量为pi，费用为ci，要求总重量超过h的前提费用最小。求最小费用。n≤100，m≤50000。
dp。f[i][j]=min(f[i-1][j],f[i][j-p[i]]+c[i])，边界f[0][0]=0，f[0][1..m+mx]=INF。最后在f[n][m..m+mx]中找一个最小的。
#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;
}
int f[2][maxn],mx,n,m,p[maxn],c[maxn],x,y;
int main(){
n=read(); m=read(); inc(i,1,n)p[i]=read(),c[i]=read(),mx=max(mx,p[i]);
x=0; y=1; inc(i,0,m+mx)f[x][i]=INF; f[x][0]=0;
inc(i,1,n){
inc(j,0,m+mx)f[y][j]=f[x][j];
inc(j,p[i],m+mx)f[y][j]=min(f[y][j],f[y][j-p[i]]+c[i]);
swap(x,y);
}
y=INF; inc(i,m,m+mx)y=min(y,f[x][i]); printf("%d",y); return 0;
}t个族群，每个族群有ni只蚂蚁，同族群蚂蚁没有区别。问从所有蚂蚁中选出s到b只蚂蚁有多少方案。t≤1000，ni≤100。
dp，f[i][j]表示考虑第i个族群，剩下j只蚂蚁没选择。则f[i][j]=sum(f[i-1][j-k]),k=0..min(j,n[i])。然而O(n^3)会超时，注意到可以计算f[i-1][j]的前缀和sum[j]，然后就能比较方便的得到f[i-1][j-k],k=0..min(j,n[i])=j<=n[i]?sum[j]:sum[j]-sum[j-k]，使复杂度变为O(n^2)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#define mod 1000000
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 f[maxn],cnt[maxn],t,a,s,b,ans,sum[maxn];
int main(){
t=read(); a=read(); s=read(); b=read(); inc(i,1,a){int x=read(); cnt[x]++;} inc(i,0,a)sum[i]=1;
inc(i,1,t){
inc(j,0,a){if(j<=cnt[i])f[j]=sum[j];else f[j]=(mod+sum[j]-sum[j-cnt[i]-1])%mod;}
sum[0]=f[0]; inc(j,1,a)sum[j]=(sum[j-1]+f[j])%mod;
}
ans=0; inc(i,s,b)ans=(ans+f[i])%mod; printf("%d",ans); return 0;
}有N头牛，每头牛有个喝水时间段，这段时间它将专用一个棚。现在给出每头牛的喝水时间段，问至少要多少个棚才能满足它们的要求。n≤50000，时刻≤1000000。
时间段左端点对应的sum元素++，右端点+1对应的sum元素–，最后从左到右加一遍就可以得到每个时刻的喝水牛数，找个最大值就可以了。
#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 sm[maxn],n,mx,ans;
int main(){
n=read(); inc(i,1,n){int x=read(),y=read(); sm[x]++; sm[y+1]--; mx=max(mx,y);}
inc(i,1,mx)sm[i]+=sm[i-1]; inc(i,1,mx)ans=max(ans,sm[i]); printf("%d",ans); return 0;
return 0;
}网格中有一些障碍物，求从起点到终点最小步数。-500≤坐标≤500
bfs。所有坐标均加上500，就可以只考虑第一象限了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#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 dis[maxn][maxn],x,y,n; bool bad[maxn][maxn]; queue<pair<int,int> >q;
int main(){
x=read()+500; y=read()+500; n=read(); inc(i,1,n){int x=read()+500,y=read()+500; bad[x][y]=1;}
q.push(make_pair(500,500)); memset(dis,-1,sizeof(dis)); dis[500][500]=0;
while(!q.empty()){
int xx=q.front().first,yy=q.front().second; q.pop();
if(xx>-1000&&!bad[xx-1][yy]&&dis[xx-1][yy]==-1){
q.push(make_pair(xx-1,yy)); dis[xx-1][yy]=dis[xx][yy]+1;
if(xx-1==x&&yy==y){printf("%d",dis[xx-1][yy]); break;}
}
if(xx<1000&&!bad[xx+1][yy]&&dis[xx+1][yy]==-1){
q.push(make_pair(xx+1,yy)); dis[xx+1][yy]=dis[xx][yy]+1;
if(xx+1==x&&yy==y){printf("%d",dis[xx+1][yy]); break;}
}
if(yy>-1000&&!bad[xx][yy-1]&&dis[xx][yy-1]==-1){
q.push(make_pair(xx,yy-1)); dis[xx][yy-1]=dis[xx][yy]+1;
if(xx==x&&yy-1==y){printf("%d",dis[xx][yy-1]); break;}
}
if(yy<1000&&!bad[xx][yy+1]&&dis[xx][yy+1]==-1){
q.push(make_pair(xx,yy+1)); dis[xx][yy+1]=dis[xx][yy]+1;
if(xx==x&&yy+1==y){printf("%d",dis[xx][yy+1]); break;}
}
}
return 0;
}N个矩形，排成一排。现在希望用尽量少的矩形海报盖住它们。不能盖到矩形之外的地方。n≤250000。
发现如果有一对矩形高度相等，且中间的矩形高度都比它们高，那么就可以省下一个矩形海报。故可以用个单调递增的栈维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#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;
}
stack<int>st; int n,ans;
int main(){
n=read();
inc(i,1,n){
int x=read(),y=read(); while(!st.empty()&&y<=st.top()){if(y==st.top())ans++; st.pop();} st.push(y);
}
printf("%d",n-ans); return 0;
}n个存钱罐，每个罐子的钥匙都在另外某个存钱罐里，问最少打破几个存钱罐，才能得到所有存钱罐里的钱。n≤1000000。
因为每个存钱罐只有一把钥匙，所以整幅图都是由一些互不连接的连着一个环的链组成，而打破存钱罐的个数正是这些连着一个环的链的个数，即图中联通块的个数，故用并查集维护。
#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 fa[maxn],n,ans;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=read(); inc(i,1,n)fa[i]=i; inc(i,1,n){int x=read(),y=find(x),z=find(i); if(y!=z)fa[z]=y;}
inc(i,1,n)if(i==fa[i])ans++; printf("%d",ans); return 0;
}给出一个n个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大。n≤1000000。
两次dfs。第一次dfs维护子树的大小、节点的深度、以子树的根为根的子树深度和。第二次dfs维护以某节点为根除了以1为根时它的子树之外的所有节点的深度和。最后比较所有节点两个深度和相加的值。具体看代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1000010
#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;}
ll ds[maxn],sz[maxn],fads[maxn],dep[maxn]; int n,ans,fa[maxn];
void dfs1(int x){
sz[x]=1; ds[x]=0;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x]){
fa[es[i].t]=x; dep[es[i].t]=dep[x]+1; dfs1(es[i].t);
sz[x]+=sz[es[i].t]; ds[x]+=ds[es[i].t]+sz[es[i].t];
}
}
void dfs2(int x,ll a){
fads[x]=a+n-sz[x]; ll sm=fads[x];
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x])sm+=ds[es[i].t]+sz[es[i].t];
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x])dfs2(es[i].t,sm-(ds[es[i].t]+sz[es[i].t]));
}
int main(){
n=read(); inc(i,1,n-1){int x=read(),y=read(); pe(x,y); pe(y,x);} dfs1(1); dfs2(1,0);
ans=0; inc(i,1,n)if(fads[i]+ds[i]>fads[ans]+ds[ans])ans=i; printf("%d",ans); return 0;
}n只怪物，打死第i只要耗ai血，打死后补bi血。如果你血≤0就会死。你现在有z血，问怎样的顺序可以打死所有怪。n≤100000。
先打bi大于ai的怪攒血，此时按ai升序排序。因为先杀耗血少的再杀耗血多的，则为下一步提供了更高的可能性。因为血量是单增的，所以尽量用较少的血量去杀耗血较少的怪物。再打ai大于bi的怪，此时按bi降序排序，因为先杀补血多的再杀耗血少的，则为下一步提供了更高的可能性。当前这一步的可能性也没有减少，即使补血多的耗血很多，但是由于此时血量已经是单减的了，所以若此时无法杀掉耗血多的，将来也不能。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#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;
}
int n,sz1,sz2; ll z;
struct nd{int a,b,id;}nds1[maxn],nds2[maxn];
bool cmp1(nd a,nd b){return a.a<b.a;} bool cmp2(nd a,nd b){return a.b>b.b;}
int main(){
n=read(); z=read();
inc(i,1,n){int x=read(),y=read(); if(y>=x)nds1[++sz1]=(nd){x,y,i};else nds2[++sz2]=(nd){x,y,i};}
sort(nds1+1,nds1+sz1+1,cmp1); sort(nds2+1,nds2+sz2+1,cmp2);
inc(i,1,sz1){
if(z<=nds1[i].a){printf("NIE"); return 0;} z-=nds1[i].a; z+=nds1[i].b;
}
inc(i,1,sz2){
if(z<=nds2[i].a){printf("NIE"); return 0;} z-=nds2[i].a; z+=nds2[i].b;
}
puts("TAK"); inc(i,1,sz1)printf("%d ",nds1[i].id); inc(i,1,sz2)printf("%d ",nds2[i].id); return 0;
}n个钻井，n个站，要求两两配对，但站必须在钻井的右下方。配一对的费用为两点的曼哈顿距离，求最小总费用。n≤50000。
发现满足条件站必须在钻井的右下方的所有配对方案的总费用是相同的，所以直接用站横坐标的和减钻井横坐标的和加上钻井纵坐标的和减站纵坐标的和即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#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;
}
int n; ll ans;
int main(){
n=read(); inc(i,1,n){int a=read(),b=read(); ans-=a; ans+=b;}
inc(i,1,n){int a=read(),b=read(); ans+=a; ans-=b;} printf("%lld",ans); return 0;
}给个图，每个节点都和1联通，奶牛要从1到每个节点（可以走回头路），希望经过的最长边最短。
求最小生成树即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#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;
}
int n,m,ans,fa[maxn],tot; struct e{int f,t,w;}es[maxn]; bool cmp(e a,e b){return a.w<b.w;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=read(); m=read(); inc(i,1,m){int x=read(),y=read(),z=read(); es[i]=(e){x,y,z};} sort(es+1,es+1+m,cmp);
inc(i,1,n)fa[i]=i;
inc(i,1,m){
int x=find(es[i].f),y=find(es[i].t);
if(x!=y){fa[x]=y; tot++; ans=max(ans,es[i].w); if(tot==n-1)break;}
}
printf("%d",ans); return 0;
}n种硬币面值，求凑m元多少种方案。n≤25，m≤10000。
完全背包。f[0][0]=1，f[i][j]=sum(f[i-1][j],f[i][j-a[k]])。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
using namespace std;
ll f[30][10010]; int v,n;
int main(){
scanf("%d%d",&v,&n); f[0][0]=1;
inc(i,1,v){int x; scanf("%d",&x); inc(j,0,n){f[i][j]=f[i-1][j]; if(j>=x)f[i][j]+=f[i][j-x];}}
printf("%lld",f[v][n]); return 0;
}n点树（有边权），找出一个点，使得其它所有点到它的距离和最小。n≤100000。
类似bzoj1131，但维护深度和改为维护距离和。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#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;
}
struct e{int t; ll w; int n;}es[maxn*2]; int g[maxn],ess;
void pe(int f,int t,ll w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
ll ds[maxn],sz[maxn],fads[maxn],dep[maxn],c[maxn],sum; int n,ans,fa[maxn];
void dfs1(int x){
sz[x]=c[x]; ds[x]=0;
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x]){
fa[es[i].t]=x; dep[es[i].t]=dep[x]+es[i].w; dfs1(es[i].t);
sz[x]+=sz[es[i].t]; ds[x]+=ds[es[i].t]+sz[es[i].t]*es[i].w;
}
}
void dfs2(int x,ll a,ll b){
fads[x]=a+b*(sum-sz[x]); ll sm=fads[x];
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x])sm+=ds[es[i].t]+es[i].w*sz[es[i].t];
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x])dfs2(es[i].t,sm-(ds[es[i].t]+es[i].w*sz[es[i].t]),es[i].w);
}
int main(){
n=read(); inc(i,1,n)c[i]=read(),sum+=c[i];
inc(i,1,n-1){int x=read(),y=read(),z=read(); pe(x,y,z); pe(y,x,z);} dfs1(1); dfs2(1,0,0);
ans=1; inc(i,2,n)if(fads[i]+ds[i]<fads[ans]+ds[ans])ans=i; printf("%lld",fads[ans]+ds[ans]); return 0;
}某条路n段，每段高度hi，现在要将路修成不上升或不下降序列，问最小费用，把高度a修成b费用为|a-b|。n≤2000。
有个结论，每段路修成的高度必定是原序列中已经出现过的高度（因为修好的路是非严格单调）。所以直接离散化，然后dp（修成不下降）：f[i][j]=min(f[i-1][k]+abs(a[j]-a[k])),a[j]>=a[k]。但是这样会T，而a数组因为之前的离散化是单调的，所以可以用前缀最小值数组维护一下f[i-1][1]到f[i-1][n]的最小值，然后就可以递推了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 2010
#define ll long long
#define INF 10000000000000000
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,tot,a[maxn],v[maxn]; ll f[maxn],ans,mn[maxn];
struct nd{int v,id;}nds[maxn]; bool cmp(nd a,nd b){return a.v<b.v;}
int main(){
n=read(); inc(i,1,n)nds[i]=(nd){read(),i}; sort(nds+1,nds+n+1,cmp);
inc(i,1,n){if(i==1||nds[i].v!=nds[i-1].v)v[++tot]=nds[i].v; a[nds[i].id]=tot;}
memset(f,0,sizeof(f)); ans=INF;
inc(i,1,n){
mn[tot]=f[tot]+abs(v[tot]-v[a[i]]);
for(int j=tot-1;j>=1;j--)mn[j]=min(mn[j+1],f[j]+abs(v[j]-v[a[i]])); inc(j,1,tot)f[j]=mn[j];
}
inc(i,1,tot)ans=min(ans,f[i]); memset(f,0,sizeof(f));
inc(i,1,n){
mn[1]=f[1]+abs(v[1]-v[a[i]]);
inc(j,2,tot)mn[j]=min(mn[j-1],f[j]+abs(v[j]-v[a[i]])); inc(j,1,tot)f[j]=mn[j];
}
inc(i,1,tot)ans=min(ans,f[i]); printf("%lld",ans); return 0;
}n点m边有向图，点有点权，边有边权，奶牛想要从某点出发，走一些路使得经过的点权和除以（浮点数除法）边权和最大，求这个小数（保留两位）。n≤1000，m=5000。
01分数规划！太神了，然而我看不懂证明，所以直接给出算法。假设需要所求小数最大，那么二分这个数，然后将所有边的边权改为分母（需要最小化的部分）*二分的数-分子（需要最大化的部分），然后判负环。如果有，说明解合法，否则解不合法。最后把下界输出。如果需要所求小数最小，则把边权改为分子（需要最大化的部分）-分母（需要最小化的部分）*二分的数，同时改变范围缩小的方向。
而判负环用dfs实现的spfa较快，而且每个节点都必须作为起点遍历一遍以防漏判负环。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1010
#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; double w; int n;}es[maxn*5]; int g[maxn],ess;
void pe(int f,int t){es[++ess]=(e){t,0,g[f]}; g[f]=ess;}
double v[maxn],w[maxn*5]; int n,m;
void rebuild(double x){inc(i,1,m)es[i].w=w[i]*x-v[es[i].t];}
bool ins[maxn],f; double d[maxn];
void dfs(int x){
ins[x]=1;
for(int i=g[x];i;i=es[i].n){
if(f)return;
if(d[es[i].t]>d[x]+es[i].w){
if(ins[es[i].t]){f=1; return;} d[es[i].t]=d[x]+es[i].w; dfs(es[i].t);
}
}
ins[x]=0;
}
bool spfa(){
memset(ins,0,sizeof(ins)); memset(d,0,sizeof(d)); f=0;
inc(i,1,n){dfs(i); if(f)return 0;} return 1;
}
int main(){
n=read(); m=read(); inc(i,1,n)v[i]=read(); inc(i,1,m){int x=read(),y=read(); w[i]=read(); pe(x,y);}
double l=1,r=10000;
while(r-l>0.001){
double mid=(l+r)/2; rebuild(mid); if(!spfa())l=mid;else r=mid;
}
printf("%.2lf",l); return 0;
}定义图中一个环的平均值为环上边权和除以（浮点除法）边数，求一个图中的最小环平均值，保留8位。n≤3000，m≤10000，有负权边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 3010
#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; double w; int n;}es[maxn*4]; int g[maxn],ess;
void pe(int f,int t){es[++ess]=(e){t,0,g[f]}; g[f]=ess;}
double w[maxn*4]; int n,m;
void rebuild(double x){inc(i,1,m)es[i].w=w[i]-x;}
bool ins[maxn],f; double d[maxn];
void dfs(int x){
ins[x]=1;
for(int i=g[x];i;i=es[i].n){
if(f)return;
if(d[es[i].t]>d[x]+es[i].w){
if(ins[es[i].t]){f=1; return;} d[es[i].t]=d[x]+es[i].w; dfs(es[i].t);
}
}
ins[x]=0;
}
bool spfa(){
memset(ins,0,sizeof(ins)); memset(d,0,sizeof(d)); f=0;
inc(i,1,n){dfs(i); if(f)return 0;} return 1;
}
int main(){
n=read(); m=read(); inc(i,1,m){int x=read(),y=read(); scanf("%lf",&w[i]); pe(x,y);}
double l=-10000000,r=10000000; int t=60;
while(t--){
double mid=(l+r)/2; rebuild(mid); if(!spfa())r=mid;else l=mid;
}
printf("%.8lf",l); return 0;
}n头牛，第i头牛位置为ai，种族为bi（只能为0，1），求一个区间（按数轴位置），使得区间两端牛距离差最大且两种种族牛数相等。n≤50000。
按位置排序。然后利用前缀和sum[i][0]-sum[j-1][0]=sum[i][1]-sum[j-1][1]，sum[i][0]-sum[i][1]=sum[j-1][0]-sum[j-1][1]，故用个set维护sum[i][0]-sum[i][1]的值，每次找一下set里有没有与当前两个sum元素差相等的值，距离差和答案比较一下。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50010
#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 id,v; bool operator < (const nd &a)const{return v<a.v;};};
nd nds[maxn]; set<nd>st; int n,sm[2][maxn],ans;
int main(){
n=read(); inc(i,1,n){int x=read(),y=read(); nds[i]=(nd){x,y};} sort(nds+1,nds+1+n);
inc(i,1,n)sm[0][i]=sm[0][i-1],sm[1][i]=sm[1][i-1],sm[nds[i].id][i]++;
inc(i,1,n){
set<nd>::iterator sti=st.find((nd){0,sm[0][i]-sm[1][i]});
if(sti!=st.end()){ans=max(ans,nds[i].v-nds[sti->id+1].v);}
else st.insert((nd){i,sm[0][i]-sm[1][i]});
}
printf("%d",ans); return 0;
}m种牧草，每种都有一个价钱和鲜度，n头奶牛，每头都有一个牧草价钱下限和牧草鲜度上限，要求从每头奶牛从m种牧草中选取一种符合要求的牧草，使得总价钱最小，两头奶牛选的种类不能相同。n，m≤100000。
贪心。先将所有牧草按鲜度排序，奶牛按鲜度下限排序，对于每头奶牛，选的应该是鲜度大于等于它要求的牧草中最便宜的那个，这个可以用set维护。
#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;
}
struct nd{int a,b; bool operator <(const nd &c)const{return b<c.b;}}cows[maxn],grass[maxn];
multiset<nd>st; int n,m,j; ll ans;
int main(){
n=read(); m=read(); inc(i,1,n){int x=read(),y=read(); cows[i]=(nd){x,y};}
inc(i,1,m){int x=read(),y=read(); grass[i]=(nd){x,y};} sort(cows+1,cows+1+n); sort(grass+1,grass+1+m);
for(j=m;j>=1&&grass[j].b>=cows[n].b;j--)st.insert((nd){grass[j].b,grass[j].a});
for(int i=n;i>=1;i--){
multiset<nd>::iterator sti=st.lower_bound((nd){cows[i].b,cows[i].a});
if(sti==st.end()){printf("-1"); return 0;} ans+=sti->b; st.erase(sti);
for(j;j>=1&&grass[j].b>=cows[i-1].b;j--)st.insert((nd){grass[j].b,grass[j].a});
}
printf("%lld",ans); return 0;
}n头奶牛，第i头愿意在时刻si到ti打扫牛棚，费用为ci，求打扫S到T时刻的最小费用。n≤10000，时刻≤90000。
最短路，si和ti+1连边，长度为ci，以及所有时刻ai和ai-1连边，长度为0，以保证覆盖的情况被处理。然后求S到T的最短路。好像大部分的神犇用的是线段树。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#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;
}
struct e{int t,w,n;}es[maxn]; int g[maxn],ess,n,be,en; bool inq[maxn]; queue<int>q; ll d[maxn];
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
void spfa(int s){
while(!q.empty())q.pop(); memset(inq,0,sizeof(inq)); inc(i,be,en)d[i]=INF;
q.push(s); inq[s]=1; d[s]=0;
while(!q.empty()){
int x=q.front(); q.pop(); inq[x]=0;
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;
if(!inq[es[i].t])q.push(es[i].t),inq[es[i].t]=1;
}
}
}
int main(){
n=read(); be=read(); en=read()+1; inc(i,1,n){int a=read(),b=read()+1,c=read(); pe(a,b,c);}
inc(i,be,en)pe(i+1,i,0); spfa(be); printf("%lld",d[en]==INF?-1:d[en]); return 0;
}n个节点，每个节点有一个后继节点，问从每个节点出发能到多少个没去过的节点。n≤100000。
因为每个节点只有一个后继节点，所有tarjan缩点后就会变成一堆链，对每条链dfs一下即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#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;
}
struct e{int f,t,n;}es[maxn]; int g[maxn],ess,n;
void pe(int f,int t){es[++ess]=(e){f,t,g[f]}; g[f]=ess;}
bool vis[maxn]; int bel[maxn],sm[maxn],tim,pre[maxn],low[maxn],tot,ins[maxn]; stack<int>st;
void dfs1(int x){
vis[x]=ins[x]=1; st.push(x); low[x]=pre[x]=++tim;
for(int i=g[x];i;i=es[i].n)
if(!vis[es[i].t])dfs1(es[i].t),low[x]=min(low[x],low[es[i].t]);
else if(ins[es[i].t])low[x]=min(low[x],pre[es[i].t]);
if(low[x]==pre[x]){
tot++;
while(!st.empty()){
int now=st.top(); st.pop(); bel[now]=tot; sm[tot]++; ins[now]=0; if(now==x)break;
}
}
}
void dfs2(int x){
for(int i=g[x];i;i=es[i].n){
if(!vis[es[i].t])vis[es[i].t]=1,dfs2(es[i].t),sm[x]+=sm[es[i].t];else sm[x]+=sm[es[i].t];
}
}
int main(){
n=read(); inc(i,1,n){int x=read(); pe(i,x);} inc(i,1,n)if(!vis[i])dfs1(i);
int m=ess; ess=0; memset(g,0,sizeof(g));
inc(i,1,m)if(bel[es[i].f]!=bel[es[i].t])pe(bel[es[i].f],bel[es[i].t]);
memset(vis,0,sizeof(vis)); inc(i,1,tot)if(!vis[i])vis[i]=1,dfs2(i);
inc(i,1,n)printf("%d\n",sm[bel[i]]); return 0;
}n头牛，知道所有牛身高不超过h，给出r条关系(a,b)表示第a+1到b-1头牛都比a，b牛矮，且a牛不必b牛高，问每头牛的最高身高。n≤10000，r≤10000。
那个“a牛不必比b牛高”的条件没什么用，且中间那些牛都比左右牛矮直接让它们比两边牛矮1即可。故用差分序列的方法sum[a+1]–,sum[b]++，然后将sum累加起来加上h即可。还有条件可能有重复的要判重。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
#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 h[maxn],n,k,m,r; struct ask{int a,b;}asks[maxn];
bool cmp(ask a,ask b){return a.a==b.a?a.b<b.b:a.a<b.a;}
int main(){
n=read(); k=read(); m=read(); r=read();
inc(i,1,r){int x=read(),y=read(); asks[i]=(ask){min(x,y)+1,max(x,y)-1};} sort(asks+1,asks+r+1,cmp);
inc(i,1,r){
if(asks[i].a==asks[i-1].a&&asks[i].b==asks[i-1].b)continue; h[asks[i].a]--; h[asks[i].b+1]++;
}
h[0]=m; inc(i,1,n)h[i]+=h[i-1],printf("%d\n",h[i]); return 0;
}n条钢轨，第i条起点pi，长度为wi，价钱ci，有趣度fi，要求从0修到l使得总价钱不超过b的前提下有趣度和最大。n≤10000，l≤1000，b≤1000。
首先把钢轨组织成链表。接着dp：f[i][j]表示修到第i处花钱j，则f[i][j]=f[i-wk][j-ck]+fk,k为终点为i的钢轨。边界则设为f[0][j]都为0，f[i][j]都为负无穷，以保证从0开始修。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1010
#define ll long long
#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 w,f,c,n;}nds[maxn*10]; int g[maxn];
int f[maxn][maxn],l,n,b;
int main(){
l=read(); n=read(); b=read();
inc(i,1,n){
int o=read(),p=read(),q=read(),r=read(); nds[i]=(nd){p,q,r,g[o+p]}; g[o+p]=i;
}
inc(i,1,l)inc(j,0,b)f[i][j]=-INF; inc(i,0,b)f[0][i]=0;
inc(i,0,l){
inc(j,0,b){
for(int k=g[i];k;k=nds[k].n)
if(j>=nds[k].c)f[i][j]=max(f[i][j],f[i-nds[k].w][j-nds[k].c]+nds[k].f);
}
}
printf("%d",f[l][b]<0?-1:f[l][b]); return 0;
}给出n，问4个整数的平方和为n有多少种方案，顺序不同也算。n≤10000。
神犇们都用dp，我不会……故直接三重循环枚举1到sqrt(n)判断第四个数是不是整数，结果排名倒数。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int n,ans;
int main(){
scanf("%d",&n);
inc(i,0,(int)sqrt(n))inc(j,0,(int)sqrt(n))inc(k,0,(int)sqrt(n))
if(i*i+j*j+k*k<=n&&(double)((int)sqrt(n-i*i-j*j-k*k))==sqrt(n-i*i-j*j-k*k))ans++;
printf("%d",ans); return 0;
}n头牛，第i头适应spf值在ai到bi之间的防晒霜。m种防晒霜，每种spf值为ci，有di瓶，问最多多少奶牛能得到合适的防晒霜。n，m≤2500。
贪心，把牛按上限从小到大排序，然后对于每只奶牛，应该选它可以用的spf值最低的防晒霜。这个过程可以用set维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#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;
}
struct nd{int l,r; bool operator < (const nd &a)const{return r==a.r?l<a.l:r<a.r;}}nds[maxn];
multiset<nd>st; int c,l,ans;
int main(){
c=read(); l=read(); inc(i,1,c)nds[i].l=read(),nds[i].r=read(); sort(nds+1,nds+1+c);
inc(i,1,l){int x=read(),y=read(); st.insert((nd){y,x});} st.insert((nd){0,INF});
inc(i,1,c){
multiset<nd>::iterator sti=st.lower_bound((nd){0,nds[i].l}); if(sti->r>nds[i].r)continue;
int x=sti->l,y=sti->r; st.erase(sti); x--; if(x)st.insert((nd){x,y}); ans++;
}
printf("%d",ans); return 0;
}输入N个数,输出升序排列后中间那个数。n≤10000。
本来想交个python的结果莫名奇妙RE了~
#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;
}
int a[maxn],n;
int main(){
n=read(); inc(i,1,n)a[i]=read(); sort(a+1,a+n+1); printf("%d",a[(n+1)/2]); return 0;
}n点m边无向图，知道p条信息ai，表示ai没被损坏但它和点1不联通（损坏的点不能通行），问有多少点和1联通（不包括损坏的点）。n≤30000，m≤100000。
有一个结论，最优删点方案应该是对每个信息ai，将所有ai的相邻点均设为损坏。在这之后DFS求联通性即可。
#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 e{int t,n;}es[maxn*8]; int g[maxn],ess;
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess;}
bool vis[maxn]; int n,m,p,ans;
void dfs(int x){
ans++; for(int i=g[x];i;i=es[i].n)if(!vis[es[i].t])vis[es[i].t]=1,dfs(es[i].t);
}
int main(){
n=read(); m=read(); p=read(); inc(i,1,m){int x=read(),y=read(); pe(x,y); pe(y,x);}
inc(i,1,p){int x=read(); for(int j=g[x];j;j=es[j].n)if(es[j].t!=x)vis[es[j].t]=1;}
vis[1]=1; dfs(1); printf("%d",n-ans); return 0;
}给个长度为n的全为0的序列，m种操作，1 di表示求序列中最早出现的长度为di的值为0的连续子序列，并把这个连续子序列赋为1；2 xi，di表示将[xi,xi+di-1]置为0。n，m≤50000。
用一个线段树，维护三个值：最长为0连续子序列，最长为0后缀，最长为0前缀。然后注意一下合并就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 150010
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 ls[maxn],rs[maxn],ms[maxn],len[maxn],tg[maxn],n,m;
void update(int x){
ms[x]=max(rs[x<<1]+ls[x<<1|1],max(ms[x<<1],ms[x<<1|1]));
ls[x]=(ms[x<<1]==len[x<<1])?len[x<<1]+ls[x<<1|1]:ls[x<<1];
rs[x]=(ms[x<<1|1]==len[x<<1|1])?len[x<<1|1]+rs[x<<1]:rs[x<<1|1];
}
void pushdown(int x){
if(len[x]>1){
if(tg[x]==0){
ms[x<<1]=ls[x<<1]=rs[x<<1]=len[x<<1]; tg[x<<1]=0;
ms[x<<1|1]=ls[x<<1|1]=rs[x<<1|1]=len[x<<1|1]; tg[x<<1|1]=0; tg[x]=-1;
}
if(tg[x]==1){
ms[x<<1]=ls[x<<1]=rs[x<<1]=0; tg[x<<1]=1;
ms[x<<1|1]=ls[x<<1|1]=rs[x<<1|1]=0; tg[x<<1|1]=1; tg[x]=-1;
}
}
}
void build(int x,int l,int r){
len[x]=r-l+1; tg[x]=-1; if(l==r){ls[x]=rs[x]=ms[x]=1; return;}
int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); update(x);
}
int query(int x,int l,int r,int v){
pushdown(x); if(ms[x]<v)return 0; int mid=(l+r)>>1;
if(ms[x<<1]>=v)return query(x<<1,l,mid,v); if(rs[x<<1]+ls[x<<1|1]>=v)return mid-rs[x<<1]+1;
return query(x<<1|1,mid+1,r,v);
}
void fill(int x,int l,int r,int ql,int qr){
pushdown(x);
if(ql<=l&&r<=qr){ms[x]=ls[x]=rs[x]=0; tg[x]=1; return;} int mid=(l+r)>>1;
if(ql<=mid)fill(x<<1,l,mid,ql,qr); if(mid<qr)fill(x<<1|1,mid+1,r,ql,qr);
update(x);
}
void clear(int x,int l,int r,int ql,int qr){
pushdown(x);
if(ql<=l&&r<=qr){ms[x]=ls[x]=rs[x]=len[x]; tg[x]=0; return;} int mid=(l+r)>>1;
if(ql<=mid)clear(x<<1,l,mid,ql,qr); if(mid<qr)clear(x<<1|1,mid+1,r,ql,qr);
update(x);
}
int main(){
n=read(); build(1,1,n); m=read();
inc(i,1,m){
int x=read();
if(x==1){int y=read(),z=query(1,1,n,y); printf("%d\n",z); if(z)fill(1,1,n,z,z+y-1);}
if(x==2){int y=read(),z=read(); clear(1,1,n,y,y+z-1);}
}
return 0;
}商场里有K种工具，价格分别为1，2，…，K美元。约翰手里有N美元，必须花完。求购买组合方案。n≤1000，k≤100。
完全背包，不过要高精度。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1010
#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 bigint{
int len,num[100];
void operator = (int a){len=0; memset(num,0,sizeof(num)); while(a)num[++len]=a%10,a/=10;}
void operator = (bigint a){
memset(num,0,sizeof(num)); inc(i,1,a.len)num[i]=a.num[i]; len=a.len;
}
void operator += (bigint a){
len=max(len,a.len);
inc(i,1,len){num[i]+=a.num[i]; if(num[i]>=10)num[i+1]+=num[i]/10,num[i]%=10;}
if(num[len+1])len++;
}
void print(){for(int i=len;i>=1;i--)printf("%d",num[i]);}
};
int n,k,x,y; bigint f[2][maxn];
int main(){
n=read(); k=read(); x=0; y=1; f[x][0]=1;
inc(i,1,k){
inc(j,0,n)f[y][j]=f[x][j]; inc(j,i,n)f[y][j]+=f[y][j-i]; swap(x,y);
}
f[x][n].print(); return 0;
}找一个分数它最接近给出一个分数。你要找的分数的分子分母的范围在1..32767。
枚举所求分数的分子，用其乘上给出分数得到一个浮点数分母，比较分母向上/下取整所得分数与答案比较。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#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;
}
int n,d,ansa,ansb; double ans;
int main(){
n=read(); d=read(); ans=10;
inc(i,1,32767){
int j=n*i/d,k=j+1;
if(fabs((double)k/(double)i-(double)n/(double)d)<ans)
ans=fabs((double)k/(double)i-(double)n/(double)d),ansa=k,ansb=i;
if(j*d!=n*i&&fabs((double)j/(double)i-(double)n/(double)d)<ans)
ans=fabs((double)j/(double)i-(double)n/(double)d),ansa=j,ansb=i;
}
printf("%d %d",ansa,ansb); return 0;
}n个数，合并ai和ai+1可以得到max(ai,ai+1)，代价为max(ai,ai+1)。问合并n-1次最小代价为多少。n≤1000000。
（来自题解，因为我不知道为什么这样做）维护一个单调递减栈。对于每个加入的元素，若加入后不满足单调性质，则让其与栈顶-1的元素比较：如果加入的数大，则合并栈顶和栈顶-1的数（把栈顶去掉），费用为栈顶-1；否则合并当前与栈顶的数（把栈顶去掉），费用为当前数。重复上述操作，直到满足单调性后入栈。最后从顶向下合并。
#include <cstdio>
#include <cstring>
#include <algorithm>
#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;
}
int st[maxn]; int n,top; long long ans;
int main(){
n=read(); st[0]=INF;
inc(i,1,n){
int x=read();
while(top&&x>=st[top]){
if(x>=st[top-1])ans+=st[top-1],top--;else ans+=x,top--;
}
st[++top]=x;
}
while(top>1)ans+=st[--top]; printf("%lld",ans); return 0;
}n头奶牛，知道n对奶牛之间的产奶量大小，问想知道所有奶牛产奶量大小顺序至少还需知道几对。n≤1000。
每个大小关系看为一条有向边，对每头奶牛进行dfs，求每头奶牛可以到的奶牛数和可以到它的奶牛数之和，用n-1减后就是需要和它比较的奶牛数。最后输出(n*(n-1)-所有牛的结果相加)/2即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#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;
}
struct e{int t,n;}es[maxn*10]; int g[maxn],ess;
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess;}
int f[maxn*10],t[maxn*10],n,m,sum[maxn],ans; bool vis[maxn];
void dfs(int x,int s){
for(int i=g[x];i;i=es[i].n)if(!vis[es[i].t])sum[s]++,vis[es[i].t]=1,dfs(es[i].t,s);
}
int main(){
n=read(); m=read(); inc(i,1,m)f[i]=read(),t[i]=read(),pe(f[i],t[i]);
inc(i,1,n){memset(vis,0,sizeof(vis)); dfs(i,i);} ess=0; memset(g,0,sizeof(g));
inc(i,1,m)pe(t[i],f[i]); inc(i,1,n){memset(vis,0,sizeof(vis)); dfs(i,i);}
ans=n*(n-1); inc(i,1,n)ans-=sum[i]; printf("%d",ans/2); return 0;
}给出一个树，每个节点k个政党中的一个。问每个政党间最远的两个节点距离多少。节点数≤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;
}
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;}
int n,k,dep[maxn],d[maxn],ans[maxn],type[maxn],f[21][maxn],l;
void dfs(int x){
for(int i=g[x];i;i=es[i].n)if(es[i].t!=f[0][x])f[0][es[i].t]=x,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]; inc(i,0,l)if(t&(1<<i))x=f[i][x];
for(int i=l;i>=0;i--)if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];
if(x==y)return x;else return f[0][x];
}
int main(){
n=read(); k=read(); inc(i,1,n){type[i]=read(); int x=read(); if(x)pe(x,i),pe(i,x);} dfs(1);
inc(i,1,n)if(dep[d[type[i]]]<dep[i])d[type[i]]=i;
for(l=0;(1<<l)<=n;l++); l--; inc(i,1,l)inc(j,1,n)f[i][j]=f[i-1][f[i-1][j]];
inc(i,1,n){ans[type[i]]=max(ans[type[i]],dep[i]+dep[d[type[i]]]-2*dep[lca(i,d[type[i]])]);}
inc(i,1,k)printf("%d\n",ans[i]); return 0;
}知道草料到来时F1kg，第D天F2kg。同时知道每头牛到来时间和离开时间，一牛一天吃1kg草料，问草料到来是第几天。
直接用区间左端点对应数组元素++，右端点+1对应数组元素–的方法，最后扫一下即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#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;
}
int sum[maxn],c,f1,f2,d;
int main(){
c=read(); f1=read(); f2=read(); d=read();
inc(i,1,c){int x=read(),y=read(); sum[x]++; sum[y+1]--;}
inc(i,1,d)sum[i]+=sum[i-1];
for(int i=d;i>=1;i--){
f2+=sum[i]; if(f2==f1){printf("%d",i); return 0;}
}
}管子里n个巧克力，第i个价值为ai。每天从左端点或右端点拿一个出来卖，收入为这个巧克力的价值*它是第几天卖出的。问最大价值。n≤2000
dp：f[l][r]=max(f[l+1][r]+a[l]*(n-(r-l+1)+1),f[l][r-1]+a[r]*(n-(r-l+1)+1))。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 2010
#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;
}
ll f[maxn][maxn]; int a[maxn],n;
ll dfs(int l,int r){
if(l>r)return 0; if(f[l][r]!=-1)return f[l][r];
f[l][r]=max(dfs(l+1,r)+a[l]*(n-(r-l)),dfs(l,r-1)+a[r]*(n-(r-l)));
return f[l][r];
}
int main(){
n=read(); inc(i,1,n)a[i]=read(); memset(f,-1,sizeof(f));
printf("%lld",dfs(1,n)); return 0;
}n头牛，第i头坐标为xi，将它们分成c组，要求相邻两组最小距离最大。n≤100000。
二分最小距离。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
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,c,x[maxn],l,r,ans;
bool check(int a){
int j=c-1,k=x[1]; inc(i,2,n){if(x[i]-k>=a)k=x[i],j--; if(!j)return 1;} return 0;
}
int main(){
n=read(); c=read(); inc(i,1,n)x[i]=read(); sort(x+1,x+n+1); l=1; r=1000000000;
while(l<=r){int mid=(l+r)>>1; if(check(mid))ans=mid,l=mid+1;else r=mid-1;} printf("%d",ans); return 0;
return 0;
}无向图，求刚好经过n条边的最小距离。边数≤100，n≤1000000。
边数≤100，说明点数不超过200。故可以用floyd。但要用一点技巧，即倍增floyd：定义最短路矩阵之间的乘法为对它们做floyd，则最后答案矩阵为初始边矩阵的“n次幂”，同时这种乘法满足结合律，故可以用快速幂使得复杂度降低。本弱遇到了莫名其妙的问题，快速幂一写成递归形式就爆栈，样例都过不去，写成二进制拆分形式才能不RE。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 210
#define ll long long
#define INF 10000000000000000
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 tot,n,t,s,e; map<int,int>mp;
struct mat{
ll dis[maxn][maxn];
}f[25],ans;
mat operator * (mat a,mat b){
mat c; inc(i,1,n)inc(j,1,n)c.dis[i][j]=INF;
inc(k,1,n)
inc(i,1,n)
inc(j,1,n)c.dis[i][j]=min(c.dis[i][j],a.dis[i][k]+b.dis[k][j]);
return c;
}
int getnum(int x){
int y=mp[x]; if(!y){mp[x]=++n; return n;}else return y;
}
int main(){
tot=read(); t=read(); s=getnum(read()); e=getnum(read());
inc(i,1,t){
int x=read(),y=getnum(read()),z=getnum(read()); f[0].dis[y][z]=x; f[0].dis[z][y]=x;
}
inc(i,1,n)inc(j,1,n)if(!f[0].dis[i][j])f[0].dis[i][j]=INF;
for(int i=1;(1<<i)<=tot;i++)f[i]=f[i-1]*f[i-1]; bool fl=0;
for(int i=0;(1<<i)<=tot;i++)if(tot&(1<<i)){if(!fl)ans=f[i],fl=1;else ans=ans*f[i];}
printf("%lld",ans.dis[s][e]); return 0;
}N头牛，一共K种特色。每头牛有多种特色。[i,j]段被称为balanced当且仅当K种特色在[i,j]内拥有次数相同。求最大的[i,j]段长度。n≤100000，k≤30。
得到式子：a[i][l]-a[j][l]=a[i][l-1]-a[j][l-1],l在2..k之间，移项得a[i][l]-a[i][l-1]=a[j][l]-a[j][l-1],l在2..k之间，故可以定义一个结构体，里面包含所有的a[i][l]-a[i][l-1],l在2..k之间，然后用set查找满足所有元素相等的最小j即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
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][50],n,k,ans;
struct nd{
int id; int num[50];
bool operator < (const nd &a)const{inc(i,1,k-1)if(num[i]!=a.num[i])return num[i]<a.num[i]; return 0;}
};
multiset<nd>st; nd a;
int main(){
n=read(); k=read();
inc(i,1,n){
int x=read(); inc(j,1,k)sum[i][j]=sum[i-1][j]; for(int j=k-1;j>=0;j--)if(x&(1<<j))sum[i][j+1]++;
}
inc(j,1,k-1)a.num[j]=0; a.id=0; st.insert(a);
inc(i,1,n){
inc(j,1,k-1)a.num[j]=sum[i][j]-sum[i][j+1]; a.id=i;
multiset<nd>::iterator sti=st.find(a); if(sti==st.end())st.insert(a);else{
ans=max(ans,i-sti->id);
}
}
printf("%d",ans); return 0;
}n个数，每次可以将区间l到r里的数+1或-1，问将它们变成同个数的最小操作次数和保证最小操作次数前提下有多少中可能。n≤100000。
先对原数组差分（得到的数组第一个为原数组第一个元素，之后的元素为原数组相邻元素之差），则原操作变为左右端点对应元素加1减1或减1加1，求最小操作次数使得除第一个元素之外剩下元素均为0。则先将正负数对消，剩下的数可以自己消掉或与第一个数对消，故第一问答案为max(正数之和,负数绝对值之和) 第二问答案为abs(正数之和-负数绝对值之和)+1。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#define ll long long
using namespace std;
inline ll read(){
char ch=getchar(); ll 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; ll day,xiy,a,b;
int main(){
n=read(); a=read(); inc(i,2,n){b=read(); if(b-a>0)day+=(b-a);else xiy+=(a-b); a=b;}
printf("%lld\n%lld",max(day,xiy),abs(day-xiy)+1); return 0;
}