题解归档：2016年10月

FJ开车去买食物，如果他的车上有X份食物。每走一里就花费X元。城市总共E里路，FJ从0开始走，到E结束（不能往回走），要买K份食物。城里有N个商店，每个商店的位置是Xi，有Fi份食物，每份Ci元。问到达E并买K份食物的最小花费。k≤100，n≤100。

题解

dp。f[i][j]表示现在在第i个商店，在j份食物。f[i][j]=f[i-1][j-k]+k*c[i]+j*(x[i]-x[i-1]),k≤fi。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 110
#define INF 1e16
#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[2][maxn]; int k,e,n,x,y; struct nd{int pos,f,c;}nds[maxn];
bool cmp(nd a,nd b){return a.pos<b.pos;}
int main(){
    k=read(); e=read(); n=read(); inc(i,1,n){nds[i].pos=read(); nds[i].f=read(); nds[i].c=read();}
    x=0; y=1; inc(i,0,k-1)f[x][i]=INF; f[x][k]=0; nds[n+1].pos=e; sort(nds+1,nds+n+1,cmp);
    for(int i=n;i>=1;i--){
        inc(j,0,k){
            f[y][j]=INF;
            inc(l,j,min(j+nds[i].f,k))
                f[y][j]=min(f[y][j],f[x][l]+(ll)(l-j)*nds[i].c+(ll)(nds[i+1].pos-nds[i].pos)*l);
        }
        swap(x,y);
    }
    printf("%lld",f[x][0]); return 0;
}

bzoj1578[Usaco2009 Feb]Stock Market 股票市场*（2016.10.11）

题意

知道S只股票D天的价格。初始时有M元，问最后最多多少钱。S≤50，D≤10，M≤200000。

题解

首先可以得出头日买了股票第二天立刻卖掉等价与拖几天再卖（因为可以卖掉后立刻买相同的数量）。故对每一天单独做完全背包，得到每天的最大收益第二天用即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3fffffff
#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 a[60][20],s,d,m,f[500010],mx;
int main(){
    s=read(); d=read(); m=read(); inc(i,1,s)inc(j,1,d)a[i][j]=read(); mx=m;
    inc(i,1,d-1){
        memset(f,0,sizeof(f));
        inc(j,1,s)inc(k,a[j][i],mx){f[k]=max(f[k],f[k-a[j][i]]+a[j][i+1]-a[j][i]);} mx=mx+f[mx];
    }
    printf("%d",mx); return 0;
}

bzoj2200[Usaco2011 Jan]道路和航线*（2016.10.13）

题意

n点图，两种边：有向边，权值可能为负数。无向边，权值为正数。求单源最短路。n≤25000，边数≤100000。

题解

听说spfa会挂，于是写了dijkstra，WA了n次后才知道dijkstra不能处理负权边QAQ。后来在ZS大爷的教导下用SLF优化spfa就过了。不过正解似乎是缩点后再dijkstra，代码量大，不会写。

SLF优化：在点即将入队时比较：如果其d值<队列头元素的d值则由队列头插入否则由队列尾插入，此处注意用STL的deque在比较队头时要判断队列会不会为空。听说此优化可以防很多卡spfa的姿势。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 500010
#define INF 2147483647
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,m1,m2,s,d[maxn]; bool inq[maxn];
struct e{int t,w,n;}; e es[maxn*4]; int ess,g[maxn];
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
deque<int>dq;
void spfa(){
    inc(i,1,n)d[i]=INF; d[s]=0; dq.push_back(s); inq[s]=1;
    while(!dq.empty()){
        int x=dq.front(); dq.pop_front(); 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]){
                if(!dq.empty()&&d[dq.front()]>d[es[i].t])dq.push_front(es[i].t);else dq.push_back(es[i].t);
                inq[es[i].t]=1;
            }
        }
    }
}
int main(){
    n=read(); m1=read(); m2=read(); s=read();
    inc(i,1,m1){int a=read(),b=read(),c=read(); pe(a,b,c); pe(b,a,c);}
    inc(i,1,m2){int a=read(),b=read(),c=read(); pe(a,b,c);} spfa();
    inc(i,1,n){d[i]==INF?puts("NO PATH"):printf("%d\n",d[i]);} return 0;
}

