Y族居住地水系是一个由岔口和河道组成的网络。每条河道连接着两个岔口，并且水在河道内按照一个固定的方向流动。水系中不会有环流。由于人数众多的原因，Y族的祭祀活动会在多个岔口上同时举行。Y族人认为，如果水流可以从一个祭祀点流到另外一个祭祀点，那么祭祀就会失去它神圣的意义。求保持祭祀神圣性的基础上祭祀的地点数目的最大值。
利用各种性质。首先，题目的模型被称为最长反链，即在有向无环图中求一个点集使其两两不可达。Dilworth定理：最长反链长度=最小链覆盖（用最少的链覆盖所有节点）（%vfk大神的证明然而我看不懂）。求最小链覆盖的方法：建一个二分图，如果点a、b可达，则将左边的a与右边的边相连，求最大独立集。然后又有最大独立集=点数n（指二分图的半边的点数）-二分图最大匹配。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3fffffff
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int n,m,a[200][200],s,t;
struct e{int t,c,n;}; e es[100000]; int ess,g[1000];
inline void pe(int f,int t,int c){
es[++ess]=(e){t,c,g[f]};g[f]=ess;es[++ess]=(e){f,0,g[t]};g[t]=ess;
}
void init(){ess=-1; memset(g,-1,sizeof(g));}
queue <int> q; int h[1000];
bool bfs(int s,int t){
while(! q.empty())q.pop(); memset(h,-1,sizeof(h)); h[s]=0; q.push(s);
while(! q.empty()){
int x=q.front(); q.pop();
for(int i=g[x];i!=-1;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);
}
if(h[t]==-1)return 0;else return 1;
}
int dfs(int x,int t,int f){
if(x==t)return f; int used=0;
for(int i=g[x];i!=-1;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));
es[i].c-=w; es[i^1].c+=w; used+=w; f-=w; if(f==0)return used;
}
if(used==0)h[x]=-1; return used;
}
int dinic(int s,int t){int ans=0; while(bfs(s,t))ans+=dfs(s,t,INF); return ans;};
int main(){
scanf("%d%d",&n,&m); memset(a,0,sizeof(a));
inc(i,1,m){int a1,b1; scanf("%d%d",&a1,&b1); a[a1][b1]=1;}
inc(k,1,n)inc(i,1,n)inc(j,1,n)a[i][j]|=a[i][k]&a[k][j];
s=0; t=n+n+1; init();
inc(i,1,n)pe(s,i,1),pe(i+n,t,1);
inc(i,1,n)inc(j,1,n)if(a[i][j])pe(i,j+n,1);
printf("%d",n-dinic(s,t));
}有一种自动刷题机。每秒，有两种可能的结果：写了x行代码，或删掉了之前写的y行代码。（如果y大于当前代码长度则相当于全部删除。）一旦自动刷题机在某秒结束时积累了大于等于n行的代码，它就会自动AC一题，然后新建一个文件开始写下一题。知道共切了k道题。求n可能的最小值和最大值。操作数和k≤100000
由于n越小切题数越多，故二分n就行了。反思：没看到找不到要输出-1的要求，加上二分边界太小，wa了好几发QAQ~
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
using namespace std;
int n; ll k,opt[maxn],l,r,ansl,ansr;;
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 check(ll x){
ll y=0,z=0; inc(i,1,n){z+=opt[i]; if(z<0)z=0; if(z>=x)y++,z=0;} return y;
}
int main(){
n=read(); k=(ll)read(); inc(i,1,n)opt[i]=(ll)read();
l=1; r=1e15; while(l<=r){ll mid=l+r>>1; if(check(mid)<=k)ansl=mid,r=mid-1;else l=mid+1;}
l=1; r=1e15; while(l<=r){ll mid=l+r>>1; if(check(mid)<k)r=mid-1;else ansr=mid,l=mid+1;}
if(check(ansl)!=k||check(ansr)!=k)printf("-1");else printf("%lld %lld",ansl,ansr);
return 0;
}n座城市。m条道路连接在这些城市之间，一对城市之间可能存在多条道路。对于任何一条道路，设它连接的两个城市分别为u和v，必定满足1 <=|u - v| <= K。此外，任何一个城市都与恰好偶数条道路相连（0也被认为是偶数）。这n个城市之间究竟有多少种可能的连接方法模1000000007后的结果。n，m≤30，m≤8
dp。f[i][j][S][l]表示现在处理第i个点，已经练了第j条边，与i相差≤k的点度数奇偶性状态S，正在处理的要和i连边的l。实现挺复杂的，具体看代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
#define mod 1000000007
using namespace std;
int n,m,kk; ll f[40][40][1<<9][10];
int main(){
scanf("%d%d%d",&n,&m,&kk);
f[2][0][0][0]=1;
inc(i,2,n)inc(j,0,m)inc(k,0,(1<<kk+1)-1){
inc(l,0,kk-1){
f[i][j][k][l+1]=(f[i][j][k][l+1]+f[i][j][k][l])%mod;
if(j<m&&i-kk+l>0)
f[i][j+1][k^(1<<kk)^(1<<l)][l]=(f[i][j+1][k^(1<<kk)^(1<<l)][l]+f[i][j][k][l])%mod;
}
if(!(k&1)&&f[i][j][k][kk])f[i+1][j][k>>1][0]=f[i][j][k][kk];
}
printf("%lld",f[n+1][m][0][0]);
}现有两个煤矿，有三种类型的食品车。每当一个新的食品车到达煤矿时，矿工们就会比较这种新的食品和前两次（或者少于两次，如果前面运送食品的次数不足两次）的食品。如果这几次食品车都是同一类型的食品，则矿工们产出一个单位的煤； 如果这几次食品车中有两种不同类型的食品，则矿工们产出两个单位的煤；如果这几次食品车中有三种不同类型的食品，则矿工们产出三个单位的煤。 预先已知食品车的类型及其被配送的顺序，求通过分配食品车去的煤矿得到的最大产煤量。
dp，f[i][a][b][c][d]表示送第i辆车来时矿洞1的前两次吃a和b，矿洞2的前两次吃c和d，当b或d为0表示该矿洞只送过一辆车，当a、b或c、d为0时表示该矿洞没送过车。i可以滚动掉，同时i需倒序枚举。求矿工采煤量的分类讨论比较复杂，具体看代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define maxn 100010
using namespace std;
int cg(char a){
if(a=='M')return 1;else if(a=='F')return 2;else if(a=='B')return 3;
}
int f[maxn],n,x[4][4][4][4],y[4][4][4][4]; char s[maxn];
int main(){
scanf("%d",&n); scanf("%s",s+1);
inc(i,1,n){if(s[i]=='M')f[i]=1; if(s[i]=='F')f[i]=2; if(s[i]=='B')f[i]=3;} memset(x,0,sizeof(x));
dec(i,n,1){
memset(y,0,sizeof(y));
inc(j1,0,3)inc(j2,0,3)inc(j3,0,3)inc(j4,0,3){
if((j1&&!j2)||(j3&&!j4))continue; int plus1,plus2;
if((!j1&&!j2)||(!j1&&j2==f[i])||(j1==j2&&j2==f[i]))plus1=1;else
if(j1!=j2&&j2!=f[i]&&j1!=f[i]&&j1&&j2)plus1=3;else plus1=2;
if((!j3&&!j4)||(!j3&&j4==f[i])||(j3==j4&&j4==f[i]))plus2=1;else
if(j3!=j4&&j4!=f[i]&&j3!=f[i]&&j3&&j4)plus2=3;else plus2=2;
y[j1][j2][j3][j4]=max(x[j2][f[i]][j3][j4]+plus1,x[j1][j2][j4][f[i]]+plus2);
}
swap(x,y);
}
printf("%d",x[0][0][0][0]); return 0;
}求\((\frac{b+\sqrt{d}}{2})^n\)的整数部分。\(b^2<d<10^{18},n<10^{18},d\equiv 1(mod 4),b^2\equiv 1(mod 4)\)，模数约等于\(7\times 10^{18}\)。
神题。由一些性质可以得出一个数列:\(A_n=bA_{n-1}+\frac{d-b^2}{4}*A_{n-2}\)，且这个数列的通项公式为\(A_n=(\frac{b+\sqrt{d}}{2})^n+(\frac{b-\sqrt{d}}{2})^n\)，且由题目条件得\(\frac{d-b^2}{4}\)为正整数，故可以用矩阵乘法求出\(A_n\)，由于\(\frac{b-\sqrt{d}}{2}\in(-1,0]\)，故答案为\(A_n-1\)当且仅当n为偶数且\(b^2\neq d\)。矩阵递推式：
\[ \begin{bmatrix} A_{n-1} & A_{n-2} \\ 0 & 0 \end{bmatrix}\times\begin{bmatrix} b & 1 \\ \frac{d-b^2}{4} & 0 \end{bmatrix}=\begin{bmatrix} A_n & A_{n-1} \\ 0 & 0 \end{bmatrix} \]
反思：蒟蒻不知道矩乘不满足交换律，调了很久样例。同时由于模数太大，除了需要用unsigned long long外，乘法还要用快速乘（就是用快速幂的方法计算乘法）以防溢出。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll unsigned long long
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define mod 7528443412579576937
using namespace std;
struct M{
ll a[5][5];
M(){inc(i,0,1)inc(j,0,1)a[i][j]=0;}
};
ll b,d,n; M st,ans;
ll cheng(ll a,ll b){
if(b==0)return 0; if(b==1)return a; ll c=cheng(a,b>>1)%mod;
if(b&1)return ((c+c)%mod+a)%mod;else return (c+c)%mod;
}
M mul(M a,M b){
M c; inc(i,0,1)inc(j,0,1)inc(k,0,1)
c.a[i][j]=(c.a[i][j]+cheng(a.a[i][k],b.a[k][j]))%mod;
return c;
}
M pow(M a,ll b){
if(b==1)return a; M c=pow(a,b>>1); if(b&1)return mul(mul(c,c),a);else return mul(c,c);
}
int main(){
scanf("%lld%lld%lld",&b,&d,&n);
if(n==0){printf("1"); return 0;}
st.a[0][0]=b%mod; st.a[0][1]=2;
if(n==1)ans=st;else{
ans.a[0][0]=b%mod; ans.a[0][1]=1; ans.a[1][0]=(d-b*b)/4%mod;
ans=pow(ans,n-1); ans=mul(st,ans);
}
if(b*b!=d&&!(n&1))printf("%lld",(ans.a[0][0]+mod-1)%mod);else printf("%lld",ans.a[0][0]);
return 0;
}有n个城池组成根节点为1的树，m个人，当一个人的战斗力大于等于攻打城市的防御力，就能攻占这个城市，来到这个城市的父节点，否则该人会牺牲在这个城市。当一个城市被攻占时，会使攻占的人的战斗力加或乘上某个数。现在给出m个人的最开始攻打的城市和初始战斗力，求在每个城市的牺牲人数和每个人一共攻打几个城市。注意这m个人处在不同的时空，即攻击互不影响，且每个人会一直往上攻打除非牺牲或到达根节点。
由于对一些数乘一个正数或加一个数这些数的相对大小不变，故可以用可并堆。每个人作为堆的一个节点，然后dfs，对每个节点将所有其子节点存储的堆合并，把牺牲的节点弹出，并对剩余的节点打标记。注意打或下传乘标记时还要将这个节点的加标记也一起乘上乘标记，因为(v[x]+tagpl[x])*tagmu[x]=v[x]*tagmu[x]+tagpl[x]*tagmu[x]。关于用什么堆，网上有人用斜堆结果T了，所以用复杂度稍微好一点的左偏树，只比斜堆多一个存节点最大深度的数组和多一句判断，也不难写。（斜堆也试了一下，也就慢了1s半，不知道是我斜堆(7s)写得好还是左偏树(5.5s)写得烂）。反思：脑子进水了，乘tagmu[x]写出乘x，wa了四次QAQ~
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
#define maxn 300010
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;
struct e{int t,n;}; e es[maxn]; int g[maxn],ess;
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess;}
ll h[maxn],opt[maxn],p[maxn],ans[maxn],rt[maxn],die[maxn],d[maxn],st[maxn];
ll ch[maxn][2],v[maxn],tagmu[maxn],tagpl[maxn],dep[maxn];
void pushdown(int x){
int lc=ch[x][0],rc=ch[x][1];
if(tagmu[x]!=1||tagpl[x]!=0){
if(lc)v[lc]=v[lc]*tagmu[x]+tagpl[x],
tagmu[lc]*=tagmu[x],tagpl[lc]=tagpl[lc]*tagmu[x]+tagpl[x];
if(rc)v[rc]=v[rc]*tagmu[x]+tagpl[x],
tagmu[rc]*=tagmu[x],tagpl[rc]=tagpl[rc]*tagmu[x]+tagpl[x];
tagpl[x]=0; tagmu[x]=1;
}
}
int merge(int x,int y){
if(!x||!y)return x+y; if(v[y]<v[x])swap(x,y); pushdown(x);
ch[x][1]=merge(ch[x][1],y); if(dep[ch[x][0]]<dep[ch[x][1]])swap(ch[x][0],ch[x][1]);
dep[x]=dep[ch[x][0]]+1; return x;
}
int pop(int x){
pushdown(x); int y=merge(ch[x][0],ch[x][1]); ch[x][0]=ch[x][1]=0; return y;
}
int dfs(int x){
int y=rt[x];
for(int i=g[x];i;i=es[i].n)d[es[i].t]=d[x]+1,dfs(es[i].t),y=merge(y,rt[es[i].t]);
while(y&&v[y]<h[x])die[y]=x,y=pop(y),ans[x]++;
if(x!=1){
if(opt[x])v[y]*=p[x],tagmu[y]*=p[x],tagpl[y]*=p[x];else v[y]+=p[x],tagpl[y]+=p[x];
}
rt[x]=y; return y;
}
int main(){
n=read(); m=read(); inc(i,1,n)h[i]=read();
inc(i,2,n){int a=read(); pe(a,i); opt[i]=read(); p[i]=read();}
inc(i,1,m){
v[i]=read(); tagmu[i]=1; dep[i]=1; st[i]=read(); rt[st[i]]=merge(rt[st[i]],i);
}
d[1]=1; int x=dfs(1); inc(i,1,n)printf("%lld\n",ans[i]);
inc(i,1,m)printf("%lld\n",d[st[i]]-d[die[i]]);
return 0;
}维护序列，支持区间加、区间乘、区间求和模一个数。序列大小和操作数≤100000
线段树，加标记和乘标记的处理同bzoj4003。模的时候注意细节。
#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;
int n,m; ll sm[maxn*3],tgpl[maxn*3],tgmu[maxn*3],v[maxn],p; bool iss[maxn*3];
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;
}
void pushdown(int x,int l,int r){
if(tgmu[x]!=1||tgpl[x]!=0){
if(!iss[x]){
int lc=x<<1,rc=x<<1|1; int mid=l+r>>1;
sm[lc]=(sm[lc]*tgmu[x]%p+tgpl[x]*(mid-l+1)%p)%p;
sm[rc]=(sm[rc]*tgmu[x]%p+tgpl[x]*(r-mid)%p)%p;
tgmu[lc]=tgmu[lc]*tgmu[x]%p; tgmu[rc]=tgmu[rc]*tgmu[x]%p;
tgpl[lc]=(tgpl[lc]*tgmu[x]%p+tgpl[x])%p; tgpl[rc]=(tgpl[rc]*tgmu[x]%p+tgpl[x])%p;
}
tgpl[x]=0; tgmu[x]=1;
}
}
int update(int x){
if(!iss[x])sm[x]=(sm[x<<1]+sm[x<<1|1])%p;
}
void build(int x,int l,int r){
tgmu[x]=1; if(l==r){sm[x]=v[l]; iss[x]=1; return;} int mid=l+r>>1; iss[x]=0;
build(x<<1,l,mid); build(x<<1|1,mid+1,r); update(x);
}
void modmu(int x,int l,int r,int ql,int qr,ll val){
pushdown(x,l,r);
if(ql<=l&&r<=qr){
sm[x]=sm[x]*val%p; tgmu[x]=tgmu[x]*val%p; tgpl[x]=tgpl[x]*val%p; return;
}
int mid=l+r>>1;
if(ql<=mid)modmu(x<<1,l,mid,ql,qr,val); if(mid<qr)modmu(x<<1|1,mid+1,r,ql,qr,val);
update(x);
}
void modpl(int x,int l,int r,int ql,int qr,ll val){
pushdown(x,l,r);
if(ql<=l&&r<=qr){
sm[x]=(sm[x]+val*(r-l+1)%p)%p; tgpl[x]=(tgpl[x]+val)%p; return;
}
int mid=l+r>>1;
if(ql<=mid)modpl(x<<1,l,mid,ql,qr,val); if(mid<qr)modpl(x<<1|1,mid+1,r,ql,qr,val);
update(x);
}
ll query(int x,int l,int r,int ql,int qr){
pushdown(x,l,r);
if(ql<=l&&r<=qr)return sm[x]; int mid=l+r>>1; ll q=0;
if(ql<=mid)q=(q+query(x<<1,l,mid,ql,qr))%p;
if(mid<qr)q=(q+query(x<<1|1,mid+1,r,ql,qr))%p; return q;
}
int main(){
n=read(); p=read(); inc(i,1,n)v[i]=read()%p; build(1,1,n); m=read();
inc(i,1,m){
int opt=read();
if(opt==1){
int x=read(),y=read(); ll z=read()%p; modmu(1,1,n,x,y,z);
}
if(opt==2){
int x=read(),y=read(); ll z=read()%p; modpl(1,1,n,x,y,z);
}
if(opt==3){
int x=read(),y=read(); printf("%lld\n",query(1,1,n,x,y)%p);
}
}
return 0;
}在树上找一条路径，使得端点到这条路径的距离最大值最小。
一个坑，就是这个路径可以不包含任意一条边，只包含一个节点。因此可以证明这条路径在树的直径上，把树的直径上的所有边存入一个序列，对直径上每个点求其它不在路径上的点与它的最大距离mxd，然后用双指针维护序列的一段使得和≤s，比较答案和序列两端到直径首末端的距离及序列中的点的最大mxd的较大值。序列中的点的最大mxd值用单调队列即可维护，怎么求树的直径呢？先对任意节点dfs/bfs求出最大距离的点，再对这个点作dfs/bfs求出与其距离最大的点，第二次遍历到第二个点所经过的路径就是树的直径。
#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 n,s,d[maxn],f[maxn],p[maxn],ed[maxn],mxd[maxn],tot,fr,ta,q1[maxn],q2[maxn],l,r,now,ans,sm[maxn];
bool vis[maxn];
struct e{int t,w,n;}; e es[maxn*3]; 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;
}
void dfs1(int x,int fa){
for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa)d[es[i].t]=d[x]+es[i].w,dfs1(es[i].t,x);
}
void dfs2(int x){
for(int i=g[x];i;i=es[i].n)if(i!=f[x])d[es[i].t]=d[x]+es[i].w,f[es[i].t]=i^1,dfs2(es[i].t);
}
void dfs3(int x){
for(int i=g[x];i;i=es[i].n)if(!vis[es[i].t])
d[es[i].t]=d[x]+es[i].w,mxd[0]=max(mxd[0],d[es[i].t]),vis[es[i].t]=1,dfs3(es[i].t);
}
int main(){
n=read(); s=read(); ess=1; inc(i,1,n-1){int a=read(),b=read(),c=read(); pe(a,b,c);}
d[1]=0; dfs1(1,0); int mx1=1; inc(i,1,n)if(d[i]>d[mx1])mx1=i; d[mx1]=0; f[mx1]=0; dfs2(mx1);
int mx2=mx1; inc(i,1,n)if(d[i]>d[mx2])mx2=i;
for(int i=mx2;i;i=es[f[i]].t)tot++,p[tot]=i,ed[tot]=es[f[i]].w,vis[i]=1;
inc(i,1,tot)d[p[i]]=0,mxd[0]=0,dfs3(p[i]),mxd[i]=mxd[0],sm[i]=sm[i-1]+ed[i];
l=1; r=1; now=ed[1]; fr=ta=1; q1[1]=mxd[1]; q2[1]=1; ans=0x3fffffff;
while(l<=r&&l<=tot-1){
while(r<=tot-1&&now<=s){
ans=min(ans,max(max(q1[fr],sm[l-1]),sm[tot-1]-sm[r-1])); r++;
while(fr<=ta&&mxd[r]>q1[ta])ta--; q1[++ta]=mxd[r]; q2[ta]=r; now+=ed[r];
}
if(q2[fr]==l)fr++; now-=ed[l]; l++;
if(l<=tot-1&&now<=s)ans=min(ans,max(max(q1[fr],sm[l-1]),sm[tot-1]-sm[r]));
}
inc(i,1,tot)ans=min(ans,max(max(mxd[i],sm[i-1]),sm[tot-1]-sm[i-1]));
printf("%d",ans); return 0;
}n种食物，每种有价钱和保质期。每次叫外卖要F元，可以购买任意多份食物。共有m元，问一共能过多少天使得每天都能吃到一份不过期的食物。n≤200，其他都≤10^18。
先排序+单调队列去掉那些价钱贵保质期反而短的外卖，剩下的队列按保质期从短到长排（也就是价钱从便宜到贵排）。然后有结论：生存天数为以叫外卖次数为自变量的单峰函数。因此三分叫外卖次数（注意上界为m/最便宜外卖的价钱），如何根据叫外卖次数求生存天数呢？又有结论：每次叫外卖间隔时间越平均越优。设叫外卖次数为k，从便宜到贵买，依次扩充叫外卖间隔时间，当最后钱不够买齐k组当前食物时，则能买多少组买多少。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
#define maxn 300
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 p,s;}; nd a1[maxn],a2[maxn];
ll p[maxn],s[maxn],m,f,l,r,ans; int n;
bool cmp(nd a,nd b){return a.s==b.s?a.p>b.p:a.s<b.s;}
ll calc(ll k){
ll cost=m-k*f,day=0,ans=0;
inc(i,1,n){
if(a2[i].s>=day){
ll a=min(cost/a2[i].p/k,a2[i].s-day+1); day+=a; ans+=a*k; cost-=a*k*a2[i].p;
}
if(a2[i].s>=day){
ll a=min(k,cost/a2[i].p); day++; ans+=a; cost-=a*a2[i].p;
}
}
return ans;
}
int main(){
m=read(); f=read(); n=(int)read(); inc(i,1,n)a1[i].p=read(),a1[i].s=read(); sort(a1+1,a1+1+n,cmp);
r=1; a2[r]=a1[1];
inc(i,2,n){while(r&&a2[r].p>a1[i].p)r--; a2[++r]=a1[i];} n=r;
l=1; r=(m/(f+a2[1].p)); ans=0;
while(l<=r){
ll mid1=l+(r-l)/3,mid2=r-(r-l)/3,c1=calc(mid1),c2=calc(mid2);
if(c1<c2)ans=max(ans,c2),l=mid1+1;
else if(c1>c2)ans=max(ans,c1),r=mid2-1;
else ans=max(ans,c1),l=mid1+1,r=mid2-1;
}
printf("%lld",ans); return 0;
}求两个字符串的最长公共子序列长度和个数。字符串长度均≤5000。
dp，设f[i][j]表示x串i位到末位，y串j位到末位的最长长度，g[i][j]表示x串i位到末位，y串j位到末位的最长长度的个数，方程：
x[i]==y[j]:f[i][j]=f[i+1][j+1]+1 g[i][j]=g[i+1][j+1]+(f[i][j]==f[i+1][j])g[i+1][j]+(f[i][j]==f[i][j+1])g[i][j+1]; x[i]!=y[j]:f[i][j]=max(f[i+1][j],f[i][j+1]); g[i][j]=(f[i][j]==f[i+1][j])g[i+1][j]+(f[i][j]==f[i][j+1])g[i][j+1]-(f[i][j]==f[i+1][j]&&f[i][j]==f[i][j+1]&&f[i][j]==f[i+1][j+1])*g[i+1][j+1];
边界就是g[xn+1][1..yn+1]=1和g[xn][yn+1]=1，滚动一下就行。
反思：蒟蒻wa了好多发，包括红色部分漏了，模的时候没有考虑负数和边界条件写错，但根本原因还是对dp的循环写法的不熟练（以前总是写记忆化搜索，导致现在一要滚动数组就GG），尤其是边界如何处理方面。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define maxn 6000
#define ll long long
#define mod 100000000
using namespace std;
char sx[maxn],sy[maxn]; int nx,ny;
ll fx[maxn],fy[maxn],gx[maxn],gy[maxn];
int main(){
scanf("%s",sx+1); scanf("%s",sy+1); nx=strlen(sx+1)-1; ny=strlen(sy+1)-1;
inc(i,1,ny+1)gx[i]=1; gy[ny+1]=1;
dec(i,nx,1){
dec(j,ny,1){
if(sx[i]==sy[j]){
fy[j]=fx[j+1]+1; gy[j]=gx[j+1]+(fy[j]==fx[j])*gx[j]+(fy[j]==fy[j+1])*gy[j+1];
gy[j]%=mod;
}else{
fy[j]=max(fx[j],fy[j+1]);
gy[j]=(fy[j]==fx[j])*gx[j]+(fy[j]==fy[j+1])*gy[j+1]-(fy[j]==fx[j]&&fy[j]==fy[j+1]&&fy[j]==fx[j+1])*gx[j+1];
gy[j]+=mod; gy[j]%=mod;
}
}
swap(fx,fy); swap(gx,gy);
}
printf("%lld\n%lld",fx[1],gx[1]); return 0;
}有一个序列和一个区间集合，每次将序列中的一个数-1，求此时集合里有多少个区间和为0。序列大小≤100000，区间数≤100000，操作数≤100000。
此题解法其实并不难，对序列建线段树，用线段树每个节点维护区间和及覆盖该区间的集合内的区间的链表，同时记录每个集合内区间被分割为多少个区间。操作时就把查询经过的节点的区间和-1，如果为0则将覆盖该节点的区间的分割数-1，当分割数为0就让答案++。问题是复杂度，总是要遍历链表不会很慢吗？后来仔细想了一下，每次向线段树挂区间时最多挂log2n个节点，共影响到mlog2n个节点，因此遍历链表的总节点数为mlog2n，且当一个节点区间和变为0遍历链表后就永远不会再遍历，因此总复杂度大致是O(mlog2n)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100100
using namespace std;
struct nd{int v,n;}; nd nds[maxn*50]; int v[maxn*4],tot[maxn],g[maxn*4],n,m,a[maxn],q,ans,ndss;
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;
}
void ins(int num,int node){
nds[++ndss]=(nd){num,g[node]}; g[node]=ndss;
}
void update(int x){
for(int i=g[x];i;i=nds[i].n){tot[nds[i].v]--; if(!tot[nds[i].v])ans++;}
}
void build(int x,int l,int r){
if(l==r){v[x]=a[l]; return;}; int mid=l+r>>1;
build(x<<1,l,mid); build(x<<1|1,mid+1,r); v[x]=v[x<<1]+v[x<<1|1];
}
void insert(int x,int l,int r,int ql,int qr,int num){
if(ql<=l&&r<=qr){ins(num,x); tot[num]++; return;} int mid=l+r>>1;
if(ql<=mid)insert(x<<1,l,mid,ql,qr,num); if(mid<qr)insert(x<<1|1,mid+1,r,ql,qr,num);
}
void change(int x,int l,int r,int q){
v[x]--; if(!v[x])update(x); if(l==r)return; int mid=l+r>>1;
if(q<=mid)change(x<<1,l,mid,q);else change(x<<1|1,mid+1,r,q);
}
int main(){
//freopen("in.txt","r",stdin);
n=read(); m=read(); inc(i,1,n)a[i]=read(); build(1,1,n);
inc(i,1,m){int l=read(),r=read(); insert(1,1,n,l,r,i);} q=read();
inc(i,1,q){int x=(read()+ans-1)%n+1; change(1,1,n,x); printf("%d\n",ans);}
return 0;
}求\((\sum_{i=0}^k{C(n,i)})\%2333\)。n，k≤10^18
根据Lucas定理（我不会），C(n,k)%2333=C(n/2333,k/2333)*C(n%2333,k%2333)，故可以进行一些化简（把模省去了）
\[ \begin{split} \sum_{i=0}^k{C(n,i)}&=\sum_{i=0}^k{C(n/2333,i/2333)*C(n\%2333,i\%2333)} \\ &=\sum_{i=0}^{k/2333-1}{(C(n/2333,i)\sum_{j=0}^{2332}{C(n\%2333,j))}} \\ &+C(n/2333,k/2333)*\sum_{i=0}^{k\%2333}{C(n\%2333,i)} \end{split} \]
一开始先递推出i,j≤2333的C[i][j]和sm[i][j]（表示\(\sum_{k=0}^j{C[i][k]}\)），然后上式橙色部分可以看做红色部分的简化部分，递归求解直到n，k的范围≤2333就return sm[n][k]，同时上式中蓝色部分也可以用Lucas定理递归求解到n，k范围≤2333时return C[n][k]。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
#define maxn 2334
#define mod 2333
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;
}
ll n,k,c[maxn][maxn],sm[maxn][maxn]; int t;
void calc(){
c[0][0]=sm[0][0]=1; inc(i,1,mod)sm[0][i]=1;
inc(i,1,mod){
c[i][0]=sm[i][0]=1;
inc(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
inc(j,1,mod)sm[i][j]=(sm[i][j-1]+c[i][j])%mod;
}
}
ll solvec(ll n,ll k){
if(n<=mod&&k<=mod)return c[n][k];else return solvec(n/mod,k/mod)*c[n%mod][k%mod]%mod;
}
ll solvesm(ll n,ll k){
if(k<mod)return solvec(n/mod,k/mod)*sm[n%mod][k%mod]%mod;
return (solvesm(n/mod,k/mod-1)*sm[n%mod][mod-1]%mod+solvec(n/mod,k/mod)*sm[n%mod][k%mod]%mod)%mod;
}
int main(){
t=read(); calc();
inc(i,1,t){n=read(); k=read(); printf("%lld\n",solvesm(n,k)%mod);}
return 0;
}n*n的顶点图，一开始相邻顶点均有边相连，现在删掉k条边，希望知道每次删边后边的两个端点是否联通。n≤1500，k≤2*n*(n-1)，边最多被删一次。
隐隐觉得是并查集，但不知道删边怎么表示。在膜拜了题解后明白原来可以转成对偶图（以格子和外框为节点），原图的删边就是新图的加边。每次新图加边时就判断是否会产生环，若会，说明原图的两个端点在删边后不连通。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 2000
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
int pos[maxn][maxn],fa[2*maxn*maxn],tot,n,k,x[2],y[2]; bool ans; char s[2][5];
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 find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=read(); k=read(); tot=0; inc(i,1,n-1)inc(j,1,n-1)pos[i][j]=++tot; inc(i,1,tot)fa[i]=i;
inc(i,1,k){
x[0]=read(),y[0]=read(); scanf("%s",s[0]); x[1]=read(),y[1]=read(); scanf("%s",s[1]);
if(s[ans][0]=='N'){
int a=find(pos[x[ans]-1][y[ans]]),b=find(pos[x[ans]][y[ans]]);
if(a==b)ans=1;else fa[a]=b,ans=0;
}
else{
int a=find(pos[x[ans]][y[ans]-1]),b=find(pos[x[ans]][y[ans]]);
if(a==b)ans=1;else fa[a]=b,ans=0;
}
if(!ans)puts("TAK");else puts("NIE");
}
return 0;
}容器体积为c，n个物体，每个有一个体积，求不超过容器能放入的最大体积。n≤5000，c≤50000
裸01背包。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define maxn 50100
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,f[maxn];
int main(){
c=read(); n=read();
inc(i,1,n){
int a=read(); dec(j,c,a)f[j]=max(f[j],f[j-a]+a);
}
printf("%d",f[c]); return 0;
}N只牛，每只牛都与其他N-1只牛聊着天。一个对话的进行，需要两只牛都按照和她们间距离等大的音量吼叫，计算音量和。N≤10000
第i只牛与前i-1只牛对话的音量和是x=sum[1..i-1]+sum[2..i-1]+sum[3..i-1]+…+sum[i-1..i-1]，x+(sum[1..0]+sum[1..1]+sum[1..2]+sum[1..3]+…+sum[1..i-2])=sum[1..i-1](i-1)，令sm[i]=sum[1..i]，则x=sm[i-1](i-1)-sigma(j,1,i-2)sm[j]，而这个sigma(j,1,i-2)sm[j]也可以在开始时求出。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10100
#define inc(i,j,k) for(int i=j;i<=k;i++)
#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 a[maxn],sms[maxn],smb[maxn],ans;
int main(){
n=read(); inc(i,1,n)a[i]=read(); sort(a+1,a+n+1); ans=0;
inc(i,1,n-1)a[i]=a[i+1]-a[i],sms[i]=sms[i-1]+a[i],smb[i]=smb[i-1]+sms[i];
inc(i,2,n)ans+=sms[i-1]*(i-1)-smb[i-2];
printf("%lld",ans*2); return 0;
}一个数为偶数就让它/2，为奇数就让它*3+1，问多少步可以让它变成1。n≤1000000
模拟。
#include <cstdio>
int main(){
int n; scanf("%d",&n); int ans=0;
while(n!=1){if(n&1)n=n*3+1;else n>>=1; ans++;}
printf("%d",ans); return 0;
}n个点，问最多能画多少条线使两两不平行。n≤200。
枚举所有线，排序后去重。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50000
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;
}
double xl[maxn]; bool hx; int n,x[300],y[300],tot,ans;
int main(){
n=read(); inc(i,1,n)x[i]=read(),y[i]=read();
inc(i,1,n)inc(j,i+1,n){
if(x[i]==x[j])hx=1;else xl[++tot]=(double)(y[i]-y[j])/(x[i]-x[j]);
}
sort(xl+1,xl+tot+1); ans=unique(xl+1,xl+tot+1)-xl-1;
printf("%d",ans+hx); return 0;
}坐标系上n个点，其中一些点连了边，问使点连通还要连边的最小总长度。n≤1000。
用并查集维护连通块，先将连好边的点合并，然后再按长度从小到大连边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 1100
#define inc(i,j,k) for(int i=j;i<=k;i++)
#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,fa[maxn],cnt; ll x[maxn],y[maxn];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct e{int f,t; ll len;}; e es[maxn*maxn]; int ess;
bool cmp(e a,e b){return a.len<b.len;}
inline bool merge(int _x,int _y){int x=find(_x),y=find(_y); if(x==y)return 0; fa[x]=y; return 1;}
int main(){
n=read(); m=read(); inc(i,1,n)x[i]=read(),y[i]=read(),fa[i]=i;
inc(i,1,n)inc(j,i+1,n)es[++ess]=(e){i,j,(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])};
sort(es+1,es+ess+1,cmp);
inc(i,1,m){int a=read(),b=read(); if(merge(a,b))cnt++;} double ans=0;
inc(i,1,ess){if(merge(es[i].f,es[i].t))ans+=sqrt(es[i].len),cnt++; if(cnt==n-1)break;}
printf("%.2lf",ans); return 0;
}数轴上n个互不覆盖的区间，问要用多少个长为L的线段覆盖。n≤10000
排序区间，然后从每个区间左端点开始铺木板，如果最后一块木板能够铺到下一个区间就铺，以此类推。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 10100
#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;
}
struct rg{int l,r;}; rg rgs[maxn]; int n,l,ans;
bool cmp(rg a,rg b){return a.l<b.l;}
int main(){
n=read(); l=read();
inc(i,1,n)rgs[i].l=read(),
rgs[i].r=read()-1;
sort(rgs+1,rgs+1+n,cmp); int i=1;
while(i<=n){
ans+=(rgs[i].r-rgs[i].l+l)/l; int rem=(rgs[i].r-rgs[i].l+1)%l; if(rem)rem=l-rem;
while(i<n&&rem>=rgs[i+1].r-rgs[i].r)rem-=(rgs[i+1].r-rgs[i].r),i++;
if(i==n)break; if(rem>=rgs[i+1].l-rgs[i].r)rgs[i+1].l+=rem-(rgs[i+1].l-rgs[i].r)+1;
i++;
}
printf("%d",ans); return 0;
}n个任务，每个有一个所需时间和最晚完成时刻，问最晚要从什么时候开始工作。n≤1000
贪心，按最晚完成时刻从早到晚排序，如果当前任务来不及完成，就将前面的任务往前推，否则累积一个“自由时间”。当推任务时，如果之前有“自由时间”，就用自由时间减往前推的时间，否则用最晚开始时间去减往前推的时间。反思：我开始贪错了，按最晚开始时刻从早到晚排序，结果WA很久。现在还是想不太清楚原因，希望哪位神犇能帮我指出。
以下数据会出错：
2
10 20
1 12
如果按正确的应该输出9，但按我的错解输出的是1。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1100
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; struct job{int t,s;}; job jobs[maxn];
bool cmp(job a,job b){return a.s==b.s?a.t<b.t:a.s<b.s;};
int main(){
n=read(); inc(i,1,n)jobs[i].t=read(),jobs[i].s=read(); sort(jobs+1,jobs+1+n,cmp);
int ans=jobs[1].s-jobs[1].t,rem=0;
inc(i,2,n){
if(jobs[i].s-jobs[i].t<jobs[i-1].s)rem-=jobs[i-1].s-(jobs[i].s-jobs[i].t);
else rem+=jobs[i].s-jobs[i].t-jobs[i-1].s;
if(rem<0)ans+=rem,rem=0; if(ans<0){printf("-1"); return 0;}
}
printf("%d",ans); return 0;
}一个序列只由1﹑2﹑3三种数组成。求最少要改变多少个数使它变成不下降序列或不上升序列。序列大小≤30000
DP。设f[i][j]表示正在考虑第i个数，上一个数是j。求不下降序列最少改变个数方程：
f[i][j]=min(f[i+1][k]+1,k∈[j,3]),a[i]<j
f[i][j]=min(f[i+1][a[i]],f[i+1][k]+1,k∈[j,3]且k!=a[i])a[i]>=j
求不上升同理。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 50000
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define INF 0x3fffffff
using namespace std;
int n,a[maxn],x[5],y[5],ans;
int main(){
scanf("%d",&n); inc(i,1,n)scanf("%d",&a[i]); memset(x,0,sizeof(x));
dec(i,n,1){
memset(y,0,sizeof(y));
inc(j,1,3)if(a[i]<j){
y[j]=INF; inc(k,j,3)y[j]=min(y[j],x[k]+1);
}else{
y[j]=x[a[i]]; inc(k,j,3)if(k!=a[i])y[j]=min(y[j],x[k]+1);
}
swap(x,y);
}
ans=INF; inc(i,1,3)ans=min(ans,x[i]); memset(x,0,sizeof(x));
dec(i,n,1){
memset(y,0,sizeof(y));
inc(j,1,3)if(a[i]>j){
y[j]=INF; dec(k,j,1)y[j]=min(y[j],x[k]+1);
}else{
y[j]=x[a[i]]; dec(k,j,1)if(k!=a[i])y[j]=min(y[j],x[k]+1);
}
swap(x,y);
}
inc(i,1,3)ans=min(ans,x[i]); printf("%d",ans); return 0;
}n块土地，要让它们全部都灌到水。使一个土地灌到水需要在这块土地上建水库或使它直接或间接与有水库的土地相连。给出在每块土地上建水库的费用和土地间两两连边的费用，求最小费用。n≤300
建一个超级源，让它们和所有土地连边，费用为在这块土地上建水库的费用。然后就是求最小生成树了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 400
#define inc(i,j,k) for(int i=j;i<=k;i++)
#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,fa[maxn],cnt,ans;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct e{int f,t,len;}; e es[maxn*maxn+maxn]; int ess;
bool cmp(e a,e b){return a.len<b.len;}
inline bool merge(int _x,int _y){int x=find(_x),y=find(_y); if(x==y)return 0; fa[x]=y; return 1;}
int main(){
n=read(); inc(i,1,n){int a=read(); es[++ess]=(e){0,i,a}; fa[i]=i;}
inc(i,1,n)inc(j,1,n){int a=read(); if(i<j)es[++ess]=(e){i,j,a};}
sort(es+1,es+ess+1,cmp); cnt=0;
inc(i,1,ess){if(merge(es[i].f,es[i].t))ans+=es[i].len,cnt++; if(cnt==n)break;}
printf("%d",ans); return 0;
}有N个节日，每个节日有个开始时间,及持续时间。牛想尽可能多的参加节日，问最多可以参加多少。注意牛的转移速度是极快的，不花时间，且节日必须完整参加。N≤10000，开始时刻和持续时间≤100000。
dp。设f[i]表示i时刻到最后时刻最多可以参加多少节日。则f[i]=max(f[i+1],f[range[j].r+1],j为时刻i开始的节日)。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 10100
#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;
}
struct rg{int len,n;}; rg rgs[maxn]; int f[maxn*20],n,mx,g[maxn*20];
int main(){
n=read(); inc(i,1,n){int a=read(),b=read(); rgs[i]=(rg){b,g[a]}; g[a]=i; mx=max(mx,a);}
for(int i=mx;i>=1;i--){
f[i]=f[i+1]; for(int j=g[i];j;j=rgs[j].n)f[i]=max(f[i],f[i+rgs[j].len]+1);
}
printf("%d",f[1]); return 0;
}数轴上有n个石子，第i个石头的坐标为Di，现在要从0跳到L，每次跳都从一个石子跳到相邻的下一个石子。现在问移走这M个石子后，相邻两个石子及0到最前一个石子及最后一个石子到L距离的最小值的最大值是多少。n≤50000
为什么有NOIP2015即视感~二分距离最小值，然后如果当前石子和上一个石子相差小于二分值就将这个石子移走，如果位置L与上一个石子相差小于二分值，此时若还没有移满M个且有没移走的石子，就可以将其移走，否则不合法。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50100
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,rc[maxn],l,r,ans;
bool check(int x){
int y=0,z=0;
inc(i,1,n){if(rc[i]-y<x){z++; if(z>m)return 0;}else y=rc[i];}
if(d-y<x&&(z==m||z==n))return 0; return 1;
}
int main(){
d=read(); n=read(); m=read(); inc(i,1,n)rc[i]=read(); sort(rc+1,rc+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;
}n天，每天有一个花费，现在要将它们分成连续的m段，要求所有段的总花费的最大值最小。求这个值。n，m≤100000
二分花费，小于二分值的天作为一段。注意二分的下界应该是每天花费的最大值。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100100
#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 n,m,mon[maxn],l,r,ans;
bool check(int x){
int y=1,z=0;
inc(i,1,n){
if(z+mon[i]>x){y++; z=mon[i]; if(y>m)return 0;}else z+=mon[i];
}
return 1;
}
int main(){
n=read(); m=read(); inc(i,1,n)mon[i]=read(),l=max(l,mon[i]),r+=mon[i];
while(l<=r){
int mid=(l+r)>>1; if(check(mid))ans=mid,r=mid-1;else l=mid+1;
}
printf("%d",ans); return 0;
}n头能力不一样的奶牛，给出m对奶牛之间的能力比较结果，要求判断多少奶牛的能力排名已经确定。n≤100，m≤4500。
把每个结果看成一条有向边，对每头奶牛dfs，求出每头奶牛赢几头奶牛，输几头奶牛。如果赢数加输数等于n-1，那么这头奶牛的排名就可以确定。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 101
#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;
}
struct e{int t,n;}; e es[maxn*45]; int ess,g[maxn]; bool vis[maxn];
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess;}
int win[maxn],lose[maxn],n,m,ans;
void dfs(int st,int x){
for(int i=g[x];i;i=es[i].n)if(!vis[es[i].t]){
lose[es[i].t]++; win[st]++; vis[es[i].t]=1; dfs(st,es[i].t);
}
}
int main(){
n=read(); m=read();
inc(i,1,m){int a=read(),b=read(); pe(a,b);}
inc(i,1,n)memset(vis,0,sizeof(vis)),dfs(i,i);
inc(i,1,n)if(win[i]+lose[i]==n-1)ans++; printf("%d",ans); return 0;
}此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。