bzoj1774[Usaco2009 Dec]Toll 过路费*（2016.10.14）

题意

n点m边，从点a到b的费用为边权和加a到b经过点的点权最大值，给出q个询问问从a到b的最小费用。n≤200。

题解

用先对点权排序，接下来用floyd算每两个点的最短路和最小费用，因为点权已经单调了，所以求路径的点权最大值之间比较两个点和中间枚举的那个点的点权最大值即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 300
#define INF 0x3fffffff
using namespace std;

inline int read(){
    char ch=getchar(); int f=1,x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f*x;
}
struct nd{int v,id;}nds[maxn]; bool cmp(nd a,nd b){return a.v<b.v;}
int num[maxn],g[maxn][maxn],ans[maxn][maxn],n,m,k;
int main(){
    n=read(); m=read(); k=read(); inc(i,1,n)nds[i].v=read(),nds[i].id=i; sort(nds+1,nds+n+1,cmp);
    inc(i,1,n)num[nds[i].id]=i; inc(i,1,n)inc(j,i+1,n)g[i][j]=ans[i][j]=g[j][i]=ans[j][i]=INF;
    inc(i,1,m){int x=read(),y=read(),z=read(); g[num[x]][num[y]]=g[num[y]][num[x]]=min(g[num[x]][num[y]],z);}
    inc(l,1,n)inc(i,1,n)inc(j,1,n){
        g[i][j]=min(g[i][j],g[i][l]+g[l][j]);
        ans[i][j]=min(ans[i][j],g[i][j]+max(nds[l].v,max(nds[i].v,nds[j].v)));
    }
    inc(i,1,k){int x=read(),y=read(); printf("%d\n",ans[num[x]][num[y]]);} return 0;
}

bzoj3384[Usaco2004 Nov]Apple Catching 接苹果*&bzoj1750[Usaco2005 qua]Apple Catching*（2016.10.17）

题意

两棵树，每分钟会从其中一棵树上掉一个苹果下来，捡苹果的人只愿意W次，问初始在树1处最多能捡多少苹果。分钟数≤1000，W≤30。

题解

dp。f[i][j][0/1]表示第i分钟移动了j次现在在第2/1棵树下。具体看代码。

#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;
}
bool a[maxn]; int f[2][40][2],n,w,x,y,ans;
int main(){
    n=read(); w=read(); inc(i,1,n)a[i]=read()&1; x=0; y=1;
    inc(i,0,w)f[x][i][1]=0; inc(i,1,w)f[x][i][0]=0; f[x][0][0]=-INF;
    inc(i,2,n+1){
        if(!a[i-1])f[y][0][0]=f[x][0][0]+1,f[y][0][1]=f[x][0][1];
        else f[y][0][0]=f[x][0][0],f[y][0][1]=f[x][0][1]+1;
        inc(j,1,w){
            if(!a[i-1])f[y][j][0]=max(f[x][j-1][1],f[x][j][0]+1),
            f[y][j][1]=max(f[x][j-1][0]+1,f[x][j][1]);
            else f[y][j][0]=max(f[x][j-1][1]+1,f[x][j][0]),
            f[y][j][1]=max(f[x][j-1][0],f[x][j][1]+1);
        }
        swap(x,y);
    }
    inc(i,0,w)ans=max(ans,max(f[x][i][0],f[x][i][1])); printf("%d",ans); return 0;
}

bzoj1731[Usaco2005 dec]Layout 排队布局*（2016.10.18）

题意

n头奶牛在数轴上，不同奶牛可以在同个位置处，编号小的奶牛必须在前面。m条关系，一种是两头奶牛距离必须超过d，一种是两头奶牛距离不能超过d。要求：如果不存在情况满足要求则输出-1，奶牛1到n的距离可以为无限大输出-2，否则输出1到n的最大距离。

题解

差分约束系统。注意：如果是求最大值，则定义限制条件设定为≤并跑最短路，因为得到的是满足条件的最大值，如果是求最小值，则定义限制条件设定为≥并跑最长路，因为得到的是满足条件的最小值。因此按关系两边同时编号大的要向编号小的连边，之后求最短路：若存在负环输出-1，最短路为无限大输出-2，否则输出最短路。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1010
#define INF 1e16
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 e{int t; ll w; int n;}; e es[maxn*40]; int g[maxn],ess;
void pe(int f,int t,ll w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
int n,m1,m2,cnt[maxn]; ll d[maxn]; bool inq[maxn]; deque<int>q;
ll spfa(){
    memset(inq,0,sizeof(inq)); memset(cnt,0,sizeof(cnt)); inc(i,1,n)d[i]=INF;
    q.push_back(1); inq[1]=1; d[1]=0; cnt[1]=1;
    while(!q.empty()){
        int x=q.front(); q.pop_front(); 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]){
                if(!q.empty()&&d[es[i].t]<d[q.front()])q.push_front(es[i].t);else q.push_back(es[i].t);
                inq[es[i].t]=1; cnt[es[i].t]++; if(cnt[es[i].t]>=n)return -1;
            }
        }
    }
    if(d[n]==INF)return -2; return d[n];
}
int main(){
    n=read(); m1=read(); m2=read();
    inc(i,1,m1){int x=read(),y=read(),z=read(); if(x>y)swap(x,y); pe(x,y,z);}
    inc(i,1,m2){int x=read(),y=read(),z=read(); if(x>y)swap(x,y); pe(y,x,-z);} inc(i,1,n-1)pe(i+1,i,0);
    printf("%lld",spfa()); return 0;
}

bzoj2059[Usaco2010 Nov]Buying Feed 购买饲料*（2016.10.17）

题意

约翰开车来到镇上，他要带K吨饲料回家。如果他的车上有X吨饲料，每公里就要花费X^{2元，开车D公里就需要D* X}2元。约翰可以从N家商店购买饲料，所有商店都在一个坐标轴上，第i家店的位置是Xi，饲料的售价为每吨Ci元，库存为Fi。n≤500，k≤10000。

题解

dp。f[i][j]表示在第i个地方，有j吨饲料：f[i][j]=f[i-1][k]+C[i-1]*(j-k)+j*(X[i]-x[i-1])，j-k≤F[i-1]。化简得f[i][j]=f[i-1][k]-C[i-1]*k+C[i-1]*j+j*(X[i]-x[i-1])，即对每个j找到最小的f[i-1][k]-C[i-1]*k，且满足j-k≤F[i-1]，故可以用优先队列优化，使复杂度降低为O(nk)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
#define ll long long
#define INF 1e16
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;
}
long long f[2][maxn]; int n,k,e,x,y,r;
struct nd{ll x,f,c;}nds[maxn]; bool cmp(nd a,nd b){return a.x<b.x;}
struct ddq{
    deque<pair<ll,int> >dq;
    void insert(ll x,int y){
        while(!dq.empty()&&dq.back().first>=x)dq.pop_back(); dq.push_back(make_pair(x,y));
    }
    void erase(int y){
        while(!dq.empty()&&dq.front().second<=y)dq.pop_front();
    }
}ddq;
int main(){
    k=read(); e=read(); n=read(); x=0; y=1; inc(i,1,n){nds[i].x=read(); nds[i].f=read(); nds[i].c=read();}
    nds[++n]=(nd){e,0,0}; sort(nds+1,nds+n+1,cmp); inc(i,1,k)f[x][i]=INF; f[x][0]=0;
    inc(i,2,n){
        ddq.dq.clear(); r=0;
        inc(j,0,k){
            while(r<=j)ddq.insert(f[x][r]-r*nds[i-1].c,r),r++; ddq.erase(j-nds[i-1].f-1);
            if(ddq.dq.empty())f[y][j]=INF;
            else f[y][j]=ddq.dq.front().first+j*nds[i-1].c+j*j*(nds[i].x-nds[i-1].x);
        }
        swap(x,y);
    }
    printf("%lld",f[x][k]); return 0;
}

bzoj3436小K的农场（2016.10.18）

题意

n个数，知道m条关系：a-b≥c、a-b≤c或a==b。问是否存在满足所有关系的情况。n≤10000，m≤10000。

题解

差分约束。因为只要求是否满足，因此最短路最长路都可以。不过要注意如果是用spfa的bfs写法，每个点都必须作为源点判一次负环，因为图可能不连通。正因为如此，虽说加了SLF的bfs写法spfa能卡过，但比dfs写法慢不只10倍。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#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 t,w,n;}; e es[maxn*40]; int g[maxn],ess;
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
int n,m,cnt[maxn],d[maxn]; bool inq[maxn]; deque<int>q;
ll spfa(int s){
    q.clear(); memset(inq,0,sizeof(inq)); memset(cnt,0,sizeof(cnt));
    q.push_back(s); inq[s]=1; d[s]=0; cnt[s]=1;
    while(!q.empty()){
        int x=q.front(); q.pop_front(); 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]){
                if(!q.empty()&&d[es[i].t]<d[q.front()])q.push_front(es[i].t);else q.push_back(es[i].t);
                inq[es[i].t]=1; cnt[es[i].t]++; if(cnt[es[i].t]>=n)return 0;
            }
        }
    }
    return 1;
}
int main(){
    n=read(); m=read();
    inc(i,1,m){
        int opt=read(),a,b,c;
        if(opt==1)a=read(),b=read(),c=read(),pe(a,b,-c);
        if(opt==2)a=read(),b=read(),c=read(),pe(b,a,c);
        if(opt==3)a=read(),b=read(),pe(b,a,0),pe(a,b,0);
    }
    inc(i,1,n)if(!spfa(i)){puts("No"); return 0;} puts("Yes"); return 0;
}

bzoj1733[Usaco2005 feb]Secret Milking Machine 神秘的挤奶机*（2016.10.18）

题意

n点无向图。要从1走到nT次，问不重复经过每条路的方案中最长路径长度的最小值。n≤200，边权≤1000000。

题解

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 40010
#define INF 0x3fffffff
using namespace std;

inline int read(){
    char ch=getchar(); int f=1,x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f*x;
}
struct e{int t,c,n;}es[maxn*4]; 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;}
void init(){memset(g,0,sizeof(g)); ess=1;}
int n,p,k,f[maxn],t[maxn],w[maxn],l,r,ans;
queue<int>q; int h[maxn];
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;i=es[i].n)if(h[es[i].t]==-1&&es[i].c){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 w,u=0;
    for(int i=g[x];i;i=es[i].n)if(h[es[i].t]==h[x]+1&&es[i].c){
        w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(!f)return u;
    }
    if(!u)h[x]=-1; return u;
}
int dinic(int x){
    init(); inc(i,1,p)if(w[i]<=x)pe(f[i],t[i],1),pe(t[i],f[i],1); int f=0;
    while(bfs(1,n))f+=dfs(1,n,INF); return f;
}
int main(){
    n=read(); p=read(); k=read(); inc(i,1,p)f[i]=read(),t[i]=read(),w[i]=read(); l=0; r=1000000;
    while(l<=r){
        int mid=(l+r)>>1; if(dinic(mid)>=k)ans=mid,r=mid-1;else l=mid+1;
    }
    printf("%d",ans); return 0;
}

bzoj3016[Usaco2012 Nov]Clumsy Cows*（2016.10.19）

题意

给定长度为n的一个括号序列，每次修改可以修改一个位置的括号，若这个括号为’(‘，则修改为’)’，若这个括号为’)’，则修改为’(‘，问最少修改多少个使得原括号序列合法。

其中：()是合法的；若A是合法的，则(A)是合法的；若A，B都是合法的，则AB是合法的。n≤100000。

题解

思路很简单，然而我没法知道它的正确性：对序列扫一遍，如果遇到右括号且当前右括号个数大于左括号个数，则将该右括号改为左括号。扫完之后统计若左括号多则往后将一半的左括号改为右括号。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std;

char ch; int s,ans;
int main(){
    ch=getchar();
    while(ch!='\n'){
        if(ch=='(')s++; if(ch==')'){s--; if(s<0)s+=2,ans++;} ch=getchar();
    }
    ans+=s/2; printf("%d",ans); return 0;
}

bzoj1742[Usaco2005 nov]Grazing on the Run 边跑边吃草*&bzoj3074[Usaco2013 Mar]The Cow Run*（2016.10.19）

题意

数轴上有n棵草，牛初始在L位置（bzoj3074的牛初始在1位置），每移动一个单位需要+1s。而每过1s没吃的草腐败度会+1，问吃完所有草的最小腐败度。n≤1000。

题解

很神的dp。f[l][r][0/1]表示从第l棵草吃到第r棵草，之后到达l/r。则

f[l][r][0]=min(dfs(l+1,r,0)+(n-r+l)*(a[l+1]-a[l]),dfs(l+1,r,1)+(n-r+l)*(a[r]-a[l])); f[l][r][1]=min(dfs(l,r-1,1)+(n-r+l)*(a[r]-a[r-1]),dfs(l,r-1,0)+(n-r+l)*(a[r]-a[l]));

之所以要乘(n-r+l)的原因是在当前的转移的同时所有未吃的草的腐败度都增加了等同于当前转移时间的值。

为了方便处理，先增加一棵虚拟的草位置为l，接下来设除了虚拟的草所有f[i][i]为正无穷，而那棵虚拟的草对于的f[i][i]=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 1e16
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][2]; int a[maxn],n,l;
ll dfs(int l,int r,int b){
    if(f[l][r][b]!=-1)return f[l][r][b];
    if(!b)f[l][r][b]=min(dfs(l+1,r,0)+(n-r+l)*(a[l+1]-a[l]),dfs(l+1,r,1)+(n-r+l)*(a[r]-a[l]));
    else f[l][r][b]=min(dfs(l,r-1,1)+(n-r+l)*(a[r]-a[r-1]),dfs(l,r-1,0)+(n-r+l)*(a[r]-a[l]));
    return f[l][r][b];
}
int main(){
    n=read(); l=read(); memset(f,-1,sizeof(f));
    inc(i,1,n)a[i]=read(); a[++n]=l; sort(a+1,a+n+1); inc(i,1,n)f[i][i][0]=f[i][i][1]=INF;
    inc(i,1,n)if(a[i]==l){f[i][i][0]=f[i][i][1]=0; break;}
    printf("%lld",min(dfs(1,n,0),dfs(1,n,1))); return 0;
}

bzoj1661[Usaco2006 Nov]Big Square 巨大正方形*（2016.10.23）

题意

n*n的图中有一些J点，一些B点和一些空白点，问在空白点添加一个J点所能得到的有4个J点组成最大正方形面积。n≤100。

题解

枚举两个点，然后根据这两个点组成的边尝试在4个上下两个方向组成四边形。

#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;

char graph[maxn][maxn]; int n,ans;
int main(){
    scanf("%d",&n); inc(i,1,n)scanf("%s",graph[i]+1);
    inc(i,1,n)inc(j,1,n)if(graph[i][j]=='J'){
        inc(k,i+1,n){
            inc(l,1,j){
                int cnt=1;
                if(graph[k][l]=='B')continue; if(graph[k][l]=='J')cnt++;
                int x=l-j,y=k-i;
                if(k-x>n||l+y>n||graph[k-x][l+y]=='B')goto jump1; if(graph[k-x][l+y]=='J')cnt++;
                if(i-x>n||j+y>n||graph[i-x][j+y]=='B')goto jump1; if(graph[i-x][j+y]=='J')cnt++;
                if(cnt>=3)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));
                jump1:;
                if(k+x<1||l-y<1||graph[k+x][l-y]=='B')goto jump2; if(graph[k+x][l-y]=='J')cnt++;
                if(i+x<1||j-y<1||graph[i+x][j-y]=='B')goto jump2; if(graph[i+x][j-y]=='J')cnt++;
                if(cnt>=3)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));
                jump2:;
            }
            inc(l,j+1,n){
                int cnt=1;
                if(graph[k][l]=='B')continue; if(graph[k][l]=='J')cnt++;
                int x=l-j,y=k-i;
                if(k-x<1||l+y>n||graph[k-x][l+y]=='B')goto jump3; if(graph[k-x][l+y]=='J')cnt++;
                if(i-x<1||j+y>n||graph[i-x][j+y]=='B')goto jump3; if(graph[i-x][j+y]=='J')cnt++;
                if(cnt>=3)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));
                jump3:;
                if(k+x>n||l-y<1||graph[k+x][l-y]=='B')goto jump4; if(graph[k+x][l-y]=='J')cnt++;
                if(i+x>n||j-y<1||graph[i+x][j-y]=='B')goto jump4; if(graph[i+x][j-y]=='J')cnt++;
                if(cnt>=3)ans=max(ans,(k-i)*(k-i)+(j-l)*(j-l));
                jump4:;
            }
        }
    }
    printf("%d",ans); return 0;
}

bzoj3062[Usaco2013 Feb]Taxi*（2016.10.23）

题意

Bessie在农场上为其他奶牛提供出租车服务，她必须赶到这些奶牛的起始位置，并把他们带到它们的目的地。Bessie的车很小，所以她只能一次只能搭载一头奶牛。N只奶牛的起始位置和结束为止都是已知的，请确定Bessie从0点出发完成任务再到m点的最少行程。Bessie意识到，要使所得到的行程最短，Bessie可能将在沿途中让奶牛上车或下车而并不一定将一头奶牛从起点直接送到终点。n≤100000，m≤1000000000。

题解

神贪心……首先每只奶牛从起点到终点的这段路程是不可避免的，所以先将它们计入答案，之后的目标是尽量减少空车的时间。接着会发现最优策略应该是载着某牛的过程中刚好遇到要坐车的奶牛，就把当前奶牛放下载这只，载完后再回到此地（此过程即是我们要最小化的“空车”阶段）接之前被放下的奶牛（注意在此过程中有可能出现多只奶牛被放下的情况）。故在起点数组里加入m，终点数组里加入0，对它们排序，接着答案依次累加abs(a[i]-b[i])。

#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,m,a[maxn],b[maxn]; long long ans;
int main(){
    n=read(); m=read(); inc(i,1,n)a[i]=read(),b[i]=read(); inc(i,1,n)ans+=abs(a[i]-b[i]);
    a[++n]=m; b[n]=0; sort(a+1,a+n+1); sort(b+1,b+n+1); inc(i,1,n)ans+=abs(a[i]-b[i]);
    printf("%lld",ans); return 0;
}

bzoj3355[Usaco2004 Jan]有序奶牛*（2016.10.24）

题意

约翰的N头牛排成一行挤奶时，有确定的顺序。他拥有L条关于奶牛顺序的信息，所有的信息都写成“A在B的前面”这样的形式。请帮助约翰删除尽可能多的冗余信息，但要保证能推出原有的顺序。n≤1500。

题解

首先拓扑排序，并给每个节点设定一个bitset存储哪些点能到达此点。接着按边终点拓扑序升序为第一关键字，起点拓扑序降序为第二关键字依次插边，如果当前终点的bitset里起点不为1则该边保留，并将终点的bitset和起点的bitset合并，否则该边不保留。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <bitset>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1510
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*100],es2[maxn*100]; int g[maxn],tot;
void pe(int f,int t,int ess){es[ess]=(e){f,t,g[f]}; g[f]=ess;}
int n,l,topo[maxn],du[maxn];
bool cmp1(e a,e b){return topo[a.t]==topo[b.t]?topo[a.f]>topo[b.f]:topo[a.t]<topo[b.t];}
bool cmp2(e a,e b){return a.f==b.f?a.t<b.t:a.f<b.f;}
queue<int>q; bitset<maxn>f[maxn];
int main(){
    n=read(); l=read(); inc(i,1,l){int x=read(),y=read(); pe(x,y,i); du[y]++;} inc(i,1,n)if(!du[i])q.push(i);
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(int i=g[x];i;i=es[i].n){
            du[es[i].t]--; if(!du[es[i].t])q.push(es[i].t),topo[es[i].t]=topo[x]+1;
        }
    }
    sort(es+1,es+l+1,cmp1); inc(i,1,n)f[i][i]=1;
    inc(i,1,l){if(!f[es[i].t][es[i].f])es2[++tot]=es[i]; f[es[i].t]|=f[es[i].f];}
    sort(es2+1,es2+tot+1,cmp2); printf("%d\n",tot);
    inc(i,1,tot)printf("%d %d\n",es2[i].f,es2[i].t); return 0;
}

bzoj1747[Usaco2005 open]Expedition 探险*（2016.10.25）

题意

n个加油站，每个坐标为x，可加油量为ai。一辆车初始油量为l，从起点到终点，每走一个单位就掉一个单位的油，问最少加油次数。n≤10000，坐标≤1000000。

题解

先假设永远不加油，之后每走一段路之前如果油不够，就从之前经过的加油站中找一个可加油量最大的站加油并去掉这个加油站，答案+1，这一过程用优先队列维护。

#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 n,l,p,ans,now; struct nd{int p,v;}nds[maxn]; bool cmp(nd a,nd b){return a.p<b.p;}
priority_queue<int>q;
int main(){
    n=read(); inc(i,1,n)nds[i].p=read(),nds[i].v=read(); l=read(); p=read();
    inc(i,1,n)nds[i].p=l-nds[i].p; nds[++n]=(nd){0,p}; nds[++n]=(nd){l,0}; sort(nds+1,nds+n+1,cmp);
    inc(i,1,n-1){
        q.push(nds[i].v); while(!q.empty()&&nds[i+1].p-nds[i].p>now)now+=q.top(),q.pop(),ans++;
        if(q.empty()&&nds[i+1].p-nds[i].p>now){printf("-1"); goto end;} now-=(nds[i+1].p-nds[i].p);
    }
    printf("%d",ans-1);
    end: return 0;
}

bzoj3011[Usaco2012 Dec]Running Away From the Barn*（2016.10.25）

题意

给出以1号点为根的一棵有边权的树，问每个点的子树中与它距离小于l的点有多少个。树的大小≤200000。

题解

每个节点维护一个带标记可并堆，dfs时对子节点的堆加上当前节点到该子节点的边权，之后令其与当前节点的堆合并。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 200010
#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 rt[maxn],n,ch[maxn][2],ans[maxn]; ll v[maxn],tg[maxn],l;
struct e{int t; ll w; int n;}es[maxn]; int g[maxn],ess;
void pushdown(int x){
    if(tg[x]){
        if(ch[x][0])v[ch[x][0]]+=tg[x],tg[ch[x][0]]+=tg[x];
        if(ch[x][1])v[ch[x][1]]+=tg[x],tg[ch[x][1]]+=tg[x];
        tg[x]=0;
    }
}
int merge(int x,int y){
    if(!x||!y)return x+y; if(v[x]<v[y])swap(x,y); pushdown(x);
    ch[x][1]=merge(ch[x][1],y); swap(ch[x][0],ch[x][1]); return x;
}
int pop(int x){
    pushdown(x); return merge(ch[x][0],ch[x][1]);
}
void dfs(int x,int fa){
    for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa){
        dfs(es[i].t,x); tg[rt[es[i].t]]+=es[i].w; v[rt[es[i].t]]+=es[i].w;
        rt[x]=merge(rt[x],rt[es[i].t]); ans[x]+=ans[es[i].t];
    }
    while(v[rt[x]]>l)rt[x]=pop(rt[x]),ans[x]--;
}
int main(){
    n=read(); l=read(); inc(i,2,n){int x=read(); ll y=read(); es[i-1]=(e){i,y,g[x]}; g[x]=i-1;}
    inc(i,1,n)rt[i]=i,v[i]=0,tg[i]=0,ans[i]=1,ch[i][0]=ch[i][1]=0; dfs(1,0);
    inc(i,1,n)printf("%d\n",ans[i]); return 0;
}

bzoj2590[Usaco2012 Feb]Cow Coupons*（2016.10.31）

题意

市场上有N头奶牛，第i头奶牛价格为Pi。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为Ci，每头奶牛只能使用一次优惠券。FJ想知道花不超过M的钱最多可以买多少奶牛。n≤50000，m≤10^14。

题解

先按ci升序排序，把前k头买下来（如果可以的话）接着把剩下的牛按pi升序排序：如果当前奶牛优惠价与原价差值比k头奶牛中最大的一头大，则花那一头优惠价与原价差值把优惠券“赎”回来，并用优惠价买当前奶牛；否则直接以原价买当前奶牛。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50010
#define INF 0x3fffffff
#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{int p,c;}nds[maxn]; int n,k; ll m,sum; priority_queue<int,vector<int>,greater<int> >q;
bool cmp1(nd a,nd b){return a.c<b.c;}
bool cmp2(nd a,nd b){return a.p<b.p;}
int main(){
    n=read(); k=read(); m=read(); inc(i,1,n)nds[i].p=read(),nds[i].c=read(); sort(nds+1,nds+1+n,cmp1);
    inc(i,1,k){
        sum+=nds[i].c; if(sum>m){printf("%d",i-1); goto end;}
        if(i==n){printf("%d",n); goto end;} q.push(nds[i].p-nds[i].c);
    }
    sort(nds+1+k,nds+n+1,cmp2);
    inc(i,k+1,n){
        int t=q.empty()?INF:q.top();
        if(nds[i].p-nds[i].c>t){sum+=t; q.pop(); sum+=nds[i].c; q.push(nds[i].p-nds[i].c);}else sum+=nds[i].p;
        if(sum>m){printf("%d",i-1); goto end;} if(i==n){printf("%d",n); goto end;}
    }
    end: return 0;
}

bzoj1109[POI2007]堆积木Klo*（2016.10.31）

题意

n个数，第i个数为ai，现在要移走一些数，使得移走后有最多的数位于它对应的位置上。求移走的数。n≤100000。

题解

dp方程：f[i]=f[j]+1(i>j,a[i]>a[j],a[i]-a[j]>=i-j即a[i]-i>=a[j]-j)，而第一个限制条件是可以由后两个限制条件所推出，因此只要在满足第二个条件的前提下求满足第三个条件的即可，而这可以在对ai排序后用关于a[i]-i]的最长上升子序列解决。本弱用的是树状数组（将数从小到大插入，每次求其左边的f最大值+1），复杂度O(nlog2n)。（听说这叫二维偏序）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#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 n,c[maxn],ans,tot; pair<int,int>nds[maxn];
inline void add(int x,int y){while(x<=n)c[x]=max(c[x],y),x+=lb(x);}
inline int query(int x){int q=0; while(x>=1)q=max(q,c[x]),x-=lb(x); return q;}
int main(){
    n=read(); inc(i,1,n){int x=read(); if(i-x>=0)nds[++tot]=make_pair(i-x,x);}
    sort(nds+1,nds+1+tot);
    inc(i,1,tot){int x=query(nds[i].second-1)+1; ans=max(ans,x); add(nds[i].second,x);}
    printf("%d",ans); return 0;
}

bzoj2020[Usaco2010 Jan]Buying Feed, II*（2016.10.11）

题意

题解