bzoj Usaco补完计划(优先级 Gold>Silver>资格赛)

　　听说KPM初二暑假就补完了啊%%%

　　先刷Gold再刷Silver（因为目测没那么多时间刷Silver，方便以后TJ2333（雾

　　按AC数降序刷

-------------------------------------------------------------------------------------------------------

　　bzoj1597: [Usaco2008 Mar]土地购买

　　　　斜率优化DP

　　　　h升序，w降序。

　　　　f[i]=min(f[j]+h[i]*w[j+1])

　　　　(h[j]-h[k])/(w[k+1]-w[j+1])<h[i]

　　　　所以下凸，斜率不下降

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=;

struct poi{int h,w;}a[maxn];

int n,m,x,y,z,l,r,tot,h[maxn],w[maxn];

ll q[maxn],f[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.h==b.h?a.w<b.w:a.h<b.h;}

double xl(int x,int y){return (f[y]-f[x])/(w[x+]-w[y+]);}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i].h),read(a[i].w);

    sort(a+,a++n,cmp);

    for(int i=;i<=n;i++)

    {

        while(tot&&w[tot]<=a[i].w)tot--;

        h[++tot]=a[i].h;w[tot]=a[i].w;

    }

    l=;r=;

    for(int i=;i<=tot;i++)

    {

        while(l<r&&xl(q[l],q[l+])<h[i])l++;

        f[i]=f[q[l]]+1ll*h[i]*w[q[l]+];

        while(l<r&&xl(q[r-],q[r])>xl(q[r],i))r--;

        q[++r]=i;

    }

    printf("%lld\n",f[tot]);

    return ;

}

　　bzoj1699: [Usaco2007 Jan]Balanced Lineup排队

　　　　裸RMQ

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

int n,m,f[][],g[][],l,r,k;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int log2(int x){return log(x)/log();}

int exp(int x){return <<x;}

void rmq()

{

    for(int j=;j<=log2(n);j++)

    for(int i=;i<=n-exp(j)+;i++)

    f[i][j]=max(f[i][j-],f[i+exp(j-)][j-]),g[i][j]=min(g[i][j-],g[i+exp(j-)][j-]);

}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)read(f[i][]),g[i][]=f[i][];

    rmq();

    for(int i=;i<=m;i++)

    {

        read(l);read(r);

        k=log2(r-l+);

        printf("%d\n",max(f[l][k],f[r-exp(k)+][k])-min(g[l][k],g[r-exp(k)+][k]));

    }

}

　　bzoj1666: [Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏

　　　　直接模拟

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

using namespace std;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int ans,n;

int main()

{

    read(n);

    while(n!=)

    {

        ans++;

        if(n&)n=n*+;

        else n/=;

    }

    printf("%d\n",ans);

}

　　bzoj1692: [Usaco2007 Dec]队列变换

　　　　hash+二分logn比较正反后缀字典序

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#define ull unsigned long long

using namespace std;

ull mul[],hs[],ophs[],L,R,l,r,mid,len,num,n;

char s[];

void read(ull &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int lcp()

{

    l=;r=R-L+;

    while(l<r)

    {

        mid=(l+r+)>>;

        int hs1=hs[L+mid-]-hs[L-]*mul[mid];

        int hs2=ophs[R-mid+]-ophs[R+]*mul[mid];

        if(hs1!=hs2)r=mid-;else l=mid;

    }

    return l;

}

bool cmp()

{

    if(s[L]!=s[R])return s[L]>s[R];

    len=lcp();

    if(len==R-L+)return ;

    else return s[L+len]>s[R-len];

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)

    for(s[i]=getchar();s[i]<'A'||s[i]>'Z';s[i]=getchar());

    mul[]=;

    for(int i=;i<=n;i++)mul[i]=mul[i-]*;

    for(int i=;i<=n;i++)hs[i]=hs[i-]*+(ull)s[i]-'A';

    for(int i=n;i;i--)ophs[i]=ophs[i+]*+(ull)s[i]-'A';

    L=;R=n;num=;

    for(int i=;i<=n;i++,num++)

    {

        printf("%c",cmp()?s[R--]:s[L++]);

        if(num==)printf("\n"),num=;

    }

}

　　bzoj1717: [Usaco2006 Dec]Milk Patterns 产奶的模式

　　　　可重叠k次最长重复子串

　　　　二分答案，h[]>=mid的分一段，如果有一段的后缀个数>=k则合法。

　　　　多关键字基数排序。

　　　　a[]为A关键字

　　　　b[]为B关键字排序后的数组（作为排序后数组的答案）

　　　　for(int i=1;i<=n;i++)sum[a[i]]++;
　　　　for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
　　　　for(int i=n;i;i--)sa[sum[a[b[i]]]=b[i],sum[a[b[i]]]--;

　　　　而在SA中

　　　　for(int i=1;i<=n;i++)rk[i]=trk[tsa[i]],sum[rk[i]]++;
　　　　for(int i=2;i<=m;i++)sum[i]+=sum[i-1];
　　　　for(int i=n;i;i--)sa[sum[rk[i]]]=tsa[i],sum[rk[i]]--;

　　　　A B关键字就是字符的字典序。

　　　　a[]实际上是trk[]

　　　　b[]是tsa[]

　　　　定义了一个rk[]=trk[tsa[]]

　　　　那么多关键字排序的时候就sa[sum[trk[tsa[]]]]变成了sa[sum[rk[]]]。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

using namespace std;

const int maxn=;

int n,m,p,k,l,r;

int sum[maxn],rk[maxn],sa[maxn],trk[maxn],tsa[maxn],h[maxn],s[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void suffix()

{

    for(int i=;i<=n;i++)sum[s[i]]++;

    for(int i=;i<=;i++)sum[i]+=sum[i-];

    for(int i=n;i;i--)sa[sum[s[i]]]=i,sum[s[i]]--;

    rk[sa[]]=;p=;

    for(int i=;i<=n;i++)rk[sa[i]]=(s[sa[i]]!=s[sa[i-]])?++p:p;

    m=p;int j=;

    while(m<n)

    {

        memcpy(trk,rk,sizeof(rk));memset(sum,,sizeof(sum));p=;

        for(int i=n-j+;i<=n;i++)tsa[++p]=i;

        for(int i=;i<=n;i++)if(sa[i]>j)tsa[++p]=sa[i]-j;

        for(int i=;i<=n;i++)rk[i]=trk[tsa[i]],sum[rk[i]]++;

        for(int i=;i<=m;i++)sum[i]+=sum[i-];

        for(int i=n;i;i--)sa[sum[rk[i]]]=tsa[i],sum[rk[i]]--;

        rk[sa[]]=;p=;

        for(int i=;i<=n;i++)rk[sa[i]]=(trk[sa[i]]!=trk[sa[i-]]||trk[sa[i]+j]!=trk[sa[i-]+j])?++p:p;

        m=p;j*=;

    }

    h[]=;p=;

    for(int i=;i<=n;i++)

    {

        if(rk[i]==)continue;

        j=sa[rk[i]-];

        while(s[i+p]==s[j+p])p++;

        h[rk[i]]=p;

        if(p)p--;

    }

}

bool check(int mid)

{

    int num=;

    for(int i=;i<=n;i++)

    if(h[i]>=mid)num++;

    else

    {

        if(num>=k)return ;

        num=;

    }

    if(num>=k)return ;

    return ;

}

int main()

{

    read(n);read(k);

    for(int i=;i<=n;i++)read(s[i]);

    suffix();

    l=;r=n;

    while(l<r)

    {

        int mid=(l+r+)>>;

        if(check(mid))l=mid;

        else r=mid-;

    }

    printf("%d\n",l);

}

　　bzoj1724: [Usaco2006 Nov]Fence Repair 切割木板

　　　　堆，每次合并最小的两个木板

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#define ll long long

using namespace std;

struct poi{int sum;};

priority_queue<poi>q;

bool operator <(poi a,poi b){return a.sum>b.sum;};

int x,y,n;

ll ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(x),q.push((poi){x});

    for(int i=;i<n;i++)

    {

        x=q.top().sum;q.pop();

        y=q.top().sum;q.pop();

        ans+=x+y;

        q.push((poi){x+y});

    }

    printf("%lld\n",ans);

}

　　bzoj1572: [Usaco2009 Open]工作安排Job

　　　　能加就加；加不进去还是加进去，然后删掉最小的。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#include<queue>

#define ll long long

using namespace std;

struct poi{ll d,p;}a[];

struct tjm{ll p;};

priority_queue<tjm>q;

bool operator<(tjm a,tjm b){return a.p>b.p;}

ll n,x,t;

long long ans;

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return (a.d<b.d)||((a.d==b.d)&&(a.p>b.p));}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i].d),read(a[i].p);

    sort(a+,a++n,cmp);

    t=;

    for(int i=;i<=n;i++)

    {

        if(a[i].d<t)

        {

            x=q.top().p;

            if(a[i].p>x)

            {

                ans=ans-x+a[i].p;

                q.pop();

                q.push((tjm){a[i].p});

            }

        }

        else

        {

            t++;

            q.push((tjm){a[i].p});

            ans+=a[i].p;

        }

    }

    printf("%lld\n",ans);

}

　　bzoj1726: [Usaco2006 Nov]Roadblocks第二短路

　　　　次短路模板

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int inf=,maxn=,maxm=;

struct zs{int too,sum,pre;}e[maxm];

int n,m,tot,front,rear;

int dist[maxn],dist2[maxn],v[maxn],last[maxn],h[maxm],x,y,z;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void spfa(int x)

{

    for(int i=;i<=n;i++)dist[i]=inf,dist2[i]=inf,v[i]=;

    v[x]=;dist[x]=;rear=;front=;h[]=x;

    while(front!=rear)

    {

        int now=h[++front];if(front==maxm)front=-;

        for(int i=last[now];i;i=e[i].pre)

        {

            int too=e[i].too,dis=dist[now]+e[i].sum;

            bool flag=;

            if(dist[too]>dis)dist2[too]=dist[too],dist[too]=dis,flag=;

            if(dist[too]<dis&&dist2[too]>dis)dist2[too]=dis,flag=;

            if(dist2[too]>dist2[now]+e[i].sum)dist2[too]=dist2[now]+e[i].sum,flag=;

            if(flag&&!v[too])

            {

                v[too]=;

                h[++rear]=too;

                if(rear==maxm)rear=-;

            }

        }

        v[now]=;

    }

}

int main()

{

    read(n);read(m);

    for(int i=;i<=m;i++)

    read(x),read(y),read(z),add(x,y,z),add(y,x,z);

    spfa();

    printf("%d\n",dist2[n]);

    return ;

}

　　bzoj1579: [Usaco2009 Feb]Revamping Trails 道路升级

　　　　分层图（优先队列好慢。。。但是不会被卡

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<queue>

#define ll long long

using namespace std;

const int inf=,maxn=,maxm=;

struct poi{ll dis,pos,ceng;};

struct zs{int too,sum,pre;}e[maxm];

priority_queue<poi>q;

bool operator<(poi a,poi b){return a.dis>b.dis;}

int n,m,k,tot,x,y,z,last[maxn];;

ll dist[maxn][],ans;

bool v[maxn][];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void spfa(int x)

{

    for(int i=;i<=n;i++)for(int j=;j<=k;j++)dist[i][j]=inf,v[i][j]=;

    v[x][]=;dist[x][]=;q.push((poi){,x});

    while(!q.empty())

    {

        poi now=q.top();int ceng=now.ceng;q.pop();

        for(int i=last[now.pos];i;i=e[i].pre)

        {

            int too=e[i].too;

            if(dist[too][ceng]>dist[now.pos][ceng]+e[i].sum)

            {

                dist[too][ceng]=dist[now.pos][ceng]+e[i].sum;

                if(!v[too][ceng])

                {

                    v[too][ceng]=;

                    q.push((poi){dist[too][ceng],too,ceng});

                }

            }

            if(dist[too][ceng+]>dist[now.pos][ceng]&&ceng<k)

            {

                dist[too][ceng+]=dist[now.pos][ceng];

                if(!v[too][ceng+])

                {

                    v[too][ceng+]=;

                    q.push((poi){dist[too][ceng+],too,ceng+});

                }

            }

        }

        v[now.pos][ceng]=;

    }

}

int main()

{

    read(n);read(m);read(k);

    for(int i=;i<=m;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);

    spfa();

    ans=inf;

    for(int i=;i<=k;i++)

    ans=min(ans,dist[n][i]);

    printf("%lld\n",ans);

}

　　bzoj1690: [Usaco2007 Dec]奶牛的旅行

　　　　最优比率环。以前写过篇题解，当时没有真的懂，看了一下分数规划终于明白了。已经更新以前的题解。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<queue>

using namespace std;

struct zs{int too,pre;double dis;}e[];

struct poi{int pos;double dis;};

priority_queue<poi>q;

bool operator <(poi a,poi b){return a.dis-b.dis>1e-;}

int n,m,x,y,now,tot,num[],last[];

bool v[];

double l,r,mid,dis[],fun[];

bool spfa(int x)

{

    for(int i=;i<=n;i++)dis[i]=;v[x]=true;q.push((poi){,});dis[]=;

    while(!q.empty())

    {

        int i,too;

        for(i=last[now=q.top().pos],too=e[i].too,q.pop();i;i=e[i].pre,too=e[i].too)

        {

            double dist=e[i].dis*mid-fun[too];

            if(dis[too]-dis[now]-dist>1e-)

            {

                dis[too]=dis[now]+dist;

                if(!v[too])v[too]=,q.push((poi){too,e[i].dis}),num[too]++;

                if(num[too]>)return ;

            }

        }

        v[now]=;

    }

    return ;

}

int main()

{

    scanf("%d %d",&n,&m);

    for(int i=;i<=n;i++)scanf("%lf",&fun[i]);

    for(int i=;i<=m;i++)

    {

        scanf("%d %d %lf",&x,&y,&e[++tot].dis);

        e[tot].too=y;e[tot].pre=last[x];last[x]=tot;

    }

    l=;r=;

    while(r-l>1e-)

    {

        memset(v,,sizeof(v));

        memset(num,,sizeof(num));

        mid=(l+r)/;

        if(spfa())l=mid;

        else r=mid;

    }

    printf("%.2lf",l);

}

　　bzoj1711: [Usaco2007 Open]Dining吃饭

　　　　三分图，牛i拆成i和i'，S连食物，食物连i，i'连饮料，饮料连T，最大流。

　　　　脑洞大开问了下CZL，如果有多一种种类的话就把牛右边改成100*100个点表示另外两种怎么选，自己yy的写法被CZL随手叉掉，还学习了一波随机化的姿势和卡掉随机化的姿势，受益匪浅嘿嘿嘿

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

using namespace std;

const int inf=,maxn=;

struct poi{int too,pre,cf;}e[];

int n,m,tot,ans,x,y,z,front,rear,fd,dk,ffd,ddk,sum;

int h[maxn],v[maxn],last[maxn],dis[maxn],cur[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z)

{

    e[++tot].too=y;e[tot].cf=z;e[tot].pre=last[x];last[x]=tot;

    e[++tot].too=x;e[tot].pre=last[y];last[y]=tot;

}

bool bfs()

{

    for(int i=;i<=sum;i++)v[i]=,dis[i]=-;

    dis[]=;v[]=;h[]=;front=;rear=;

    while(front!=rear)

    {

        int now=h[++front];if(front==maxn)front=-;

        for(int i=last[now];i;i=e[i].pre)

        {

            int too=e[i].too;

            if(!v[too]&&e[i].cf)

            {

                dis[too]=dis[now]+;if(too==sum)return ;

                v[too]=;h[++rear]=too;if(rear==maxn)rear=-;

            }

        }

    }

    return ;

}

int dfs(int x,int f)

{

    int flow=,tmp;

    if(x==sum)return f;

    for(int &i=cur[x];i;i=e[i].pre)

    {

        int too=e[i].too;

        if(dis[too]==dis[x]+&&e[i].cf)

        {

            tmp=dfs(too,min(f-flow,e[i].cf));

            e[i].cf-=tmp;e[i^].cf+=tmp;flow+=tmp;

            if(f==flow)return f;

        }

    }

    return flow;

}

void dinic()

{

    while(bfs())

    {

        for(int i=;i<=sum;i++)cur[i]=last[i];

        ans+=dfs(,inf);

    }

}

int main()

{

    tot=;

    read(n);read(fd);read(dk);sum=fd+n*+dk+;

    for(int i=;i<=fd;i++)add(,i,);

    for(int i=;i<=dk;i++)add(i+fd+n*,sum,);

    for(int i=;i<=n;i++)add(i+fd,i+n+fd,);

    for(int i=;i<=n;i++)

    {

        read(ffd);read(ddk);

        for(int j=;j<=ffd;j++)

        {

            read(x);

            add(x,i+fd,);

        }

        for(int j=;j<=ddk;j++)

        {

            read(x);

            add(i+n+fd,x+fd+n*,);

        }

    }

    dinic();

    printf("%d\n",ans);

}

　　bzoj1708: [Usaco2007 Oct]Money奶牛的硬币

　　　　裸完全（无限？）背包。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#define ll long long

using namespace std;

ll n,v,x,f[];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(v);read(n);

    f[]=;

    for(int i=;i<=v;i++)

    {

        read(x);

        for(int j=x;j<=n;j++)

        f[j]+=f[j-x];

    }

    printf("%lld\n",f[n]);

    return ;

}

　　bzoj1827: [Usaco2010 Mar]gather 奶牛大集会

　　　　树上处理题。第一次dfs记录下size[x]表示子树有几只牛和dis[x]表示子树所有牛到x的距离，第二次求总距离，每次到子节点时，总距离就加上边权*（n-size[son]），减去边权*（n-size[son])，也就是加上边权*（n-2*size[son]）。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=;

struct poi{int too,pre,sum;}e[];

int last[maxn];

ll n,x,y,z,tot,cnt;

ll dis[maxn],size[maxn],ans;

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void dfs(int x,int fa)

{

    for(int i=last[x];i;i=e[i].pre)

    {

        if(e[i].too==fa)continue;

        dfs(e[i].too,x);

        size[x]+=size[e[i].too];

        dis[x]+=dis[e[i].too]+size[e[i].too]*e[i].sum;

    }

}

void dfs2(int x,int fa,ll dist)

{

    ans=min(ans,dist);

    for(int i=last[x];i;i=e[i].pre)

    {

        if(e[i].too==fa)continue;

        ll sum=e[i].sum*(cnt-*size[e[i].too]);

        dfs2(e[i].too,x,dist+sum);

    }

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(size[i]),cnt+=size[i];

    for(int i=;i<n;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);

    dfs(,);

    ans=dis[];

    dfs2(,,dis[]);

    printf("%lld\n",ans);

    return ;

}

　　bzoj1725: [Usaco2006 Nov]Corn Fields牧场的安排

　　　　状压

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int n,m,x;

ll ans,f[][],state[];

bool v[];

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            read(x);

            if(x)

            state[i]|=(<<(j-));

        }

    }

    int st=(<<m)-;

    v[]=;

    for(int i=;i<=st;i++)

    {

        int flag=;

        for(int j=;j<m;j++)

        if((((i>>(j-))&))&((i>>j)&)==)

        {

            flag=;

            break;

        }

        v[i]=flag;

    }

    f[][]=;

    for(int i=;i<=n;i++)

    for(int j=;j<=st;j++)

    if(v[j])

    if((j|state[i])==state[i])

    for(int k=;k<=st;k++)

    if(v[k])

    if((k|state[i-])==state[i-])

    if((j&k)==)

    f[i][j]=(f[i][j]+f[i-][k])%;

    for(int i=;i<=st;i++)

    ans=(ans+f[n][i])%;

    printf("%lld\n",ans);

    return ;

}

　　bzoj1592: [Usaco2008 Feb]Making the Grade 路面修整

　　　　首先可以证明一个结论，最后修改出的序列的数字还是原序列的数字，因为是不下降或者不上升，直接改到一样显然是最优的，不然必然会多改一点。

　　　　于是把高度离散化，枚举i和高度就行了，前一个路面的高度可以直接记录最小值。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn=,inf=;

struct poi{int pos,sum;}a[maxn];

int n,ht[maxn],lisan[maxn],ans,f[maxn][maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.sum<b.sum;}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i].sum),a[i].pos=i;

    sort(a+,a++n,cmp);

    for(int i=;i<=n;i++)ht[a[i].pos]=a[i].sum,lisan[a[i].pos]=i;

    for(int i=;i<=n;i++)for(int j=;j<=n;j++)f[i][j]=inf;

    for(int i=;i<=n;i++)f[][i]=;

    for(int i=;i<=n;i++)

    {

        int mn=inf;

        for(int j=;j<=n;j++)

        {

            mn=min(mn,f[i-][j]);

            f[i][j]=min(f[i][j],mn)+abs(a[j].sum-ht[i]);

        }

    }

    ans=f[n][];

    for(int i=;i<=n;i++)ans=min(ans,f[n][i]);

    for(int i=;i<=n;i++)for(int j=;j<=n;j++)f[i][j]=inf;

    for(int i=;i<=n;i++)f[][i]=;

    lisan[]=n;

    for(int i=;i<=n;i++)

    {

        int mn=inf;

        for(int j=n;j;j--)

        {

            mn=min(mn,f[i-][j]);

            f[i][j]=min(f[i][j],mn)+abs(a[j].sum-ht[i]);

        }

    }

    for(int i=;i<=n;i++)ans=min(ans,f[n][i]);

    printf("%d\n",ans);

}

　　bzoj2442: [Usaco2011 Open]修剪草坪

　　　　DP+单调队列优化

　　　　学会了DP的巧妙姿势，如果可以选和不选求最大值可以尝试直接求不选的最小值，好写很多。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

const int maxn=;

int n,k,a[maxn],q[maxn],l,r;

ll sum,ans,f[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(k);

    for(int i=;i<=n;i++)read(a[i]),sum+=a[i];

    for(int i=;i<=n;i++)

    {

        while((i-q[l]>k+)&&(l<=r))l++;

        f[i]=f[q[l]]+a[i];

        while((l<=r)&&(f[i]<f[q[r]]))r--;

        q[++r]=i;

    }

    ans=;

    for(int i=n-k;i<=n;i++)

    ans=min(ans,f[i]);

    printf("%lld\n",sum-ans);

    return ;

}

　　bzoj1576: [Usaco2009 Jan]安全路经Travel

　　　　树链剖分或并查集。树剖以后补。

　　　　跑出最短路径树就是这题了。

树链剖分：

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#define ll long long

using namespace std;

const int maxn=,inf=;

struct gg{int dis,pos;};

priority_queue<gg>q;

bool operator<(gg a,gg b){return a.dis>b.dis;}

struct poi{int x,too,pre,sum;}e[maxn];

struct tjm{int sum,tag;}a[maxn];

struct zs{int x,y,len;}edge[maxn];

int n,m,x,y,z,flag,tot,tot2,cnt;

int last[maxn],size[maxn],fa[maxn],dep[maxn],son[maxn],w[maxn],top[maxn],dist[maxn],eg[maxn];

bool used[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].x=x;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void dfs1(int x)

{

    size[x]=;

    for(int i=last[x];i;i=e[i].pre)

    {

        int too=e[i].too;

        if(fa[too]==x&&too!=fa[x])

        {

            dep[too]=dep[x]+e[i].sum;

            dfs1(too);

            if(size[too]>size[son[x]])son[x]=too;

            size[x]+=size[too];

        }

    }

}

void dfs2(int x,int tp)

{

    w[x]=++cnt;top[x]=tp;

    if(son[x])dfs2(son[x],tp);

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=son[x]&&e[i].too!=fa[x]&&fa[e[i].too]==x)

    dfs2(e[i].too,e[i].too);

}

void pushdown(int x)

{

    if(a[x].tag==inf)return;

    int tag=a[x].tag;a[x].tag=inf;

    a[x<<].tag=min(tag,a[x<<].tag);

    a[x<<|].tag=min(tag,a[x<<|].tag);

}

void update(int x,int nl,int nr,int l,int r,int delta)

{

    if(l<=nl&&nr<=r)a[x].tag=min(a[x].tag,delta);

    else

    {

        int mid=(nl+nr)>>;

        if(l<=mid)update(x<<,nl,mid,l,r,delta);

        if(r>mid)update(x<<|,mid+,nr,l,r,delta);

    }

}

ll query(int x,int nl,int nr,int num)

{

    if(nl!=nr)pushdown(x);

    if(nl==num&&nr==num)return a[x].tag;

    else

    {

        int mid=(nl+nr)>>;

        if(nl<=num&&num<=mid)return query(x<<,nl,mid,num);

        if(mid<num&&num<=nr)return query(x<<|,mid+,nr,num);

    }

}

void work(int x,int y,int len)

{

    int f1=top[x],f2=top[y];

    while(f1!=f2)

    {

        if(dep[f1]<dep[f2])swap(x,y),swap(f1,f2);

        update(,,cnt,w[f1],w[x],len);

        x=fa[f1];f1=top[x];

    }

    if(x==y)return;

    if(dep[x]<dep[y])swap(x,y);

    update(,,cnt,w[son[y]],w[x],len);

}

void build(int x,int l,int r)

{

    a[x].tag=inf;int mid=(l+r)>>;

    if(l!=r)build(x<<,l,mid),build(x<<|,mid+,r);

}

void spfa(int x)

{

    bool v[maxn];

    for(int i=;i<=n;i++)dist[i]=inf,v[i]=;

    v[x]=;dist[x]=;q.push((gg){,x});

    while(!q.empty())

    {

        int now=q.top().pos;q.pop();

        for(int i=last[now];i;i=e[i].pre)

        {

            int too=e[i].too;

            if(dist[too]>dist[now]+e[i].sum)

            {

                dist[too]=dist[now]+e[i].sum;

                dep[too]=dep[now]+e[i].sum;

                fa[too]=now;eg[too]=i;

                if(!v[too])

                {

                    v[too]=;

                    q.push((gg){dist[too],too});

                }

            }

        }

        v[now]=;

    }

}

int main()

{

    tot=;

    read(n);read(m);

    for(int i=;i<=m;i++)

    {

        read(x);read(y);read(z);

        add(x,y,z),add(y,x,z);

    }

    spfa();

    for(int i=;i<=n;i++)used[eg[i]]=used[eg[i]^]=;

    for(int i=;i<=tot;i++)

    if(!used[i])

    {

        edge[++tot2].x=e[i].x;edge[tot2].y=e[i].too;

        edge[tot2].len=e[i].sum+dep[e[i].x]+dep[e[i].too];

    }

    dfs1();dfs2(,);build(,,n);

    for(int i=;i<=tot2;i++)

    work(edge[i].x,edge[i].y,edge[i].len);

    for(int i=;i<=n;i++)

    {

        int ans=query(,,cnt,w[i]);

        if(ans!=inf)printf("%d\n",ans-dep[i]);

        else printf("-1\n");

    }

    return ;

}

并查集：

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

const int inf=,maxn=;

struct zs{int x,too,sum,pre;}e[maxn];

struct poi{int dis,pos;};

struct tjm{int len,x,y;}edge[maxn];

priority_queue<poi>q;

bool operator<(poi a,poi b){return a.dis>b.dis;}

int n,m,x,y,z,tot,tot2;

int last[maxn],dist[maxn],h[maxn],fq[maxn],eg[maxn],fa[maxn],v[maxn];

bool used[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].x=x;e[tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void spfa(int x)

{

    bool v[maxn];

    for(int i=;i<=n;i++)dist[i]=inf,v[i]=;

    v[x]=;dist[x]=;q.push((poi){,x});

    while(!q.empty())

    {

        int now=q.top().pos;q.pop();

        for(int i=last[now];i;i=e[i].pre)

        {

            int too=e[i].too;

            if(dist[too]>dist[now]+e[i].sum)

            {

                dist[too]=dist[now]+e[i].sum;

                h[too]=h[now]+e[i].sum;

                fq[too]=now;eg[too]=i;

                if(!v[too])

                {

                    v[too]=;

                    q.push((poi){dist[too],too});

                }

            }

        }

        v[now]=;

    }

}

bool cmp(tjm a,tjm b){return a.len<b.len;}

int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}

int main()

{

    tot=;

    read(n);read(m);

    for(int i=;i<=m;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);

    spfa();

    for(int i=;i<=n;i++)used[eg[i]]=used[eg[i]^]=;

    for(int i=;i<=tot;i++)

    if(!used[i])

    {

        edge[++tot2].x=e[i].x;edge[tot2].y=e[i].too;

        edge[tot2].len=e[i].sum+h[e[i].x]+h[e[i].too];

    }

    sort(edge+,edge++tot2,cmp);

    for(int i=;i<=n;i++)fa[i]=i;

    for(int i=;i<=tot2;i++)

    {

        int x=edge[i].x,y=edge[i].y,f1=gf(x),f2=gf(y),lastx=,lasty=;

        while(f1!=f2)

        {

            if(h[f1]<h[f2])swap(x,y),swap(f1,f2),swap(lastx,lasty);

            if(!v[x])

            {

                v[x]=i;

                if(lastx)fa[lastx]=x;

            }else if(lastx)fa[lastx]=f1;

            lastx=f1;x=fq[lastx];f1=gf(x);

        }

    }

    for(int i=;i<=n;i++)

    if(v[i])printf("%d\n",edge[v[i]].len-h[i]);

    else printf("-1\n");

}

　　bzoj1782: [Usaco2010 Feb]slowdown 慢慢游

　　　　其实就是求每个节点到根的路径上比自己小的节点有几个，BIT维护一下就行了。

　　　　好像网上题解有其他写法，等等去学习一下姿势

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=;

struct poi{int too,pre;}e[maxn];

int n,m,x,y,z,tot;

int a[maxn],p[maxn],ans[maxn],last[maxn],v[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int lowbit(int x){return x&-x;}

void update(int x,int delta){for(;x<=n;x+=lowbit(x))a[x]+=delta;}

int sum(int x){int ret=;for(;x;x-=lowbit(x))ret+=a[x];return ret;}

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void dfs(int x,int fa)

{

    ans[p[x]]=sum(p[x]-);

    update(p[x],);

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa)

    dfs(e[i].too,x);

    update(p[x],-);

}

int main()

{

    read(n);

    for(int i=;i<n;i++)read(x),read(y),add(x,y),add(y,x);

    for(int i=;i<=n;i++)read(v[i]);

    for(int i=;i<=n;i++)p[v[i]]=i;

    dfs(,);

    for(int i=;i<=n;i++)printf("%d\n",ans[i]);

    return ;

}

　　bzoj1571: [Usaco2009 Open]滑雪课Ski

　　　　挺显然的一个DP

　　　　f[i][j]表示时间i，能力值为j最多滑几次

　　　　预处理出mind[i]表示能力值为i滑一次雪的最短时间，ke[i][j]表示时间i结束，能力值达到j的课程开始的时间。

　　　　f[i][j]=max(f[i-1][j],f[i-mind[j]][j]+1,f[ke[i][j]][k]]);

　　　　最后一个可以开个数组g[i][j]记录max(f[i][1~j])来优化。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=;

int n,x,y,z,tot,ans,t,s,m[maxn],l[maxn],a[maxn],c[maxn],d[maxn];

int f[maxn][],g[maxn][],mind[maxn],ke[maxn][];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(t);read(s);read(n);

    for(int i=;i<=s;i++)

    read(m[i]),read(l[i]),read(a[i]),ke[m[i]+l[i]][a[i]]=m[i];

    for(int i=;i<=n;i++)read(c[i]),read(d[i]);

    for(int i=;i<=;i++)mind[i]=;

    for(int i=;i<=;i++)

    for(int j=;j<=n;j++)

    if(c[j]<=i)mind[i]=min(mind[i],d[j]);

    memset(f,-,sizeof(f));

    memset(g,-,sizeof(g));

    f[][]=g[][]=;

    for(int i=;i<=t;i++)

    {

        for(int j=;j<=;j++)

        {

            f[i][j]=f[i-][j];

            if(i>=mind[j])f[i][j]=max(f[i][j],f[i-mind[j]][j]+);

            f[i][j]=max(f[i][j],g[ke[i][j]][j]);

            g[i][j]=max(g[i][j-],f[i][j]);

        }

    }

    int ans=;

    for(int i=;i<=;i++)ans=max(ans,f[t][i]);

    printf("%d\n",ans);

    return ;

}

　　bzoj1715: [Usaco2006 Dec]Wormholes 虫洞

　　　　spfa判负环。

　　　　傻了，输出NO没过行WA了好几次，输样例的时候看不出来。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

struct zs{int dis,pre,too;}e[];

int i,now,n,m,front,rear,x,y,z,tot,T,w;

int h[],last[],dis[],ru[];

bool v[];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int spfa(int x)

{

    memset(dis,,(n+)<<);memset(v,,sizeof(v));memset(ru,,sizeof(ru));

    dis[x]=;front=;rear=;h[]=x;v[x]=;

    while(front!=rear)

    {

        now=h[++front];if(front==)front=-;

        for(int i=last[now],to=e[i].too;i;i=e[i].pre,to=e[i].too)

        if(dis[to]>dis[now]+e[i].dis)

        {

            dis[to]=dis[now]+e[i].dis;

            if(!v[to])

            {

                h[++rear]=to;if(rear==)rear=-;

                v[to]=;ru[to]++;

                if(ru[to]>)return ;

            }

        }

        v[now]=;

    }

    return ;

}

void add(int x,int y,int z)

{

    e[++tot].too=y;e[tot].dis=z;e[tot].pre=last[x];last[x]=tot;

}

int main()

{

    read(T);

    while(T--)

    {

        tot=;memset(last,,sizeof(last));

        read(n);read(m);read(w);

        for(int i=;i<=m;i++)

        read(x),read(y),read(z),add(x,y,z),add(y,x,z);

        for(int i=;i<=w;i++)

        read(x),read(y),read(z),add(x,y,-z);

        if(spfa())printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

　　bzoj1596: [Usaco2008 Jan]电话网络

　　　　树形DP

　　　　dp[i][0]为i被覆盖，i不建塔

　　　　dp[i][1]为i建塔

　　　　dp[i][2]为i不被覆盖，i不建塔

　　　　一开始inf开太大GG了呜呜

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,inf=;

struct poi{int too,pre;}e[maxn];

int n,m,x,y,z,tot;

int dp[maxn][],last[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void dfs(int x,int fa)

{

    dp[x][]=inf;dp[x][]=;dp[x][]=;

    int sum=;

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa)

    {

        dfs(e[i].too,x);

        dp[x][]+=min(dp[e[i].too][],min(dp[e[i].too][],dp[e[i].too][]));

        dp[x][]+=min(dp[e[i].too][],dp[e[i].too][]);

        sum+=min(dp[e[i].too][],dp[e[i].too][]);

    }

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa)

    dp[x][]=min(dp[x][],dp[e[i].too][]-min(dp[e[i].too][],dp[e[i].too][])+sum);

}

int main()

{

    read(n);

    for(int i=;i<n;i++)

    read(x),read(y),add(x,y),add(y,x);

    dfs(,);

    printf("%d",min(dp[][],dp[][]));

    return ;

}

　　bzoj1770: [Usaco2009 Nov]lights 燈

　　　　meet in the middle

　　　　直接用Claris题解啦！

　　　　好像还能写高斯消元，那明天就学高斯消元吧嘿嘿嘿 UPD：不学了好难啊

　　　　又又又又又又叕叕叕叕叕叕交成老代码WA了好多次啊淦

　　　　好激心，对着能AC的代码找了大概有1h+找不出错

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=;

map<ll,int>cnt;

int n,m,x,y,half,ans;

ll f[],state;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void dfs1(int x,ll st,int t)

{

    if(x==half)

    {

        int &cntt=cnt[st];

        if(!cntt)cntt=t;

        else cntt=min(cntt,t);

        return;

    }

    dfs1(x+,st,t);dfs1(x+,st^f[x],t+);

}

void dfs2(int x,ll st,int t)

{

    if(x==(n-half))

    {

        int &cntt=cnt[state^st];

        if(cntt)ans=min(ans,cntt+t-);

        return;

    }

    dfs2(x+,st,t);dfs2(x+,st^f[x+half],t+);

}

int main()

{

    read(n);read(m);

    half=n/;state=(1ll<<n)-;

    for(int i=;i<=m;i++)

    {

        read(x);read(y);

        x--;y--;

        f[x]|=1ll<<y;

        f[y]|=1ll<<x;

    }

    for(int i=;i<n;i++)f[i]|=1ll<<i;

    ans=inf;

    dfs1(,,);dfs2(,,);

    printf("%d\n",ans);

    return ;

}

　　bzoj1691: [Usaco2007 Dec]挑剔的美食家

　　　　贪心，用splay维护。把牛和牧草都按新鲜程度从大到小排序，枚举牛，把新鲜程度大于牛要求的都加进splay，找到牛要求的价格-1的后继，加入答案。

　　　　感觉splay的删除操作写的还是有点丑，下次再改改。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define which(x) (son[fa[x]][1]==x)

#define ll long long

using namespace std;

const int maxn=;

struct poi{int cost,fresh;}a[maxn],b[maxn];

const int extar[]={,-};

int fa[maxn],cnt[maxn],son[maxn][],val[maxn],data[maxn];

int root,x,y,n,m,j,tot,xiugai;

ll ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.fresh>b.fresh;}

void rotate(int x)

{

    int f=fa[x];

    bool k=which(x);

    son[f][k]=son[x][!k];son[x][!k]=f;son[fa[f]][which(f)]=x;

    if(son[f][k])fa[son[f][k]]=f;fa[x]=fa[f];fa[f]=x;

    cnt[x]=cnt[f];

    cnt[f]=cnt[son[f][]]+cnt[son[f][]]+val[f];

}

void splay(int x,int g)

{

    while(fa[x]!=g)

    {

        int f=fa[x];

        if(fa[f]==g)

        {

            rotate(x);

            break;

        }

        if(which(x)^which(f))rotate(x);

        else rotate(f);

        rotate(x);

    }

    if(!g)root=x;

}

int search(int x,int y)

{

    if(data[x]>y&&son[x][])return search(son[x][],y);

    if(data[x]<y&&son[x][])return search(son[x][],y);

    return x;

}

int ext(int x,int w)

{

    int k=search(x,extar[w]);

    splay(k,);

    return data[k];

}

int succ(int x)

{

    int k=search(root,x);

    splay(k,);

    if(data[k]>x)return data[k];

    return ext(son[k][],);

}

void insert(int &x,int w,int f)

{

    if(!x)

    {

        x=++tot;

        cnt[x]=val[x]=;

        data[x]=w;

        fa[x]=f;

        xiugai=tot;

        return;

    }

    if(data[x]==w)val[x]++,xiugai=x;

    if(data[x]<w)insert(son[x][],w,x);

    if(data[x]>w)insert(son[x][],w,x);

    cnt[x]++;

}

void del(int w)

{

    int k=search(root,w);

    splay(k,);

    if(data[k]==w)

    {

        if(val[k]>)val[k]--,cnt[k]--;

        else

        if(!son[k][])

        {

            root=son[k][];

            fa[root]=fa[k]=son[k][]=cnt[k]=val[k]=data[k]=;

        }

        else

        {

            fa[son[k][]]=;ext(son[k][],);

            son[root][]=son[k][];

            if(son[k][])fa[son[k][]]=root;

            cnt[root]+=cnt[son[k][]];

            fa[k]=son[k][]=son[k][]=data[k]=val[k]=cnt[k]=;

        }

    }

}

int main()

{

    read(n);read(m);

    if(n>m)

    {

        printf("-1\n");

        return ;

    }

    for(int i=;i<=n;i++)read(a[i].cost),read(a[i].fresh);

    for(int i=;i<=m;i++)read(b[i].cost),read(b[i].fresh);

    sort(a+,a++n,cmp);sort(b+,b++m,cmp);

    j=;

    for(int i=;i<=n;i++)

    {

        for(;b[j].fresh>=a[i].fresh&&j<=m;j++)

        {

            insert(root,b[j].cost,);

            splay(xiugai,);

        }

        int now=succ(a[i].cost-);

        if(now)ans+=now;

        else

        {

            printf("-1\n");

            return ;

        }

        del(now);

    }

    printf("%lld\n",ans);

    return ;

}

　　bzoj1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富

　　　　经典DP

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=;

int n,m,x,y,z,tot;

int f[maxn][maxn],map[maxn][maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    read(map[i][j]);

    memset(f,-0x7f,sizeof(f));

    f[][]=;

    for(int j=;j<=m;j++)

    for(int i=;i<=n;i++)

    f[i][j]=max(f[i+][j-],max(f[i][j-],f[i-][j-]))+map[i][j];

    printf("%d\n",f[n][m]);

    return ;

}

　　bzoj1593: [Usaco2008 Feb]Hotel 旅馆

　　　　线段树维护左边，中间，最大值。

　　　　查询时按左中右的顺序查就可以保证最左边了

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int l,r,m,tag;}a[maxn*];

int n,m,x,y,z,tot;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void build(int x,int l,int r)

{

    a[x].l=a[x].r=a[x].m=r-l+;

    if(l==r)return;

    int mid=(l+r)>>;

    build(x<<,l,mid);build(x<<|,mid+,r);

}

void pushup(int x,int l,int r)

{

    int mid=(l+r)>>;

    a[x].l=a[x<<].l;a[x].r=a[x<<|].r;

    if(a[x<<].l==(mid-l+))a[x].l+=a[x<<|].l;

    if(a[x<<|].r==(r-mid))a[x].r+=a[x<<].r;

    a[x].m=max(a[x<<].r+a[x<<|].l,max(a[x<<].m,a[x<<|].m));

}

void pushdown(int x,int l,int r)

{

    if(a[x].tag==)

    {

        int mid=(l+r)>>;

        a[x<<].l=a[x<<].r=a[x<<].m=mid-l+;a[x<<].tag=;

        a[x<<|].l=a[x<<|].r=a[x<<|].m=r-mid;a[x<<|].tag=;

    }

    if(a[x].tag==)

    {

        a[x<<].l=a[x<<].r=a[x<<].m=;a[x<<].tag=;

        a[x<<|].l=a[x<<|].r=a[x<<|].m=;a[x<<|].tag=;

    }

    a[x].tag=;

}

void change(int x,int l,int r,int cl,int cr,int delta)

{

    if(cl<=l&&r<=cr)

    {

        a[x].tag=delta;

        if(delta==)a[x].l=a[x].r=a[x].m=r-l+;

        else a[x].l=a[x].r=a[x].m=;

    }

    else

    {

        pushdown(x,l,r);

        int mid=(l+r)>>;

        if(cl<=mid)change(x<<,l,mid,cl,cr,delta);

        if(cr>mid)change(x<<|,mid+,r,cl,cr,delta);

        pushup(x,l,r);

    }

}

int find(int x,int l,int r,int len)

{

    pushdown(x,l,r);

    if(l==r)return l;

    int mid=(l+r)>>;

    if(a[x<<].m>=len)return find(x<<,l,mid,len);

    if(a[x<<].r+a[x<<|].l>=len)return mid-a[x<<].r+;

    return find(x<<|,mid+,r,len);

}

int main()

{

    read(n);read(m);

    build(,,n);

    for(int i=;i<=m;i++)

    {

        read(x);

        if(x==)

        {

            read(y);

            if(a[x].m>=y)

            {

                int l=find(,,n,y);

                printf("%d\n",l);

                change(,,n,l,l+y-,);

            }

            else printf("0\n");

        }

        if(x==)

        {

            read(y);read(z);

            change(,,n,y,y+z-,);

        }

    }

    return ;

}

　　bzoj1697: [Usaco2007 Feb]Cow Sorting牛排序

　　　　置换群

　　　　两种方法中选更优的一种：（循环节总权值：sum，循环节大小：len，循环节中最小值：minai，数组中最小值：mina）

　　　　　　①每个循环节中最小值将其他移回原位。代价：sum+（len-2）*minai

　　　　　　②整个数组的最小值移进循环节帮循环节最小值将其他移回原位。代价：sum+(len+1)*mina+minai

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<vector>

#define ll long long

using namespace std;

const int maxn=;

struct poi{int sum,next;}a[maxn];

int n,m,x,y,z,tot,mina,minai,j,k,ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.sum<b.sum;}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i].sum),a[i].next=i;

    sort(a+,a++n,cmp);

    mina=a[].sum;

    for(int i=;i<=n;i++)

    if(a[i].next!=-)

    {

        j=a[i].next;minai=a[i].sum;k=;

        a[i].next=-;

        while(j!=i)

        {

            k++;

            ans+=a[j].sum;

            int t=a[j].next;

            a[j].next=-;

            j=t;

        }

        ans+=min((k-)*minai,*minai+(k+)*mina);

    }

    printf("%d\n",ans);

    return ;

}

　　bzoj1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

　　　　曼哈顿距离|x1-y1|+|x2-y2|有四种情况

　　　　(x1-y1-(x2-y2)) (x1-y1-(y2-x2)) (y1-x1-(x2-y2)) (y1-x1-(y2-x2))

　　　　那我们陵X=x+y，Y=x-y，那两个点的曼哈顿距离为max(|X1-Y1|,|Y1-Y2|)，也就是切比雪夫距离。

　　　　按X排序，保证队头队尾X的差<=c，加入新元素时用set找到（用splay处理重复元素有点麻烦，学习了一波set）前驱后继，如果前驱或后继的y和新加入元素的y差值<=c，就用并查集把新元素和前驱或后继连起来。

　　　　set用法见代码。find找到set中元素，lowerbound找到第一个大于等于它的元素，其实是不一样的，find找不到会返回end()。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<map>

#include<set>

#define ll long long

using namespace std;

const int maxn=;

const ll inf=1e10;

int n,m,x,y,z,tot,ans,ans2,c,now;

int fa[maxn],cnt[maxn];

struct poi{ll x,y;int pos;}a[maxn],hj,qq;

multiset<poi>b;

set<poi>::iterator it;

bool operator<(poi a,poi b){return a.y<b.y;}

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}

bool cmp(poi a,poi b){return a.x<b.x;}

void link(int x,int y)

{

    x=gf(x);y=gf(y);

    if(x!=y)

    {

        fa[x]=y;

        ans--;

    }

}

int main()

{

    read(n);read(c);

    for(int i=;i<=n;i++)fa[i]=i;

    for(int i=;i<=n;i++)

    {

        read(x);read(y);ans=n;

        a[i].x=x+y;a[i].y=x-y;a[i].pos=i;

    }

    sort(a+,a++n,cmp);

    b.insert((poi){,inf,});b.insert((poi){,-inf,});

    now=;b.insert(a[]);

    for(int i=;i<=n;i++)

    {

        while(a[i].x-a[now].x>c)b.erase(b.find(a[now++]));

        it=b.lower_bound(a[i]);

        hj=*it;qq=*--it;

        if(hj.y-a[i].y<=c)link(hj.pos,a[i].pos);

        if(a[i].y-qq.y<=c)link(qq.pos,a[i].pos);

        b.insert(a[i]);

    }

    for(int i=;i<=n;i++)cnt[gf(i)]++;

    for(int i=;i<=n;i++)ans2=max(ans2,cnt[i]);

    printf("%d %d\n",ans,ans2);

    return ;

}

　　bzoj1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

　　　　基环树找环+DP

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,j,top;

int f[maxn],v[maxn],next[maxn],st[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(next[i]);

    for(int i=;i<=n;i++)

    if(!v[i])

    {

        int top=;

        for(j=i;!v[j];j=next[j])st[++top]=j,v[j]=i;

        if(v[j]==i)

        {

            int cnt=;

            for(;st[top-cnt+]!=j;cnt++);

            for(int k=;k<=cnt;k++)f[st[top-k+]]=cnt;

            top-=cnt;

        }

        int cnt=;

        while(top)f[st[top--]]=f[j]+(++cnt);

    }

    for(int i=;i<=n;i++)printf("%d\n",f[i]);

    return ;

}

　　bzoj1574: [Usaco2009 Jan]地震损坏Damage

　　　　一开始看成最少损坏几个了，想了好久QAQ

　　　　最少几个不能去显然把不能去的几个周围一圈全部搞坏就行了，然后再dfs一遍找出一共几个不能回到1点就行了

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre;}e[maxn];

int n,m,x,y,z,c,ans,tot;

int map[maxn],v[maxn],last[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void dfs(int x)

{

    ans--;v[x]=;

    for(int i=last[x];i;i=e[i].pre)

    if(!v[e[i].too])dfs(e[i].too);

}

int main()

{

    read(n);read(m);read(c);ans=n;

    for(int i=;i<=m;i++)read(x),read(y),add(x,y),add(y,x);

    for(int i=;i<=c;i++)

    {

        read(x);

        v[x]=;

        for(int j=last[x];j;j=e[j].pre)

        v[e[j].too]=;

    }

    dfs();

    printf("%d\n",ans);

    return ;

}

　　bzoj1707: [Usaco2007 Nov]tanning分配防晒霜

　　　　一开始只会网络流，感觉会TLE，不会写QAQ

　　　　直接拿@willinglive题解啦

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int x,y;}a[maxn];

int n,m,x,y,z,tot,ans,spf[maxn],num[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.y<b.y;}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)read(a[i].x),read(a[i].y);

    sort(a+,a++n,cmp);

    for(int i=;i<=m;i++)read(spf[i]),read(num[i]);

    spf[]=inf;

    for(int i=;i<=n;i++)

    {

        int mnj=;

        for(int j=;j<=m;j++)

        if(num[j])if(a[i].x<=spf[j]&&spf[j]<=a[i].y)if(spf[mnj]>spf[j])mnj=j;

        if(mnj)ans++,num[mnj]--;

    }

    printf("%d\n",ans);

    return ;

}

　　bzoj1709: [Usaco2007 Oct]Super Paintball超级弹珠

　　　　直接记录。。。左上到右下是x-y+n，右上到左下是x+y-1，注意可能站在对手的位置射....

　　　　没删调试输出交上去WA了一次QAQ

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,k,x,y,z,tot,ans;

int row[maxn],col[maxn],lt[maxn],rt[maxn],map[maxn][maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(k);

    for(int i=;i<=k;i++)

    {

        read(x);read(y);map[x][y]++;

        row[x]++;col[y]++;lt[x-y+n]++;rt[x+y-]++;

    }

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

    if(row[i]+col[j]+lt[i-j+n]+rt[i+j-]-*map[i][j]==k)ans++;

    printf("%d\n",ans);

    return ;

}

　　bzoj1706: [usaco2007 Nov]relays 奶牛接力跑

　　　　之前写过题解

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=;

struct poi{ll mtx[maxn][maxn];}f,g;

ll n,m,s,t,tot,x,y,z;

int v[];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void floyd(poi &a,poi b)

{

    poi c;memset(c.mtx,0x3f,sizeof(c.mtx));

    for(int k=;k<=tot;k++)

    for(int i=;i<=tot;i++)

    for(int j=;j<=tot;j++)

    c.mtx[i][j]=min(c.mtx[i][j],a.mtx[i][k]+b.mtx[k][j]);

    memcpy(a.mtx,c.mtx,sizeof(c.mtx));

}

void ksm(int n)

{

    while(n)

    {

        if(n&)floyd(g,f);

        floyd(f,f);

        n>>=;

    }

}

int main()

{

    read(n);read(m);read(s);read(t);

    memset(f.mtx,0x3f,sizeof(f.mtx));

    for(int i=;i<=m;i++)

    {

        read(z);read(x);read(y);

        if(!v[x])v[x]=++tot;if(!v[y])v[y]=++tot;

        f.mtx[v[x]][v[y]]=min(f.mtx[v[x]][v[y]],z);

        f.mtx[v[y]][v[x]]=min(f.mtx[v[y]][v[x]],z);

    }

    memset(g.mtx,0x3f,sizeof(g.mtx));

    for(int i=;i<=tot;i++)g.mtx[i][i]=;

    ksm(n);

    printf("%lld\n",g.mtx[v[s]][v[t]]);

    return ;

}

　　bzoj1753: [Usaco2005 qua]Who's in the Middle

　　　　...直接排序

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot;

int a[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i]);

    sort(a+,a++n);

    printf("%d\n",a[(n+)>>]);

    return ;

}

　　bzoj1584: [Usaco2009 Mar]Cleaning Up 打扫卫生

　　　　有趣的DP...不会写（躺。感觉自己思维每次只能碰到正解的一部分，却达不到最关键的点，只想到了不同数个数的平方一定要小于长度，却没有根据这个推出不同数个数不能超过sqrt(n)，虽然是显而易见的...（其实感觉跟不确定这题到底是不是DP有关，因为看数据范围就觉得像根号，但是从没见过带根号的DP...

　　　　f[i]=min(f[b[j]]+j*j)(1≤j*j≤n)

　　　　b[j]表示b[j]+1~i的出现次数为j。维护的话记录下每个a[i]最晚出现次数pre[a[i]]，如果pre[a[i]]并没有出现在b[j]+1~i也就是pre[a[i]]<=b[j]的话，这一段的不同数个数就要增加（cnt[j]++），如果cnt[j]>j的话就必须从b[j]+1一直向右删，删到第一个在这一段里只出现一次的数，这可以用pre来判断。

　　　　总的时间复杂度O（nsqrt(n)）

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,k;

int a[maxn],b[maxn],pre[maxn],cnt[maxn];

ll f[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)read(a[i]);

    memset(pre,-,sizeof(pre));

    memset(f,0x7f,sizeof(f));

    f[]=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j*j<=n;j++)

        if(pre[a[i]]<=b[j])

        {

            cnt[j]++;

            if(cnt[j]>j)

            {

                for(k=b[j]+;k<pre[a[k]];k++);

                b[j]=k;cnt[j]--;

            }

        }

        for(int j=;j*j<=n;j++)

        f[i]=min(f[i],f[b[j]]+j*j);

        pre[a[i]]=i;

    }

    printf("%lld\n",f[n]);

    return ;

}

　　bzoj1754: [Usaco2005 qua]Bull Math

　　　　高精度乘法，WA了5次，调了1h，身败名裂QAQ

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int lena,lenb,lenc;

int a[maxn],b[maxn],c[maxn];

char s1[],s2[];

int main()

{

    scanf("%s%s",s1,s2);

    lena=strlen(s1);lenb=strlen(s2);

    for(int i=;i<lena;i++)a[lena-i]=s1[i]-'';

    for(int i=;i<lenb;i++)b[lenb-i]=s2[i]-'';

    for(int i=;i<=lena;i++)

    {

        int x=;

        for(int j=;j<=lenb;j++)

        {

            x=a[i]*b[j]+x+c[i+j-];

            c[i+j-]=x%;

            x/=;

        }

        c[i+lenb]=x;

    }

    lenc=lena+lenb;

    while((!c[lenc])&&lenc>)lenc--;

    for(int i=lenc;i;i--)printf("%d",c[i]);

    printf("\n");

    return ;

}

　　bzoj1828: [Usaco2010 Mar]balloc 农场分配

　　　　贪心，右端点第一关键字升序，左端点第二关键字降序，一个一个能取就取，正确性自己脑洞一下就知道了

　　　　感觉现在线段树挺熟悉的了，10min敲完 1A

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int min,delta;}a[maxn*];

struct tjm{int x,y;}v[maxn];

int n,m,x,y,z,tot,mn,ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(tjm a,tjm b){return a.y==b.y?a.x>b.x:a.y<b.y;}

void pushup(int x,int l,int r){if(l!=r)a[x].min=min(a[x<<].min,a[x<<|].min);}

void pushdown(int x,int l,int r)

{

    if(l==r)return;

    a[x<<].delta+=a[x].delta;a[x<<|].delta+=a[x].delta;

    a[x<<].min+=a[x].delta;a[x<<|].min+=a[x].delta;

    a[x].delta=;

}

void build(int x,int l,int r)

{

    if(l==r)read(a[x].min);

    else

    {

        int mid=(l+r)>>;

        build(x<<,l,mid);

        build(x<<|,mid+,r);

        pushup(x,l,r);

    }

}

void update(int x,int l,int r,int wl,int wr,int delta)

{

    if(wl<=l&&r<=wr)a[x].delta+=delta,a[x].min+=delta;

    else

    {

        pushdown(x,l,r);

        int mid=(l+r)>>;

        if(wl<=mid)update(x<<,l,mid,wl,wr,delta);

        if(wr>mid)update(x<<|,mid+,r,wl,wr,delta);

        pushup(x,l,r);

    }

}

int query(int x,int l,int r,int wl,int wr)

{

    if(wl<=l&&r<=wr)return a[x].min;

    else

    {

        pushdown(x,l,r);

        int mid=(l+r)>>,ans=inf;

        if(wl<=mid)ans=min(ans,query(x<<,l,mid,wl,wr));

        if(wr>mid)ans=min(ans,query(x<<|,mid+,r,wl,wr));

        return ans;

    }

}

int main()

{

    read(n);read(m);

    build(,,n);

    for(int i=;i<=m;i++)read(v[i].x),read(v[i].y);

    sort(v+,v++m,cmp);

    for(int i=;i<=m;i++)

    {

        mn=query(,,n,v[i].x,v[i].y);

        if(mn)ans++,update(,,n,v[i].x,v[i].y,-);

    }

    printf("%d\n",ans);

    return ;

}

　　bzoj1710: [Usaco2007 Open]Cheappal 廉价回文

　　　　添加和删除一样，然后就是经典DP了。f[l][r]表示把[l,r]改为回文的最小代价，则有：

　　　　f[l][r]=min(f[l+1][r]+cost[s[l]],f[l][r-1]+cost[s[r]];

　　　　if(s[l]==s[r])f[l][r]=min(f[l][r],f[l+1][r-1]);

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot;

int f[maxn][maxn],cost[maxn];

char s[maxn],ch[];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(m);

    scanf("%s",s+);

    for(int i=;i<=n;i++)

    {

        scanf("%s",ch);read(x);read(y);

        cost[(int)ch[]]=min(x,y);

    }

    for(int i=;i<m;i++)

    for(int l=;l<=m-i;l++)

    {

        f[l][l+i]=min(f[l+][l+i]+cost[(int)s[l]],f[l][l+i-]+cost[(int)s[l+i]]);

        if(s[l]==s[l+i])f[l][l+i]=min(f[l][l+i],f[l+][l+i-]);

    }

    printf("%d\n",f[][m]);

    return ;

}

　　bzoj1598: [Usaco2008 Mar]牛跑步

　　　　K短路，启发式搜索A*模板。

　　　　f(n)=g(n)+h(n)，g为n到起点实际距离，h为n到终点最短距离，所以先跑一遍最短路，从n点开始A*，1进队k次后得到k个答案。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<queue>

using namespace std;

const int maxn=,inf=1e9;

struct poi{int dis,pos;};

struct zs{int too,sum,pre;}e[maxn],e2[maxn];

priority_queue<poi>q;

bool operator<(poi a,poi b){return a.dis>b.dis;}

int n,m,k,x,y,z,tot;

int last[maxn],last2[maxn],dist[maxn],tim[maxn],ans[maxn];

bool v[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add1(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void add2(int x,int y,int z){e2[++tot].too=y;e2[tot].sum=z;e2[tot].pre=last2[x];last2[x]=tot;}

void spfa()

{

    for(int i=;i<=n;i++)dist[i]=inf;

    dist[]=;q.push((poi){,});

    while(!q.empty())

    {

        int now=q.top().pos;q.pop();

        for(int i=last[now],too=e[i].too;i;i=e[i].pre,too=e[i].too)

        if(dist[too]>dist[now]+e[i].sum)

        {

            dist[too]=dist[now]+e[i].sum;

            if(!v[too])

            {

                v[too]=;

                q.push((poi){dist[too],too});

            }

        }

        v[now]=;

    }

}

void astar()

{

    q.push((poi){dist[n],n});

    while(!q.empty())

    {

        poi top=q.top();int now=top.pos,dis=top.dis;q.pop();

        tim[now]++;

        if(now==)ans[tim[now]]=dis;

        if(tim[now]<=k)

        for(int i=last2[now],too=e2[i].too;i;i=e2[i].pre,too=e2[i].too)

        q.push((poi){dis-dist[now]+e2[i].sum+dist[too],too});

    }

}

int main()

{

    read(n);read(m);read(k);

    for(int i=;i<=m;i++)

    {

        read(x);read(y);read(z);

        add1(y,x,z);add2(x,y,z);

    }

    spfa();

    astar();

    for(int i=;i<=k;i++)

    if(ans[i])printf("%d\n",ans[i]);

    else printf("-1\n");

    return ;

}

　　bzoj2060: [Usaco2010 Nov]Visiting Cows 拜访奶牛

　　　　树形DP f[x][1]表示x选 f[x][0]表示x不选

　　　　f[x][1]=sigma(f[son[]][0]);

　　　　f[x][0]=max(sigma(max(f[son[]][0],f[son[]][1]))-max(f[son[i]][0],f[son[i]][1])+f[son[i]][1]);

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre;}e[maxn];

int n,m,x,y,z,tot;

int f[maxn][],last[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void dp(int x,int fa)

{

    f[x][]=;int sum=;

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa)

    {

        dp(e[i].too,x);

        f[x][]+=f[e[i].too][];

        sum+=max(f[e[i].too][],f[e[i].too][]);

    }

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa)f[x][]=max(f[x][],sum-max(f[e[i].too][],f[e[i].too][])+f[e[i].too][]);

}

int main()

{

    read(n);

    for(int i=;i<n;i++)read(x),read(y),add(x,y),add(y,x);

    dp(,);

    printf("%d\n",max(f[][],f[][]));

    return ;

}

　　bzoj1741: [Usaco2005 nov]Asteroids 穿越小行星群

　　　　对于一个小行星(x,y)，如果x不打y一定要打，于是x连y做二分图最大匹配就行了，或者可以理解成最小割

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

using namespace std;

struct poi{int too,pre;}e[];

int n,m,x,y,t,tot,ans,num,lin[],last[],v[];

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool dfs(int x)

{

    for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)

    if(v[too]!=t)

    {

        v[too]=t;

        if((!lin[too])||dfs(lin[too]))

        {

            lin[too]=x;

            return ;

        }

    }

    return ;

}

int main()

{

    read(n);read(m);

    for(int i=;i<=m;i++)read(x),read(y),add(x,y);

    for(int i=;i<=n;i++)

    {

        ++t;

        if(dfs(i))ans++;

    }

    printf("%d\n",ans);

}

　　bzoj1703: [Usaco2007 Mar]Ranking the Cows 奶牛排名

　　　　传递闭包+bitset优化

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<bitset>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,ans;

bitset<maxn>a[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(m);

    for(int i=;i<=m;i++)read(x),read(y),a[x][y]=;

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

    if(a[j][i])a[j]|=a[i];

    ans=;

    for(int i=;i<=n;i++)

    for(int j=i+;j<=n;j++)

    if(!(a[i][j]||a[j][i]))ans++;

    printf("%d\n",ans);

    return ;

}

　　bzoj1578: [Usaco2009 Feb]Stock Market 股票市场

　　　　没见过的DP，居然可以用前一天的DP值来当容量（躺（智商太低想不到系列。

　　　　显然某一天卖股票只可能卖一种，也就是之前肯定只买一种来卖，这个自己yy一下就知道了。

　　　　f[i]表示第i天的最大收益，然后用前一天的DP值来做完全背包就行了。至于为什么用前一天的，因为用之前的和用前一天的其实是一样的，相当于之前买的在前一天卖了再买。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,d;

int f[],gp[][],g[][];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(d);read(m);

    for(int i=;i<=n;i++)

    for(int j=;j<=d;j++)

    read(gp[j][i]);

    f[]=m;

    for(int i=;i<=d;i++)

    {

        for(int j=;j<=n;j++)

        for(int k=gp[i-][j];k<=f[i-];k++)

        g[i][k]=max(g[i][k-gp[i-][j]]+gp[i][j]-gp[i-][j],g[i][k]);

        f[i]=g[i][f[i-]]+f[i-];

    }

    printf("%d\n",f[d]);

    return ;

}

　　bzoj1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列

　　　　转2进制后前缀和，前缀和的每位都减去第一位，如果有两个前缀和 i 和 j 相同的话，那么i+1~j这一段的k种颜色出现次数一样多。哈希之后用map，我的写法怎么这么奇葩233

　　　　很好证明，∵ b1-a1==b2-a2==b3-a3 ∴ b1-b1-(a1-a1)==b2-b1-(a2-a1)==b3-b1-(a3-a1)==0

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<map>

#define ull unsigned long long

using namespace std;

const int maxn=,inf=1e9;

map<ull,int>a;

int n,k,now,ans,x;

int digit[maxn][];

void read(int &k)

{

    k=;int f=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int find(int pos)

{

    ull sum=;

    for(int i=;i<=k;i++)sum=sum*+1ull*digit[pos][i];

    if(!a[sum]&&sum)a[sum]=pos;

    return a[sum];

}

int main()

{

    read(n);read(k);

    for(int i=;i<=n;i++)

    {

        read(x);

        int now=;

        for(;x;x>>=)digit[i][++now]=x&;

        for(int j=;j<=k;j++)digit[i][j]+=digit[i-][j];

    }

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=k;j++)digit[i][j]-=digit[i][];

        ans=max(ans,i-find(i));

    }

    printf("%d\n",ans);

}

　　bzoj1734: [Usaco2005 feb]Aggressive cows 愤怒的牛

　　　　二分最小值最大化

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,c,x,y,z,tot,l,r,mid;

int a[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool check()

{

    int cnt=,pre=-inf;

    for(int i=;i<=n;i++)

    {

        if(a[i]-pre>=mid)cnt++,pre=a[i];

        if(cnt==c)return ;

    }

    return ;

}

int main()

{

    read(n);read(c);

    for(int i=;i<=n;i++)read(a[i]);

    sort(a+,a++n);

    l=;r=1e9;

    while(l<r)

    {

        mid=(l+r+)>>;

        if(check())l=mid;

        else r=mid-;

    }

    printf("%d\n",l);

    return ;

}

　　bzoj1585: [Usaco2009 Mar]Earthquake Damage 2 地震伤害

　　　　最小割。把每个点拆成俩，连起来容量为1，有report的点容量就为inf，原图边按二分图加进去，容量inf。S连1，report的点连T，跑最大流。

　　　　1是不能割的，所以拆点后容量也是inf，查了好久TAT

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

using namespace std;

const int inf=,maxn=;

struct poi{int too,pre,cf;}e[];

int n,m,tot,ans,x,y,z,front,rear,sum,p;

int h[maxn],v[maxn],last[maxn],dis[maxn],cur[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z)

{

    e[++tot].too=y;e[tot].cf=z;e[tot].pre=last[x];last[x]=tot;

    e[++tot].too=x;e[tot].pre=last[y];last[y]=tot;

}

bool bfs()

{

    for(int i=;i<=sum;i++)v[i]=,dis[i]=-;

    dis[]=;v[]=;h[]=;front=;rear=;

    while(front!=rear)

    {

        int now=h[++front];if(front==maxn)front=-;

        for(int i=last[now];i;i=e[i].pre)

        {

            int too=e[i].too;

            if((!v[too])&&e[i].cf)

            {

                dis[too]=dis[now]+;if(too==sum)return ;

                v[too]=;h[++rear]=too;if(rear==maxn)rear=-;

            }

        }

    }

    return ;

}

int dfs(int x,int f)

{

    int flow=,tmp;

    if(x==sum)return f;

    for(int &i=cur[x];i;i=e[i].pre)

    {

        int too=e[i].too;

        if(dis[too]==dis[x]+&&e[i].cf)

        {

            tmp=dfs(too,min(f-flow,e[i].cf));

            e[i].cf-=tmp;e[i^].cf+=tmp;flow+=tmp;

            if(f==flow)return f;

        }

    }

    return flow;

}

void dinic()

{

    while(bfs())

    {

        for(int i=;i<=sum;i++)cur[i]=last[i];

        ans+=dfs(,inf);

    }

}

int main()

{

    tot=;

    read(p);read(m);read(n);sum=p*+;

    add(,,inf);add(,+p,inf);

    for(int i=;i<=p;i++)add(i,i+p,);

    for(int i=;i<=m;i++)

    read(x),read(y),add(x+p,y,inf),add(y+p,x,inf);

    for(int i=;i<=n;i++)

    read(x),add(x,x+p,inf),add(x+p,sum,inf);

    dinic();

    printf("%d\n",ans);

    return ;

}

----------------------------------------BZOJ 100题纪念----------------------------------------　　

　　bzoj1704: [Usaco2007 Mar]Face The Right Way 自动转身机

　　　　O（n）枚举k，O（n）扫一遍判断。从左到右，遇见反着的就转过来，前面的保证已经转好了就不要再动了，一直往后扫就行。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,ansk,ans,tim,now;

int a[maxn],v[maxn];

char ch[];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)

    {

        scanf("%s",ch);

        if(ch[]=='B')a[i]=;

    }

    ans=inf;

    for(int i=;i<=n;i++)

    {

        tim=;now=;

        for(int j=;j<=n-i+;j++)

        {

            if(v[j]==i)now^=;

            if(a[j]^now)tim++,now^=,v[j+i]=i;

        }

        bool flag=;

        for(int j=n-i+;j<=n;j++)

        {

            if(v[j]==i)now^=;

            if(a[j]^now)

            {

                flag=;

                break;

            }

        }

        if(!flag)

        if(tim<ans)ans=tim,ansk=i;

    }

    printf("%d %d\n",ansk,ans);

    return ;

}

　　bzoj2199: [Usaco2011 Jan]奶牛议会

　　　　网上题解都不tarjan缩点的。。。一缩就跑到#26了

　　　　因为是求所有解中的，不能拓扑后倒序了，只能一个议案一个议案地枚举，判断Y和N是否可以，如果Y和N都行就是？了。

　　　　今天发现自己写了两年的tarjan一直是错的，怎么还能过那么多题QAQ

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int maxn=;

struct poi{int x,too,pre;}e[maxn],e2[maxn];

int n,m,t,tot,tot2,tott,top,color;

int dfn[maxn],low[maxn],col[maxn],last[maxn],last2[maxn],v[maxn],st[maxn],lack[maxn];

char ans[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int readd()

{

    int x;read(x);char c=getchar();

    while(c!='Y'&&c!='N')c=getchar();

    if(c=='Y')return (x<<)^;

    return x<<;

}

void add(int x,int y){e[++tot].too=y;e[tot].x=x;e[tot].pre=last[x];last[x]=tot;}

void add2(int x,int y){e2[++tot2].too=y;e2[tot2].x=x;e2[tot2].pre=last2[x];last2[x]=tot2;}

void dfs(int x)

{

    v[x]=t;

    for(int i=last2[x];i;i=e2[i].pre)

    if(v[e2[i].too]!=t)dfs(e2[i].too);

}

bool check(int x)

{

    t++;dfs(x);

    for(int i=;i<=n;i++)

    if(v[col[(i<<)^]]==t&&v[col[i<<]]==t)return ;

    return ;

}

void tarjan(int x)

{

    dfn[x]=low[x]=++tott;st[++top]=x;lack[x]=top;

    for(int i=last[x];i;i=e[i].pre)

    if(!dfn[e[i].too])tarjan(e[i].too),low[x]=min(low[x],low[e[i].too]);

    else if(!col[e[i].too])low[x]=min(low[x],dfn[e[i].too]);

    if(dfn[x]==low[x])

    {

        color++;

        for(;top>=lack[x];top--)col[st[top]]=color;

    }

}

void dfss(int x)

{

    v[x]=;

    for(int i=last[x];i;i=e[i].pre)

    if(!v[e[i].too])dfss(e[i].too);

}

int main()

{

    read(n);read(m);

    for(int i=;i<=m;i++)

    {

        int x=readd(),y=readd();

        add(x^,y);add(y^,x);

    }

    for(int i=;i<=((n<<)^);i++)if(!dfn[i])tarjan(i);

    for(int i=;i<=tot;i++)

    if(col[e[i].x]!=col[e[i].too])add2(col[e[i].x],col[e[i].too]);

    for(int i=;i<=n;i++)

    {

        if(col[(i<<)^]==col[i<<]){puts("IMPOSSIBLE");return ;}

        int x=check(col[(i<<)^]),y=check(col[i<<]);

        if(!(x||y)){puts("IMPOSSIBLE");return ;}

        else if(x&&y)ans[i]='?';

        else if(x)ans[i]='Y';

        else if(y)ans[i]='N';

    }

    for(int i=;i<=n;i++)putchar(ans[i]);

}

　　bzoj1718: [Usaco2006 Jan] Redundant Paths 分离的路径

　　　　边双连通分量缩点后求出叶子数，(leaf+1)/2为答案，易证，自己脑补

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int x,too,pre;}e[maxn],e2[maxn];

int n,m,x,y,z,tot,tot2,leaf,tott,top,color;

int col[maxn],dfn[maxn],low[maxn],st[maxn],lack[maxn],last[maxn],chu[maxn],last2[maxn],v[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].x=x;e[tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void add2(int x,int y){e2[++tot2].x=x;e2[tot2].too=y;e2[tot2].pre=last2[x];last2[x]=tot2;}

void tarjan(int x,int fa)

{

    dfn[x]=low[x]=++tott;st[++top]=x;lack[x]=top;

    for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)

    if(too!=fa)

    {

        if(!dfn[too])tarjan(too,x),low[x]=min(low[x],low[too]);

        else if(!col[too])low[x]=min(low[x],dfn[too]);

    }

    if(dfn[x]==low[x])for(color++;top>=lack[x];top--)col[st[top]]=color,add2(color,st[top]);

}

int main()

{

    read(n);read(m);

    for(int i=;i<=m;i++)read(x),read(y),add(x,y),add(y,x);

    for(int i=;i<=n;i++)if(!dfn[i])tarjan(i,);

    for(int k=;k<=color;k++)

    for(int j=last2[k];j;j=e2[j].pre)

    for(int i=last[e2[j].too];i;i=e[i].pre)

    if(v[col[e[i].too]]!=k&&(col[e[i].too]!=k))chu[k]++,v[col[e[i].too]]=k;

    for(int i=;i<=color;i++)if(chu[i]==)leaf++;

    printf("%d\n",(leaf+)/);

    return ;

}

　　bzoj1700: [Usaco2007 Jan]Problem Solving 解题

　　　　DP。f[i][j]表示解决i到j道题的最少天数。

　　　　如果某天付完尾款还能在付首付就有 f[j][i]=min(f[k][j-1]+1)

　　　　不然就 f[j][i]=min(f[k][j-1]+2)

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot;

int f[maxn][maxn],suma[maxn],sumb[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(m);read(n);

    for(int i=;i<=n;i++)read(suma[i]),read(sumb[i]);

    for(int i=;i<=n;i++)suma[i]+=suma[i-],sumb[i]+=sumb[i-];

    memset(f,0x3f,sizeof(f));f[][]=;

    for(int i=;i<=n;i++)

    for(int j=;j<=i;j++)

    for(int k=;k<j;k++)

    {

        if(m>=(sumb[j-]-sumb[k-])&&m>=(suma[i]-suma[j-])&&m>=(sumb[i]-sumb[j-]))

        f[j][i]=min(f[j][i],f[k][j-]+);

        if(m>=(sumb[j-]-sumb[k-]+suma[i]-suma[j-])&&m>=(sumb[i]-sumb[j-]))

        f[j][i]=min(f[j][i],f[k][j-]+);

    }

    int ans=inf;

    for(int i=;i<=n;i++)ans=min(ans,f[i][n]);

    printf("%d\n",ans);

    return ;

}

　　bzoj1755: [Usaco2005 qua]Bank Interest

　　　　。。。。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

double r,m,y;

void read(double &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(r);read(m);read(y);

    for(int i=;i<=y;i++)

    m=m*(+r/);

    printf("%d\n",(int)floor(m));

    return ;

}

　　bzoj1731: [Usaco2005 dec]Layout 排队布局

　　　　差分约束系统。

　　　　求最大值的话先化成x-y<=c的形式（c为常数），y往x连边权值为c跑最短路。

　　　　求最小值的话先化成x-y>=c的形式（c为常数），y往x连边权值为c跑最长路。

　　　　小于或大于要化成小于等于或大于等于

　　　　负环则无解。dist[n]==inf说明对n无限制。

　　　　理解：x-y<=c化成x<=c+y的形式，类似最短路中的松弛操作（dist[too]>dist[now]+e[i].dis），最长路同理。最短路为最大值是因为同小取小，最长路最小值是因为同大取大。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre,sum;}e[maxn];

int n,ml,md,x,y,z,front,rear,tot;

int dist[maxn],h[maxn],v[maxn],last[maxn],tim[maxn];

bool flag;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

void spfa()

{

    for(int i=;i<=n;i++)dist[i]=inf;

    dist[]=;v[]=;front=rear=;h[++rear]=;

    while(front!=rear)

    {

        int now=h[++front];if(front==maxn)front=-;

        for(int i=last[now],too=e[i].too;i;i=e[i].pre,too=e[i].too)

        if(dist[too]>dist[now]+e[i].sum)

        {

            dist[too]=dist[now]+e[i].sum;

            if(!v[too])

            {

                if(tim[too]>){printf("-1");flag=;return;}

                tim[too]++;v[too]=;h[++rear]=too;

                if(rear==maxn)rear=-;

            }

        }

        v[now]=;

    }

}

int main()

{

    read(n);read(ml);read(md);

    for(int i=;i<=n;i++)add(i,i-,);

    for(int i=;i<=ml;i++)read(x),read(y),read(z),add(x,y,z);

    for(int i=;i<=md;i++)read(x),read(y),read(z),add(y,x,-z);

    spfa();

    if(flag)return ;

    if(dist[n]==inf)printf("-2");

    else printf("%d\n",dist[n]);

    return ;

}

　　bzoj1705: [Usaco2007 Nov]Telephone Wire 架设电话线

　　　　f[i][j]前 i 个柱子，第 i 个高度为 j 的最小代价

　　　　f[i][j] = f[i-1][k] + c*(j-k) + (h[i]-j)^2

　　　　f[i][j] = f[i-1][k] - c*k + c*j + h[i]^2 - 2*h[i]*j + j^2;

　　　　可以发现k和j无关，所以可以把时间复杂度降低到O（n*100）

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=;

int n,c,x,y,z,mn,ans,tot;

int h[maxn],f[maxn][];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(c);

    for(int i=;i<=n;i++)read(h[i]);

    memset(f,0x7f,sizeof(f));

    for(int i=;i<=;i++)f[][i]=(h[]-i)*(h[]-i);

    for(int i=;i<=n;i++)

    {

        mn=inf;

        for(int j=h[i-];j<max(h[i-],h[i]);j++)mn=min(mn,f[i-][j]-c*j);

        for(int j=max(h[i-],h[i]);j<=;j++)

        {

            mn=min(mn,f[i-][j]-c*j);

            f[i][j]=min(f[i][j],mn-*h[i]*j+j*j+c*j+h[i]*h[i]);

        }

        mn=inf;

        for(int j=;j>=h[i];j--)

        {

            if(j>=h[i-])mn=min(mn,f[i-][j]+c*j);

            f[i][j]=min(f[i][j],mn-*h[i]*j+j*j-c*j+h[i]*h[i]);

        }

    }

    ans=inf;

    for(int i=;i<=;i++)ans=min(ans,f[n][i]);

    printf("%d\n",ans);

    return ;

}

　　bzoj1575: [Usaco2009 Jan]气象牛Baric

　　　　f[i][j]前 i 个数据，选了 j 个的最小误差

　　　　预处理出st[i] , mid[i][j] , ed[i]表示 i 为开头的误差，选 i 和 j 中间的误差，i 为结尾的误差。

　　　　if(j==1)f[i][j] = st[i];

　　　　else f[i][j] = f[k][j-1] + mid[k][i];

　　　　最后找最小值的时候再把ed[i]加上就行。

　　　　一开始没在数据最小前提下找最小误差WA了两次好气啊

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,e;

ll f[maxn][maxn],ans2;

int st[maxn],mid[maxn][maxn],ed[maxn],a[maxn],ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(e);

    for(int i=;i<=n;i++)read(a[i]);

    for(int i=;i<=n;i++)

    {

        for(int j=;j<i;j++)st[i]+=*abs(a[i]-a[j]);

        for(int j=i+;j<=n;j++)

        for(int k=i+;k<j;k++)

        mid[i][j]+=abs(*a[k]-a[i]-a[j]);

        for(int j=i+;j<=n;j++)ed[i]+=*abs(a[i]-a[j]);

    }

    memset(f,,sizeof(f));f[][]=;

    for(int i=;i<=n;i++)

    for(int j=;j<=i;j++)

    if(j==)f[i][j]=st[i];

    else for(int k=;k<i;k++)f[i][j]=min(f[i][j],f[k][j-]+mid[k][i]);

    ans=ans2=inf;

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

    if(f[j][i]+ed[j]<=e)

    if(ans>=i)ans=i,ans2=min(ans2,f[j][i]+ed[j]);

    printf("%d %lld\n",ans,ans2);

}

　　bzoj1783: [Usaco2010 Jan]Taking Turns

　　　　博弈论DP...

　　　　f[i]表示先手取i，先手能取得的最大收益。g[i]表示先手取i，后手能获得的最大收益。

　　　　后手显然每次取之前先手能取的最大收益，因为先手取完变后手。

　　　　因为先手是之前的后手，后手是之前的先手，所以先手之前取什么取决于后手，那么先手就只能取后手取的maxi的后手最大值+a[i]。

　　　　g[i] = f[maxi];

　　　　f[i] = g[maxi] + a[i];

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,maxi;

int a[maxn];

ll f[maxn],g[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i]);

    maxi=n+;

    for(int i=n;i;i--)

    {

        g[i]=f[maxi];

        f[i]=g[maxi]+a[i];

        if(f[i]>=f[maxi])maxi=i;

    }

    printf("%lld %lld\n",f[maxi],g[maxi]);

    return ;

}

　　　　UPD：还有一种比较妙的做法是，维护X和Y分别表示当前的先手的最大收益和当前的后手的最大收益，实际上先手已经选过了，现在排到后手选，若是后手选了a[i]能大于等于当前的先手，也就是先手能找到一个更大的收益，那么就选，并且后手变先手。

　　　　用DP更好理解。f[i][0]表示先手，f[i][1]表示后手。两人都不选，f[i][0]=f[i+1][0],f[i][1]=f[i+1][1]。但是上次的后手可以变成这次的先手if(f[i+1][1]+a[i]>=f[i][0])f[i][0]=f[i+1][1]+a[i],同时上次先手变这次后手f[i][1]=f[i+1][0];

　　　　注意由于是倒推，应该找个先手的最大值，若后手取一个数没有比当前先手大而变成先手的话，显然先手并不会这么笨，还是取之前那个好

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,a[maxn];

ll x,y;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i]);

    for(int i=n;i;i--)if(y+a[i]>=x)swap(x,y),x+=a[i];

    printf("%lld %lld\n",x,y);

    return ;

}

　　bzoj1774: [Usaco2009 Dec]Toll 过路费

　　　　floyd中间点按点权从小到大枚举，那i->k->j这条路径上点权最大的一定是 i j k 三者之一。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{ll c,pos;}a[maxn];

ll n,m,K,x,y,z;

ll f[maxn][maxn],g[maxn][maxn],cc[maxn];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.c<b.c;}

int main()

{

    read(n);read(m);read(K);

    for(int i=;i<=n;i++)read(a[i].c),a[i].pos=i,cc[i]=a[i].c;

    sort(a+,a++n,cmp);

    memset(f,,sizeof(f));memset(g,,sizeof(g));

    for(int i=;i<=m;i++)read(x),read(y),read(z),g[y][x]=g[x][y]=min(z,g[x][y]);

    for(int i=;i<=n;i++)g[i][i]=;

    for(int l=;l<=n;l++)

    {

        ll k=a[l].pos,c=a[l].c;

        for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

        {

            g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

            f[i][j]=min(f[i][j],g[i][k]+g[k][j]+max(c,max(cc[i],cc[j])));

        }

    }

    for(int i=;i<=K;i++)

    {

        read(x);read(y);

        printf("%lld\n",f[x][y]);

    }

    return ;

}

　　bzoj1590: [Usaco2008 Dec]Secret Message 秘密信息

　　　　字典树记录一下就行。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot;

int next[maxn][],a[maxn],son[maxn],cnt[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void insert(int len)

{

    int now=;

    for(int i=;i<=len;i++)

    {

        if(!next[now][a[i]])next[now][a[i]]=++tot;

        now=next[now][a[i]];

        son[now]++;

        if(i==len)cnt[now]++;

    }

}

int find(int len)

{

    int now=,sum=;

    for(int i=;i<=len;i++)

    {

        if(!next[now][a[i]])break;

        now=next[now][a[i]];

        if(i==len)sum+=son[now];

        else sum+=cnt[now];

    }

    return sum;

}

int main()

{

    tot=;

    read(n);read(m);

    for(int i=;i<=n;i++)

    {

        read(x);

        for(int j=;j<=x;j++)

        read(a[j]);

        insert(x);

    }

    for(int i=;i<=m;i++)

    {

        read(x);

        for(int j=;j<=x;j++)

        read(a[j]);

        printf("%d\n",find(x));

    }

    return ;

}

　　bzoj1577: [Usaco2009 Feb]庙会捷运Fair Shuttle　　

　　　　贪心，能加就加，不能加踢出去最晚下车的。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct zs{int y,c,pre;}e[maxn];

struct poi{int y,c;};

priority_queue<poi>q;

bool operator<(poi a,poi b){return a.y<b.y;}

int n,c,x,y,z,k,tot,ans,people;

int last[maxn],xiache[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].y=y;e[tot].c=z;e[tot].pre=last[x];last[x]=tot;}

int main()

{

    read(k);read(n);read(c);

    for(int i=;i<=k;i++)

    {

        read(x);read(y);read(z);

        if(x==y)ans+=z;

        else add(x,y,z);

    }

    for(int i=;i<=n;i++)

    {

        for(int j=last[i];j;j=e[j].pre)q.push((poi){e[j].y,e[j].c}),people+=e[j].c,xiache[e[j].y]+=e[j].c;

        ans+=xiache[i];people-=xiache[i];

        while(people>c)

        {

            poi now=q.top();

            people-=now.c;xiache[now.y]-=now.c;q.pop();

            if(people<c)q.push((poi){now.y,c-people}),xiache[now.y]+=c-people,people=c;

        }

    }

    printf("%d\n",ans);

    return ;

}

　　bzoj1663: [Usaco2006 Open]赶集

　　　　按时间排序后DP f[i] = max ( f[i] , f[j]+1 ) t[j] + dis[j][i] <= t[i]

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int t,pos;}a[maxn];

int n,m,x,y,z,tot,ans;

int f[maxn],dis[maxn][maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.t<b.t;}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i].t),a[i].pos=i;

    sort(a+,a++n,cmp);

    for(int i=;i<=n;i++)for(int j=;j<=n;j++)read(dis[i][j]);

    for(int i=;i<=n;i++)dis[][i]=dis[][i];

    for(int i=;i<=n;i++)

    {

        for(int j=;j<i;j++)

        if(a[j].t+dis[a[j].pos][a[i].pos]<=a[i].t)

        {

            f[i]=max(f[i],f[j]+);

            ans=max(ans,f[i]);

        }

    }

    printf("%d\n",ans);

    return ;

}

　　bzoj1775: [Usaco2009 Dec]Vidgame 电视游戏问题

　　　　自己瞎写了个DP居然过了...

　　　　f[i][j]表示前 i 个平台，预算为 j 的最大收益

　　　　f[i][j] = max( f[i][j] , max( f[i][k-gp[i]]+pv[j] , f[i-1][k-gp[i]]+pv[j] ) );

　　　　算 i 时 k 循环范围是 v-p[i]~gp[i] ，最后令f[i][k]=f[i][k-p[i]]，相当于强制买了平台。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,v;

int f[][],p[maxn],g[maxn],gp[maxn],pv[maxn],ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(v);

    for(int i=;i<=n;i++)

    {

        read(p[i]);read(g[i]);

        for(int j=;j<=g[i];j++)

        {

            read(gp[j]);read(pv[j]);

            for(int k=v-p[i];k>=gp[j];k--)

            f[i][k]=max(f[i][k],max(f[i][k-gp[j]]+pv[j],f[i-][k-gp[j]]+pv[j]));

        }

        for(int k=v;k>=p[i];k--)f[i][k]=max(f[i-][k],f[i][k-p[i]]);

        for(int k=p[i]-;k>=;k--)f[i][k]=f[i-][k];

    }

    for(int i=;i<=v;i++)ans=max(ans,f[n][v]);

    printf("%d\n",ans);

    return ;

}

　　bzoj1583: [Usaco2009 Mar]Moon Mooing 哞哞叫

　　　　两个公式都是递增的，那么搞一个队列，记录下两个公式分别遍历到哪里，比较两个公式遍历到的元素再算一次公式的大小，把小的一个加入队列并把指针后移一位，这样可以保证一直最小。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=;

ll n,c,num[][],now1,now2,ans[maxn],r;

void read(ll &k)

{

    k=;int f=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(c);read(n);

    for(int i=;i<=;i++)

    for(int j=;j<=;j++)

    read(num[i][j]);

    ans[]=c;int l1=,l2=;r=;

    now1=num[][]*c/num[][]+num[][];

    now2=num[][]*c/num[][]+num[][];

    while(r<n)

    {

        if(now1<now2)

        {

            if(now1!=ans[r])ans[++r]=now1;

            now1=ans[++l1]*num[][]/num[][]+num[][];

        }

        else

        {

            if(now2!=ans[r])ans[++r]=now2;

            now2=ans[++l2]*num[][]/num[][]+num[][];

        }

    }

    printf("%lld\n",ans[n]);

}

　　bzoj1716: [Usaco2006 Dec]The Fewest Coins 找零钱

　　　　对John做多重背包，店家做无限（完全？）背包，如果John给的钱超过n*vmax，那至少给了（n+1）个硬币，根据抽屉原理必有一种硬币有两颗，所以拿回来就行。。。网上题解说的vmax*vmax我不怎么懂QAQ

　　　　涨姿势，原来多重背包还能二进制优化O_O

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=;

struct poi{int c,v;}a[maxn];

int n,m,x,y,z,tot,t,N,t1,t2,vmax,ans,inf;

int f[maxn],g[maxn],v[maxn],c[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.v<b.v;}

int main()

{

    read(n);read(t);

    for(int i=;i<=n;i++)read(v[i]),vmax=max(vmax,v[i]);

    for(int i=;i<=n;i++)

    {

        read(c[i]);

        for(int j=;j<=c[i];j<<=)a[++N].c=j,a[N].v=v[i]*j,c[i]-=j;

        if(c[i])a[++N].c=c[i],a[N].v=c[i]*v[i];

    }

    sort(a+,a++N,cmp);

    t1=t+n*vmax;t2=n*vmax;

    while(N&&a[N].v>t1)N--;

    memset(f,,(t1+)<<);f[]=;inf=f[];

    for(int i=;i<=N;i++)

    {

        for(int j=t1;j>=a[i].v;j--)

        f[j]=min(f[j],f[j-a[i].v]+a[i].c);

    }

    memset(g,,(t2+)<<);g[]=;

    for(int i=;i<=n;i++)

    {

        for(int j=v[i];j<=t2;j++)

        g[j]=min(g[j],g[j-v[i]]+);

    }

    ans=inf;

    for(int i=t;i<=t1;i++)ans=min(ans,f[i]+g[i-t]);

    if(ans==inf)printf("-1");

    else printf("%d\n",ans);

    return ;

}

　　bzoj1742: [Usaco2005 nov]Grazing on the Run 边跑边吃草

　　　　好神的DP！居然计算未来的代价！虽然这样中间的状态就都全部是为最后的答案服务，本身是错误的了...

　　　　因为不可能路过草不吃，于是吃的一定是一段连续的区间。

　　　　f[i][j][0]表示吃了 i ~ j ，在 i 的代价，f[i][j][0]就是在 j 的代价。

　　　　f[i][j][0] = min ( f[i+1][j][0] + dis( i , i + 1) * ( n - ( j - i )) , f[i+1][j][1] + dis( i , j ) * ( n - ( j - i ) ));

　　　　之所以* ( n - ( j - i ))是因为走这段路的过程中其他草也会增加腐败度，计算了未来的代价，妙啊

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,ans,l,rc;

int f[maxn][],a[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(l);

    for(int i=;i<=n;i++)read(a[i]);

    sort(a+,a++n);

    for(int i=;a[i]<=l&&i<=n;i++)f[i][]=f[i][]=(l-a[i])*n,rc=i;

    for(int i=rc+;i<=n;i++)f[i][]=f[i][]=(a[i]-l)*n;

    for(int i=;i<n;i++)

    {

        for(int j=;j<=n;j++)

        {

            f[j][]=min(f[j][]+(a[j+i]-a[j+i-])*(n-i),f[j][]+(a[j+i]-a[j])*(n-i));

            f[j][]=min(f[j+][]+(a[j+]-a[j])*(n-i),f[j+][]+(a[j+i]-a[j])*(n-i));

        }

    }

    printf("%d\n",min(f[][],f[][]));

    return ;

}

　　bzoj1594: [Usaco2008 Jan]猜数游戏

　　　　卡常卡的已经不知道这题怎么写了233，至少上了第一页QAQ CZL#1 %%%

　　　　二分答案，区间权值降序排序后，用并查集check，具体方法是将某个区间[l,r]的所有数父亲变为l-1，如果r的父亲 < l说明这个区间被完全覆盖了。

　　　　矛盾的情况：①相同权值的区间没有交集②权值大的区间覆盖了权值小的区间的交集

　　　　判断相同权值有没有交集的话只要记录最大的左端点lmax和最小的右端点rmin，如果rmin<lmax就是没交集了。

　　　　于是这个权值一定存在于[lmax,rmin]这个交集，看一下有没有被覆盖就行了。

　　　　因为权值相同的区间一定都有交集所以可以看成一个大区间把lmin到rmax全部指向lmin-1。

　　　　离散化的话如果两个区间的端点没有紧挨着（r1+1<l2），那么要给中间的区间空个格，也就是r1离散化后的值实际比l2离散化后的值少2。

　　　　像这种求被覆盖区间的都可以用并查集

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int pos,sum;}b[maxn];

int n,m,mid,lmax,lmin,rmax,rmin,now,last,rc,noww,l1,r1;

int l[maxn],r[maxn],x[maxn],a[maxn*],pos[maxn],fa[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.sum>b.sum;}

int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}

bool check()

{

    for(int i=;i<=now;i++)fa[i]=i;

    noww=;

    while(b[noww].pos>mid)noww++;

    lmax=lmin=pos[l[b[noww].pos]],rmax=rmin=pos[r[b[noww].pos]];

    rc=;last=noww;

    for(int i=noww+;i<=m;i++)

    {

        if(b[i].pos>mid)continue;

        rc++;

        if(b[i].sum!=b[last].sum)

        {

            if(gf(rmin)<lmax)return ;

            for(int j=fa[rmax];j>=lmin;j=fa[j])fa[gf(j)]=gf(j-);

            lmax=lmin=pos[l[b[i].pos]],rmax=rmin=pos[r[b[i].pos]];

        }

        else

        {

            lmax=max(lmax,pos[l[b[i].pos]]);lmin=min(lmin,pos[l[b[i].pos]]);

            rmax=max(rmax,pos[r[b[i].pos]]);rmin=min(rmin,pos[r[b[i].pos]]);

            if(rmin<lmax)return ;

        }

        if(rc==mid)break;

        last=i;

    }

    if(gf(rmin)<lmax)return ;

    return ;

}

int main()

{

    read(n);read(m);

    for(int i=;i<=m;i++)read(l[i]),read(r[i]),read(x[i]);

    for(int i=;i<=m;i++)a[i<<]=l[i],a[(i<<)-]=r[i];

    sort(a+,a++(m<<));

    now=;

    for(int i=;i<=(m<<);i++,now++)

    {

        pos[a[i]]=now;

        if(a[i]+<a[i+])now++;

    }

    for(int i=;i<=m;i++)b[i].sum=x[i],b[i].pos=i;

    sort(b+,b++m,cmp);

    l1=,r1=m;

    while(l1<r1)

    {

        mid=(l1+r1+)>>;

        if(check())l1=mid;

        else r1=mid-;

    }

    printf("%d",l1==m?:(l1+));

    return ;

}

　　bzoj1712: [Usaco2007 China]Summing Sums 加密

　　　　可以发现sum每次都*(n-1)（QAQ我怎么没发现），然后就可以矩阵快速幂了。

　　　　先把矩阵跑出来，然后乘n次得到n个答案就行了。。。不需要每次都跑个矩阵出来（我傻逼吧

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#define ll long long

using namespace std;

const int maxn=,inf=1e9,mod=;

struct poi{ll mtx[][];}map,g,c;

ll n,m,x,y,z,T,sum;

ll a[maxn];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void merge(poi &a,poi &b)

{

    c.mtx[][]=c.mtx[][]=c.mtx[][]=c.mtx[][]=;

    for(int i=;i<=;i++)

    for(int j=;j<=;j++)

    for(int k=;k<=;k++)

    c.mtx[i][j]=(c.mtx[i][j]+a.mtx[i][k]*b.mtx[k][j])%mod;

    a.mtx[][]=c.mtx[][];a.mtx[][]=c.mtx[][];

    a.mtx[][]=c.mtx[][];a.mtx[][]=c.mtx[][];

}

void qsm(int n)

{

    while(n)

    {

        if(n&)merge(map,g);

        merge(g,g);

        n>>=;

    }

}

int main()

{

    read(n);read(T);

    for(int i=;i<=n;i++)read(a[i]);

    for(int i=;i<=n;i++)sum=(sum+a[i])%mod;

    map.mtx[][]=map.mtx[][]=;map.mtx[][]=map.mtx[][]=;

    g.mtx[][]=-;g.mtx[][]=;g.mtx[][]=;g.mtx[][]=n-;

    qsm(T);

    for(int i=;i<=n;i++)printf("%lld\n",(map.mtx[][]*a[i]+map.mtx[][]*sum)%mod);

    return ;

}

　　bzoj1916: [Usaco2010 Open]冲浪

　　　　DP。f[i][j][1]表示第i个点，失控了j次，这一次会失控。f[i][j][0]表示第i个点，失控了j次，这一次不会失控。

　　　　会失控就找到最小的，不会失控就找最大的，两者取最小值就是至少能得到的。

　　　　f[i][j][1]=min(f[i][j][1],min(f[e[i].too][j-1][1],f[e[i].too][j-1][0])+e[i].sum);

　　　　f[i][j][0]=max(f[i][j][0],min(f[e[i].too][j][1],f[e[i].too][j][0])+e[i].sum);

　　　　看了题解才知道最后一维省略其实更好写，我好傻QAQ

　　　　f[i][j]=min(min(f[e[i].too][j-1]+e[i].sum),max(f[e[i].too][j]+e[i].sum))。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{ll too,sum,pre;}e[maxn*];

ll n,m,k,x,y,z,tot,ans;

ll f[maxn][][],last[maxn];

bool v[maxn];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}

int min(int x,int y)

{

    if(x<)return y;

    if(y<)return x;

    return x>y?y:x;

}

void dfs(int x)

{

    if(x==n)return;

    for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)

    if(!v[too])v[too]=,dfs(too);

    for(int j=;j<=k;j++)

    {

        f[x][j][]=1ll*inf*;f[x][j][]=-1ll*inf*;

        for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)

        {

            if(j)f[x][j][]=min(f[x][j][],min(f[too][j-][],f[too][j-][])+e[i].sum);

            f[x][j][]=max(f[x][j][],min(f[too][j][],f[too][j][])+e[i].sum);

        }

    }

}

int main()

{

    read(n);read(m);read(k);

    for(int i=;i<=m;i++)read(x),read(y),read(z),add(x,y,z);

    dfs();

    ans=1ll*inf*;

    for(int i=;i<=k;i++)

    {

        ans=min(ans,f[][i][]);

        ans=min(ans,f[][i][]);

    }

    printf("%lld\n",ans);

    return ;

}

　　bzoj2274: [Usaco2011 Feb]Generic Cow Protests

　　　　MDZZ为什么模数是1e9+9啊？？？不按常理出牌

　　　　卡了半天常数没快多少还丑了一堆...那还是不卡常好了

　　　　离散化一下前缀和就可以用BIT优化DP了

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9,mod=1e9+;

ll n,x,N;

ll tree[maxn],a[maxn],b[maxn];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int lowbit(ll x){return x&-x;}

void add(ll x,ll y){for(;x<=N;x+=lowbit(x))tree[x]=tree[x]+y,(tree[x]>=mod)&&(tree[x]-=mod);}

int find(ll x){ll sum=;for(;x;x-=lowbit(x))sum=sum+tree[x],sum>=mod&&(sum-=mod);return sum;}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i]),a[i]+=a[i-],b[++N]=a[i];N++;

    sort(b+,b++N);N=unique(b+,b++N)-b-;

    for(int i=;i<=n;i++)a[i]=lower_bound(b+,b++N,a[i])-b;

    x=lower_bound(b+,b++N,)-b;

    add(x,);

    for(int i=;i<=n;i++)

    {

        x=find(a[i]);

        x>=mod&&(x-=mod);

        add(a[i],x);

    }

    printf("%lld\n",x);

    return ;

}

　　bzoj2097: [Usaco2010 Dec]Exercise 奶牛健美操

　　　　二分+树形DP+贪心

　　　　把所有子树的最长长度排序，某棵子树如果最长长度超过mid就切，否则如果最长+次长超过mid就切最长。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre;}e[maxn];

int n,s,x,y,l,r,mid,tot,ans,cnt;

int a[maxn],b[maxn],fir[maxn],last[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

bool dfs(int x,int fa)

{

    int cnt=;

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa)if(!dfs(e[i].too,x))return ;

    for(int i=last[x];i;i=e[i].pre)

    if(e[i].too!=fa)b[++cnt]=fir[e[i].too]+;

    sort(b+,b++cnt);

    for(;cnt;cnt--)

    {

        if(b[cnt]>mid)ans++;

        else if(b[cnt]+b[cnt-]>mid)ans++;

        else break;

        if(ans>s)return ;

    }

    fir[x]=b[cnt];

    return ;

}

int main()

{

    read(n);read(s);if(n==n-){puts("");return ;}if(n==n-){puts("");return ;}

    for(int i=;i<n;i++)read(x),read(y),add(x,y),add(y,x);

    l=;r=n-;

    while(l<r)

    {

        ans=;

        mid=(l+r)>>;

        if(dfs(,))r=mid;

        else l=mid+;

    }

    printf("%d\n",l);

}

　　bzoj1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场

　　　　同一行连通，同一列连通的行和列标同样的号，然后二分图最大匹配，同bzoj1741

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#define ll long long

using namespace std;

const int maxn=,inf=1e9,dx[]={,,,-},dy[]={,,-,};

struct poi{int too,pre;}e[maxn];

int n,m,x,y,z,tot,rowcnt,clncnt,t,ans;

int last[maxn],lin[maxn],row[maxn][maxn],cln[maxn][maxn],vv[maxn];

bool map[maxn][maxn];

char s[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

bool xyl(int x)

{

    for(int i=last[x];i;i=e[i].pre)

    if(vv[e[i].too]!=t)

    {

        vv[e[i].too]=t;

        if((!lin[e[i].too])||xyl(lin[e[i].too]))

        {

            lin[e[i].too]=x;

            return ;

        }

    }

    return ;

}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)

    {

        scanf("%s",s+);

        for(int j=;j<=m;j++)

        map[i][j]=(s[j]=='*');

    }

    for(int i=;i<=n;i++)

    {

        rowcnt++;

        for(int j=;j<=m;j++)

        if(!map[i][j])rowcnt++;

        else row[i][j]=rowcnt;

    }

    for(int i=;i<=m;i++)

    {

        clncnt++;

        for(int j=;j<=n;j++)

        if(!map[j][i])clncnt++;

        else cln[j][i]=clncnt;

    }

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    if(map[i][j])

    add(row[i][j],cln[i][j]);

    for(int i=;i<=rowcnt;i++)t++,ans+=xyl(i);

    printf("%d\n",ans);

    return ;

}

　　bzoj1738: [Usaco2005 mar]Ombrophobic Bovines 发抖的牛

　　　　没输出-1 WA了一万次，很伤心

　　　　先跑floyed，二分答案，小于这个答案的边加入，跑最大流check

　　　　这种所有牛同时出发找最短时间的一般都是二分，一开始以为是总时间想写费用流才发现不对QAQ

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=;

const ll inf=;

struct poi{ll too,pre,cf;}e[];

ll n,m,tot,ans,x,y,z,front,rear,sum;

ll l,r,mid,cnt,mx;

ll h[maxn],v[maxn],last[maxn],dis[maxn],cur[maxn],a[maxn],b[maxn];

ll f[][];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,ll z)

{

    e[++tot].too=y;e[tot].cf=z;e[tot].pre=last[x];last[x]=tot;

    e[++tot].too=x;e[tot].cf=;e[tot].pre=last[y];last[y]=tot;

}

bool bfs()

{

    for(int i=;i<=sum;i++)v[i]=,dis[i]=-;

    dis[]=;v[]=;h[]=;front=;rear=;

    while(front!=rear)

    {

        int now=h[++front];if(front==maxn)front=-;

        for(int i=last[now];i;i=e[i].pre)

        {

            int too=e[i].too;

            if((!v[too])&&e[i].cf)

            {

                dis[too]=dis[now]+;if(too==sum)return ;

                v[too]=;h[++rear]=too;if(rear==maxn)rear=-;

            }

        }

    }

    return ;

}

int dfs(int x,ll f)

{

    int flow=,tmp;

    if(x==sum)return f;

    for(ll &i=cur[x];i;i=e[i].pre)

    {

        int too=e[i].too;

        if(dis[too]==dis[x]+&&e[i].cf)

        {

            tmp=dfs(too,min(f-flow,e[i].cf));

            e[i].cf-=tmp;e[i^].cf+=tmp;flow+=tmp;

            if(f==flow)return f;

        }

    }

    return flow;

}

void dinic()

{

    while(bfs())

    {

        for(int i=;i<=sum;i++)cur[i]=last[i];

        ans+=dfs(,inf);

    }

}

bool check()

{

    memset(last,,sizeof(last));memset(dis,,sizeof(dis));tot=;

    for(int i=;i<=n;i++)add(,i,a[i]),add(i,i+n,inf),add(i+n,sum,b[i]);

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

    if(f[i][j]<=mid)add(i,j+n,inf);

    ans=;

    dinic();

    return ans==cnt;

}

int main()

{

    tot=;

    read(n);read(m);sum=*n+;

    for(int i=;i<=n;i++)read(a[i]),read(b[i]),cnt+=a[i];

    for(int i=;i<=n;i++)for(int j=;j<=n;j++)f[i][j]=inf;

    for(int i=;i<=n;i++)f[i][i]=;

    for(int i=;i<=m;i++)read(x),read(y),read(z),f[x][y]=min((ll)z,f[x][y]),f[y][x]=f[x][y],mx+=f[x][y];

    for(int k=;k<=n;k++)

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

    l=;r=mx+;

    while(l<r)

    {

        mid=(l+r)>>;

        if(check())r=mid;

        else l=mid+;

    }

    if(r==(mx+)&&(!check()))printf("-1");

    else printf("%lld\n",l);

    return ;

}

　　bzoj1740: [Usaco2005 mar]Yogurt factory 奶酪工厂

　　　　记录一下之前的费用最小值和现在比较就行了...之前被HR一眼秒过

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

ll n,s,c,y,mn,ans;

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')f=='-'&&(c=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(s);

    mn=inf;

    for(int i=;i<=n;i++)

    {

        read(c);read(y);

        mn=min(mn+s,c);

        ans+=mn*y;

    }

    printf("%lld\n",ans);

}

　　bzoj2099: [Usaco2010 Dec]Letter 恐吓信

　　　　不会SAM（躺

　　　　显然每次砍LCP就行。

　　　　先跑出A串的SA，这样就排好了每个后缀的字典序，于是在A串中二分找到B串的字典序位置 l，LCP一定是B串与sa[l]或sa[l+1]开始的后缀的LCP，然后logn求LCP就行了。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#define ull unsigned long long

using namespace std;

const int maxn=;

int n,m,p,ans,mm;

int sum[maxn],rk[maxn],sa[maxn],trk[maxn],tsa[maxn];

ull hs1[maxn],hs2[maxn],mul[maxn];

char s[maxn],s2[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void suffix()

{

    for(int i=;i<=n;i++)sum[s[i]]++;

    for(int i=;i<=;i++)sum[i]+=sum[i-];

    for(int i=n;i;i--)sa[sum[s[i]]]=i,sum[s[i]]--;

    rk[sa[]]=;p=;

    for(int i=;i<=n;i++)rk[sa[i]]=(s[sa[i]]!=s[sa[i-]])?++p:p;

    m=p;int j=;

    while(m<n)

    {

        memcpy(trk,rk,sizeof(rk));memset(sum,,sizeof(sum));p=;

        for(int i=n-j+;i<=n;i++)tsa[++p]=i;

        for(int i=;i<=n;i++)if(sa[i]>j)tsa[++p]=sa[i]-j;

        for(int i=;i<=n;i++)rk[i]=trk[tsa[i]],sum[rk[i]]++;

        for(int i=;i<=m;i++)sum[i]+=sum[i-];

        for(int i=n;i;i--)sa[sum[rk[i]]]=tsa[i],sum[rk[i]]--;

        rk[sa[]]=;p=;

        for(int i=;i<=n;i++)rk[sa[i]]=(trk[sa[i]]!=trk[sa[i-]]||trk[sa[i]+j]!=trk[sa[i-]+j])?++p:p;

        m=p;j*=;

    }

}

int lcp(int a,int b)

{

    int l=,r=min(n-a+,mm-b+);

    while(l<r)

    {

        int mid=(l+r+)>>;

        ull hsa=hs1[a]-hs1[a+mid]*mul[mid],hsb=hs2[b]-hs2[b+mid]*mul[mid];

        if(hsa!=hsb)r=mid-;

        else l=mid;

    }

    return l;

}

int main()

{

    read(n);read(mm);

    for(int i=;i<=n;i++)

    for(s[i]=getchar();s[i]<'A'||s[i]>'Z';s[i]=getchar());

    suffix();

    mul[]=;

    for(int i=;i<=n;i++)mul[i]=mul[i-]*;

    for(int i=n;i;i--)hs1[i]=hs1[i+]*+1ull*(s[i]-'A');

    for(int i=;i<=mm;i++)

    for(s2[i]=getchar();s2[i]<'A'||s2[i]>'Z';s2[i]=getchar());

    for(int i=mm;i;i--)hs2[i]=hs2[i+]*+1ull*(s2[i]-'A');

    for(int i=;i<=mm;)

    {

        int l=,r=n;

        while(l<r)

        {

            int mid=(l+r+)>>;

            int len=lcp(sa[mid],i);

            if(s[sa[mid]+len]<s2[i+len])l=mid;

            else r=mid-;

        }

        i+=max(lcp(sa[l],i),lcp(sa[l+],i));

        ans++;

    }

    printf("%d\n",ans);

}

　　bzoj3408: [Usaco2009 Oct]Heat Wave 热浪

　　　　太年轻了一直不敢下手，就是个最短路而已= =

　　　　同样年轻的LLQ大佬

　　　　不贴代码了这博客要炸了

　　bzoj1744: [Usaco2005 oct]Skiing 奶牛滑雪

　　　　好强的题！正着来不行，倒着跑就可以了。从n,m到1,1，走过哪条边就给原来后面的距离除以这条边对速度的影响。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,dx[]={,,,-},dy[]={,,-,};

int n,m,x,y,z,tot,v0,nx,ny;

int h[maxn*][],front,rear,ht[maxn][maxn];

ll mi[maxn];

double dist[maxn][maxn],fumi[maxn];

bool v[maxn][maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

double get(int x,int y)

{

    if(x>y)return mi[x-y];

    return fumi[y-x];

}

void spfa(int x,int y)

{

    double inf=<<;inf*=inf;

    for(int i=;i<=n;i++)for(int j=;j<=m;j++)dist[i][j]=inf;

    h[][]=x;h[][]=y;front=;rear=;v[x][y]=;dist[x][y]=0.0;

    while(front!=rear)

    {

        nx=h[++front][];ny=h[front][];if(front==maxn*)front=-;

        for(int i=;i<;i++)

        {

            int xx=nx+dx[i],yy=ny+dy[i];

            if(xx<||xx>n||yy<||yy>m)continue;

            if(dist[xx][yy]>dist[nx][ny]/get(ht[xx][yy],ht[nx][ny])+1.0)

            {

                dist[xx][yy]=dist[nx][ny]/get(ht[xx][yy],ht[nx][ny])+1.0;

                if(!v[xx][yy])

                {

                    v[xx][yy]=;h[++rear][]=xx;h[rear][]=yy;

                    if(rear==maxn*)rear=-;

                }

            }

        }

        v[nx][ny]=;

    }

}

int main()

{

    read(v0);read(n);read(m);

    mi[]=;fumi[]=1.0;

    for(int i=;i<=;i++)mi[i]=mi[i-]*;

    for(int i=;i<=;i++)fumi[i]=fumi[i-]/;

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    read(ht[i][j]);

    spfa(n,m);

    printf("%.2lf\n",dist[][]/v0);

    return ;

}

　　bzoj1752: [Usaco2005 qua]Til the Cows Come Home

　　　　同上上题...nm看反WA了4次T_T

　　bzoj1733: [Usaco2005 feb]Secret Milking Machine 神秘的挤奶机

　　　　二分，长度<=mid就加入，网络流check

　　　　看样子很多人的网络流都没加当前弧优化？加了之后就上第一页了...

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre,cf;}e[maxn];

int n,m,tot,ans,front,rear,mid,t,l,r;

int h[maxn],v[maxn],last[],dis[maxn],cur[maxn],x[maxn],y[maxn],z[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z)

{

    e[++tot].too=y;e[tot].cf=z;e[tot].pre=last[x];last[x]=tot;

    e[++tot].too=x;e[tot].cf=;e[tot].pre=last[y];last[y]=tot;

}

bool bfs()

{

    for(int i=;i<=n;i++)v[i]=,dis[i]=-;

    dis[]=;v[]=;h[]=;front=;rear=;

    while(front!=rear)

    {

        int now=h[++front];if(front==maxn)front=-;

        for(int i=last[now];i;i=e[i].pre)

        {

            int too=e[i].too;

            if((!v[too])&&e[i].cf)

            {

                dis[too]=dis[now]+;if(too==n)return ;

                v[too]=;h[++rear]=too;if(rear==maxn)rear=-;

            }

        }

    }

    return ;

}

int dfs(int x,int f)

{

    int flow=,tmp;

    if(x==n)return f;

    for(int &i=cur[x];i;i=e[i].pre)

    {

        int too=e[i].too;

        if(dis[too]==dis[x]+&&e[i].cf)

        {

            tmp=dfs(too,min(f-flow,e[i].cf));

            e[i].cf-=tmp;e[i^].cf+=tmp;flow+=tmp;

            if(f==flow)return f;

        }

    }

    return flow;

}

void dinic()

{

    while(bfs())

    {

        for(int i=;i<=n;i++)cur[i]=last[i];

        ans+=dfs(,inf);

    }

}

bool check()

{

    tot=;memset(last,,sizeof(last));

    for(int i=;i<=m;i++)

    if(z[i]<=mid)

    {

        add(x[i],y[i],);

        add(y[i],x[i],);

    }

    ans=;

    dinic();

    return ans>=t;

}

int main()

{

    read(n);read(m);read(t);l=inf;r=-inf;

    for(int i=;i<=m;i++)read(x[i]),read(y[i]),read(z[i]),l=min(l,z[i]),r=max(r,z[i]);

    while(l<r)

    {

        mid=(l+r)>>;

        if(check())r=mid;

        else l=mid+;

    }

    printf("%d\n",l);

    return ;

}

　　bzoj2196: [Usaco2011 Mar]Brownie Slicing

　　　　二分，再套个二分检验。。。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

ll n,m,x,y,z,tot,cnt,A,B,l,r,mid,mid2,now;

ll a[maxn][maxn],sum[maxn][maxn];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool checkcheck()

{

    int ans=,last=;

    for(int i=;i<=m;i++)

    if(sum[mid2][i]-sum[now-][i]-sum[mid2][last-]+sum[now-][last-]>=mid)

    {

        last=i+;

        ans++;

        if(ans==B)return ;

    }

    return ;

}

bool check()

{

    now=;

    for(int i=;i<=A;i++)

    {

        int l=now,r=n;

        while(l<r)

        {

            mid2=(l+r)>>;

            if(checkcheck())r=mid2;

            else l=mid2+;

        }

        if(i==A)return mid2=(l+r)>>,checkcheck();

        now=l+;

        if(now>n)return ;

    }

    return ;

}

int main()

{

    read(n);read(m);read(A);read(B);

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    read(a[i][j]),cnt+=a[i][j],sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+a[i][j];

    l=;r=cnt/A/B;

    while(l<r)

    {

        mid=(l+r+)>>;

        if(check())l=mid;

        else r=mid-;

    }

    printf("%lld\n",l);

    return ;

}

　　bzoj1739: [Usaco2005 mar]Space Elevator 太空电梯

　　　　做n次多重背包

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int h,limit,c;}a[maxn];

int n,m,x,y,z,tot,ans;

int f[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.limit<b.limit;}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i].h),read(a[i].limit),read(a[i].c);

    sort(a+,a++n,cmp);

    for(int i=;i<=n;i++)

    for(int j=a[i].limit;j>=a[i].h;j--)

    for(int k=;k<=a[i].c;k++)

    {

        if(k*a[i].h>j)break;

        f[j]=max(f[j],f[j-k*a[i].h]+k*a[i].h);

    }

    for(int i=;i<=a[n].limit;i++)ans=max(f[i],ans);

    printf("%d\n",ans);

    return ;

}

　　bzoj2501: [usaco2010 Oct]Soda Machine

　　　　差分

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

struct poi{int sum,pos;}a[maxn];

int n,now,ans,cnt;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.sum<b.sum;}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[++cnt].sum),a[cnt].pos=,read(a[++cnt].sum),a[cnt].sum++,a[cnt].pos=-;

    sort(a+,a++cnt,cmp);

    for(int i=;i<=cnt;i++)

    {

        now+=a[i].pos;

        if(a[i].sum!=a[i+].sum)

        ans=max(ans,now);

    }

    printf("%d\n",ans);

}

　　bzoj2590: [Usaco2012 Feb]Cow Coupons

　　　　网上题解大部分是错的。。。包括黄学长的也被我hack了。还有一个博客大小写反了= =，但是代码是对的

　　　　首先肯定选k个优惠券最小的，如果不够选直接输出。如果还有多余的钱的话，比较一下（已买的里面原价与优惠价的最小差价+没买的里面的最小优惠价）和（没买的里面的最小原价），选一个小的。第一个实际上相当于把优惠卷花钱赎回来。。。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{ll sum,i;}qq1,qq2,qq3;

struct zs{ll p,c;}a[maxn];

priority_queue<poi>q1,q2,q3;

bool operator<(poi a,poi b){return a.sum>b.sum;}

ll n,m,k,x,y,z,tot,cost,ans;

bool v[maxn];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(zs a,zs b){return a.c<b.c;}

int main()

{

    read(n);read(k);read(m);

    for(int i=;i<=n;i++)read(a[i].p),read(a[i].c);

    sort(a+,a++n,cmp);

    for(int i=;i<=k;i++)

    {

        cost+=a[i].c;

        if(cost>m){printf("%d\n",i-);return ;}

    }

    for(int i=;i<=k;i++)q1.push((poi){a[i].p-a[i].c,i});

    for(int i=k+;i<=n;i++)q2.push((poi){a[i].c,i}),q3.push((poi){a[i].p,i});

    ans=k;v[]=;

    while(cost<m)

    {

        if(!q1.empty())qq1=q1.top(),q1.pop();else qq1.sum=inf;

        if(!q2.empty())for(qq2=q2.top(),q2.pop();v[qq2.i]&&(!q2.empty());q2.pop())qq2=q2.top();else qq2.sum=inf,qq2.i=;

        if(v[qq2.i])qq2.sum=inf;

        if(!q3.empty())for(qq3=q3.top(),q3.pop();v[qq3.i]&&(!q3.empty());q3.pop())qq3=q3.top();else qq3.sum=inf,qq3.i=;

        if(v[qq3.i])qq3.sum=inf;

        if(qq1.sum+qq2.sum>qq3.sum)

        {

            cost+=qq3.sum;

            if(qq1.sum!=inf)q1.push((poi){qq1.sum,qq1.i});

            if(qq2.sum!=inf)q2.push((poi){qq2.sum,qq2.i});

        }

        else

        {

            cost+=qq1.sum+qq2.sum;

            if(qq3.sum!=inf)q3.push((poi){qq3.sum,qq3.i});

        }

        if(cost<=m)ans++;

        if(ans==n)break;

    }

    printf("%lld\n",ans);

    return ;

}

　　bzoj1986: [USACO2004 Dec] Dividing the Path 划区灌溉

　　　　傻逼题调了半天。。怎么最近老是不能1A啊。。。总是出奇奇怪怪的错误

　　　　f[i]表示0~i被灌溉的最少喷灌器。

　　　　f[i]=min(f[j])+1;(i-2*B<=j<=I-2*A)

　　　　如果i在（l[i],r[i]）中，f[i]=inf;

　　　　单调队列优化即可

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,l,r,L,A,B,now;

int f[maxn],q[maxn],sum[maxn],v[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(L);read(A);read(B);

    for(int i=;i<=n;i++)

    {

        read(x);read(y);

        if(x+==y)continue;

        sum[x+]++;sum[y]--;

    }

    l=;r=;

    for(int i=;i<=L;i++)

    {

        now+=sum[i];v[i]=now;

        if(i&)continue;

        if((!v[i-*A])&&i-*A>=)

        {

            while(l<=r&&f[q[r]]>f[i-*A])r--;

            q[++r]=i-*A;

        }

        while(l<=r&&(i-q[l]>*B))l++;

        f[i]=(l>r)?inf:f[q[l]]+;

    }

    printf("%d\n",f[L]<inf?f[L]:-);

    return ;

}

　　bzoj1722: [Usaco2006 Mar] Milk Team Select 产奶比赛

　　　　早上打hihocoder暴力分都没拿满好惨啊QAQ

　　　　这破题还调了好久，我好傻逼

　　　　一眼树形DP。f[i][j][0/1] 有 j 对亲属关系，节点 i 选/不选。

　　　　对每个子树做多重背包就行了。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre;}e[maxn*];

int n,m,x,y,z,tot,X;

int f[maxn][maxn][],a[maxn],last[maxn],size[maxn],son[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void dfs(int x)

{

    f[x][][]=;f[x][][]=a[x];

    for(int i=last[x];i;i=e[i].pre)dfs(e[i].too),size[x]+=size[e[i].too]+,son[x]++;

    for(int i=last[x];i;i=e[i].pre)

    for(int j=size[x];j>=;j--)

    {

        for(int k=;k<=min(j,size[e[i].too]);k++)

        {

            if(j<=size[x]-son[x])f[x][j][]=max(f[x][j][],f[x][j-k][]+max(f[e[i].too][k][],f[e[i].too][k][]));

            f[x][j][]=max(f[x][j][],f[x][j-k][]+max(f[e[i].too][k][],k!=?f[e[i].too][k-][]:-inf));

        }

        if(j>size[e[i].too])f[x][j][]=max(f[x][j][],f[x][j-size[e[i].too]-][]+f[e[i].too][size[e[i].too]][]);

    }

    //for(int i=0;i<=size[x];i++)printf("x:%d i:%d fxi0:%d fxi1:%d\n",x,i,f[x][i][0],f[x][i][1]);

}

int main()

{

    read(n);read(X);

    for(int i=;i<=n;i++)

    {

        read(a[i]);read(y);

        if(y)add(y,i);else add(,i);

    }

    memset(f,-,sizeof(f));

    dfs();

    //printf("%d %d\n",f[1][0][0],f[1][0][1]);

    for(int i=n-;i>=;i--)if(f[][i][]>=X){printf("%d\n",i);return ;}

    printf("-1");

    return ;

}

　　bzoj2059: [Usaco2010 Nov]Buying Feed 购买饲料

　　　　MDZZ忘记自己开的是long long是8字节。。。初始化老是小了

　　　　简单DP。f[i][j]表示前i个商店，买j吨饲料的最小代价，单调队列优化。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{ll x,f,c;}a[maxn];

ll n,m,tot,k,e,l,r;

ll ans,dp[][];

ll q[maxn];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return a.x<b.x;}

int main()

{

    read(k);read(e);read(n);

    for(int i=;i<=n;i++)read(a[i].x),read(a[i].f),read(a[i].c);

    sort(a+,a++n,cmp);

    memset(dp[],0x7f,(k+)<<);dp[][]=;

    for(int i=;i<=n;i++)

    {

        l=;r=;

        for(int j=;j<=k;j++)

        {

            dp[i][j]=1ll*inf*;

            while(l<=r&&j-q[l]>a[i].f)l++;

            while(l<=r&&dp[i-][q[r]]-a[i].c*q[r]+q[r]*q[r]*(a[i].x-a[i-].x)>dp[i-][j]-a[i].c*j+j*j*(a[i].x-a[i-].x))r--;

            q[++r]=j;

            dp[i][j]=(l>r)?(1ll*inf*):dp[i-][q[l]]+a[i].c*(j-q[l])+q[l]*q[l]*(a[i].x-a[i-].x);

        }

    }

    ans=1ll*inf*;

    for(int i=;i<=n;i++)

    ans=min(ans,dp[i][k]+k*k*(e-a[i].x));

    printf("%lld\n",ans);

    return ;

}

　　bzoj1698: [Usaco2007 Feb]Lilypad Pond 荷叶池塘

　　　　哇日常水题调很久系列。　

　　　　最短路径怎么求很显然，往空地连1，荷叶连0。但是这样会发现在最短路松弛的时候记录的方案数会多算，因为可以走一圈荷叶代价为0再回来最短路径还是不变的，所以我们要想办法把边权0的去掉，就不会出现这种情况了。怎么办呢，提前dfs出两两空地能否不经过其他空地（可经过荷叶）到达就行了，然后连边边权为1，这样就去掉了所有边权为0的边，跑最短路。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=,inf=1e9,dx[]={-,-,,,,,-,-},dy[]={,,,,-,-,-,-};

struct poi{int tox,toy,pre;}e[];

int n,m,cnt,front,rear,tot,sx,sy,tx,ty,tim;

int map[maxn][maxn],b[maxn*maxn][],h[][],dist[maxn][maxn],last[maxn][maxn],vvv[maxn][maxn];

ll ans[maxn][maxn];

bool v[maxn][maxn],vv[maxn][maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x1,int y1,int x2,int y2){e[++tot].tox=x2;e[tot].toy=y2;e[tot].pre=last[x1][y1];last[x1][y1]=tot;}

void spfa(int x,int y)

{

    for(int i=;i<=n;i++)for(int j=;j<=m;j++)dist[i][j]=inf;

    dist[x][y]=;v[x][y]=;front=;rear=;h[rear][]=x;h[rear][]=y;ans[x][y]=;

    while(front!=rear)

    {

        int nowx=h[++front][],nowy=h[front][];if(front==)front=-;++tim;

        //printf("%d %d %d %lld\n",nowx,nowy,dist[nowx][nowy],ans[nowx][nowy]);

        for(int i=last[nowx][nowy],tox=e[i].tox,toy=e[i].toy;i;i=e[i].pre,tox=e[i].tox,toy=e[i].toy)

        {

            if(vvv[tox][toy]==tim)continue;vvv[tox][toy]=tim;

            if(dist[tox][toy]==dist[nowx][nowy]+)ans[tox][toy]+=ans[nowx][nowy];

            if(dist[tox][toy]>dist[nowx][nowy]+)

            {

                dist[tox][toy]=dist[nowx][nowy]+;

                ans[tox][toy]=ans[nowx][nowy];

                if(!v[tox][toy])

                {

                    v[tox][toy]=;h[++rear][]=tox;h[rear][]=toy;

                    if(rear==)rear=-;

                }

            }

        }

        for(int i=;i<;i++)

        {

            int tox=nowx+dx[i],toy=nowy+dy[i];

            if(tox<||tox>n||toy<||toy>m||map[tox][toy]==||vvv[tox][toy]==tim||map[tox][toy]==)continue;

            if(dist[tox][toy]==dist[nowx][nowy]+)ans[tox][toy]+=ans[nowx][nowy];

            if(dist[tox][toy]>dist[nowx][nowy]+)

            {

                dist[tox][toy]=dist[nowx][nowy]+;

                ans[tox][toy]=ans[nowx][nowy];

                if(!v[tox][toy])

                {

                    v[tox][toy]=;h[++rear][]=tox;h[rear][]=toy;

                    if(rear==)rear=-;

                }

            }

        }

    }

}

void dfs(int x,int y)

{

    vv[x][y]=;

    for(int i=;i<;i++)

    {

        int xx=x+dx[i],yy=y+dy[i];

        if(xx<||xx>n||yy<||yy>m||map[xx][yy]==)continue;

        if(map[xx][yy]==&&vv[xx][yy]!=)dfs(xx,yy);

        else if(map[xx][yy]!=)b[++cnt][]=xx,b[cnt][]=yy;

    }

}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    {

        read(map[i][j]);

        if(map[i][j]==)sx=i,sy=j;

        if(map[i][j]==)tx=i,ty=j;

        if(map[i][j]==)add(,,i,j);

    }

    for(int i=last[][];i;i=e[i].pre)

    {

        cnt=;

        if(!vv[e[i].tox][e[i].toy])dfs(e[i].tox,e[i].toy);

        for(int j=;j<=cnt;j++)

        for(int k=;k<=cnt;k++)

        add(b[j][],b[j][],b[k][],b[k][]);

    }

    spfa(sx,sy);

    if(dist[tx][ty]==inf)printf("-1");

    else printf("%d\n%lld",dist[tx][ty]-,ans[tx][ty]);

}

　　bzoj1777: [Usaco2010 Hol]rocks 石头木头

　　　　阶梯博弈 http://blog.csdn.net/longshuai0821/article/details/7793043

　　　　距离终点偶数长度的不用考虑.某个点的SG值为数量%(l+1)，手推可以推出来。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre;}e[maxn];

int n,m,x,y,z,tot,l,t,ans;

int v[maxn],dis[maxn],last[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void dfs(int x)

{

    for(int i=last[x];i;i=e[i].pre)

    dis[e[i].too]=dis[x]+,dfs(e[i].too);

}

int main()

{

    read(n);read(t);read(l);

    for(int i=;i<=n;i++)read(x),read(v[i]),add(x,i);

    dfs();

    for(int i=;i<=n;i++)if(dis[i]&)ans^=v[i]%(l+);

    for(int i=;i<=t;i++)

    {

        read(x);read(y);

        if(dis[x]&)ans^=(v[x]%(l+))^(y%(l+));

        v[x]=y;

        printf("%s\n",ans?"Yes":"No");

    }

    return ;

}

　　bzoj1729: [Usaco2005 dec]Cow Patterns 牛的模式匹配

　　　　嗯昨天调了一天错误代码，最后还是放弃了抄题解吧T_T

　　　　可以预处理出某种数字出现次数的前缀，KMP的时候计算一下这个区间内比自己小的数的个数就是排名。然后再比较两个串这个区间内相同数字的出现次数是否相同，如果这个条件和排名都符合，那么这两位就是可以匹配的。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,S,x1,x2,yy1,y2,cnt;

int rk[][maxn][],s[][maxn],f[maxn],ans[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int getrk(int x,int i,int j)

{

    x1=x2=yy1=y2=;

    for(int k=;k<s[x][i];k++)x1+=rk[x][i][k]-rk[x][i-j][k];

    yy1=rk[x][i][s[x][i]]-rk[x][i-j][s[x][i]];

    for(int k=;k<s[][j];k++)x2+=rk[][j][k];

    y2=rk[][j][s[][j]];

    return (x1==x2)&&(yy1==y2);

}

void getfail()

{

    f[]=;f[]=;int j;

    for(int i=;i<=m;i++)

    {

        for(j=f[i];j>&&(!getrk(,i,j));j=f[j]);

        if(getrk(,i,j))f[i+]=j+;else f[i+]=;

    }

}

void kmp()

{

    int j=;

    for(int i=;i<=n;i++)

    {

        while(j>&&(!getrk(,i,j)))j=f[j];

        if(getrk(,i,j))j++;

        if(j==m+)ans[++cnt]=i-m+,j=f[j];

    }

}

int main()

{

    read(n);read(m);read(S);

    for(int i=;i<=n;i++)read(s[][i]);

    for(int i=;i<=m;i++)read(s[][i]);

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=S;j++)rk[][i][j]=rk[][i-][j];

        rk[][i][s[][i]]++;

    }

    for(int i=;i<=m;i++)

    {

        for(int j=;j<=S;j++)rk[][i][j]=rk[][i-][j];

        rk[][i][s[][i]]++;

    }

    getfail();kmp();

    printf("%d\n",cnt);

    for(int i=;i<=cnt;i++)printf("%d\n",ans[i]);

    return ;

}

　　bzoj1605: [Usaco2008 Open]Crisis on the Farm 牧场危机

　　　　mdzz被输出方案最小字典序坑了好久TAT

　　　　预处理get[i][j]表示横坐标移动 i ，纵坐标移动 j 最后一步能救的牛。

　　　　f[i][j][k]表示已经走了i步，横坐标移动 j ，纵坐标移动 k最多能救几头牛，从四个方向转移+get[j][k]就行了。

　　　　方案就记录从哪转移来的，最小字典序我写了半天顺序实在调不下去了干脆写了个哈希来判...终于过了QAQ（蠢哭

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ull unsigned long long

using namespace std;

const int maxn=,inf=1e9,dx[]={-,,,},dy[]={,-,,};

int n,m,K,x,y,z,tot,ans,posx,posy;

int f[][][],from[][][][],cowx[maxn],cowy[maxn],grax[maxn],gray[maxn],get[][];

ull hs[][][],hss;

char anss[];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(m);read(K);

    for(int i=;i<=n;i++)read(cowx[i]),read(cowy[i]);

    for(int i=;i<=m;i++)

    {

        read(grax[i]),read(gray[i]);

        for(int j=;j<=n;j++)

        if(abs(grax[i]-cowx[j])+abs(gray[i]-cowy[j])<=K)

        get[grax[i]-cowx[j]+][gray[i]-cowy[j]+]++;

    }

    memset(f,-,sizeof(f));

    f[][][]=;

    for(int i=;i<=K;i++)

    {

        for(int j=-i;j<=i;j++)

        {

            for(int k=-i;k<=i;k++)

            if(abs(j)+abs(k)<=i)

            {

                for(int l=;l<;l++)

                {

                    int x=j+dx[l],y=k+dy[l];

                    if(f[i-][x+][y+]+get[j+][k+]>f[i][j+][k+]||(f[i-][x+][y+]+get[j+][k+]==f[i][j+][k+]&&hs[i-][x+][y+]*+l<hs[i][j+][k+]))

                    {

                        f[i][j+][k+]=f[i-][x+][y+]+get[j+][k+];

                        from[i][j+][k+][]=x;from[i][j+][k+][]=y;

                        hs[i][j+][k+]=hs[i-][x+][y+]*+l;

                    }

                }

                if(f[i][j+][k+]>ans||(f[i][j+][k+]==ans&&hs[i][j+][k+]<hss))

                {

                    ans=f[i][j+][k+];

                    hss=hs[i][j+][k+];

                    posx=j;posy=k;

                }

            }

        }

    }

    printf("%d\n",ans);

    for(int i=K;i;i--)

    {

        int nx=from[i][posx+][posy+][],ny=from[i][posx+][posy+][];

        if(nx==posx)

        {

            if(ny>posy)anss[i]='S';

            else anss[i]='N';

        }

        else

        {

            if(nx>posx)anss[i]='W';

            else anss[i]='E';

        }

        posx=nx;posy=ny;

    }

    for(int i=;i<=K;i++)printf("%c",anss[i]);

    return ;

}

　　bzoj3126: [Usaco2013 Open]Photo

　　　　噗哈哈看网上的题解全是DP+线段树或者单调队列优化，一眼差分约束，结果写差分约束真的艹过去了233（虽然跑的奇慢

　　　　对于一个区间[l,r]，有条件sum[r]-sum[l-1]==1，可以看成sum[r]-sum[l-1]>=1,sum[r]-sum[l-1]<=1，于是l-1向r连边1，r向l-1连边-1。

　　　　还有约束条件sum[i]-sum[i-1]>=0,sum[i]-sum[i-1]<=1，于是i-1往i连边0，i往i-1连边1。

　　　　然后跑spfa最短路，有负环输出-1，就过了...等会去补个DP做法嘿嘿

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<queue>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct zs{ll dis,pre,too;}e[maxn];

struct poi{ll pos,dis;};

priority_queue<poi>q;

bool operator <(poi a,poi b){return a.dis>b.dis;};

ll to,i,now,n,m,s,t,x,y,z,tot,last[maxn],dis[maxn],mn,mx,ans;

bool v[maxn],flag;

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y,int z){e[++tot].too=y;e[tot].dis=z;e[tot].pre=last[x];last[x]=tot;}

void spfa(int x)

{

    memset(dis,,(n+)<<);dis[x]=;q.push((poi){x,});v[x]=;

    while(!q.empty())

    {

        for(to=e[i=last[now=q.top().pos]].too,q.pop();i;to=e[i=e[i].pre].too)

        if(dis[to]>dis[now]+e[i].dis)

        {

            ans++;

            if(ans>){printf("-1");flag=;return;}

            dis[to]=dis[now]+e[i].dis;

            if(!v[to])v[to]=,q.push((poi){to,dis[to]});

        }

        v[now]=;

    }

}

int main()

{

    read(n);read(m);

    flag=;

    for(int i=;i<=m;i++)

    {

        read(x);read(y);

        add(x-,y,);add(y,x-,-);;

    }

    mn=;mx=n;

    for(int i=mn;i<mx;i++)add(i,i+,),add(i+,i,);

    spfa(mn);

    if(!flag)printf("%lld\n",dis[mx]);

    return ;

}

　　　　写了线段树+DP反而慢了QAQ

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,z,ans;

int l[maxn],r[maxn],a[maxn<<],x[maxn],y[maxn];

inline void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

inline void update(int x,int l,int r,int cx,int delta)

{

    if(l==cx&&r==cx){a[x]=delta;return;}

    int mid=(l+r)>>;

    if(cx<=mid)update(x<<,l,mid,cx,delta);

    if(cx>mid)update(x<<|,mid+,r,cx,delta);

    a[x]=max(a[x<<],a[x<<|]);

}

inline int query(int x,int l,int r,int cl,int cr)

{

    if(cl<=l&&r<=cr)return a[x];

    int mid=(l+r)>>,ret=-inf;

    if(cl<=mid)ret=max(ret,query(x<<,l,mid,cl,cr));

    if(cr>mid)ret=max(ret,query(x<<|,mid+,r,cl,cr));

    return ret;

}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)r[i]=i-;

    for(int i=;i<=m;i++)

    {

        read(x[i]);read(y[i]);

        l[y[i]+]=max(l[y[i]+],x[i]);

        r[y[i]]=min(r[y[i]],x[i]-);

    }

    for(int i=;i<=n;i++)l[i]=max(l[i],l[i-]);

    for(int i=n-;i;i--)r[i]=min(r[i],r[i+]);

    for(int i=;i<=n;i++)

    {

        int sum=l[i]<=r[i]?query(,,n,l[i],r[i])+:-inf;ans=max(ans,sum);

        update(,,n,i,sum);

    }

    for(int i=;i<=m;i++)if(query(,,n,x[i],y[i])<=){puts("-1");return ;}

    printf("%d\n",ans);

    return ;

}

　　bzoj3048: [Usaco2013 Jan]Cow Lineup

　　　　离散化后标尺法（两个指针l和r），保证区间数字种类<=k+1，用最大值更新答案。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,N,k,l,r,cnt,ans;

int a[maxn],b[maxn],cntt[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(k);

    for(int i=;i<=n;i++)read(a[i]),b[i]=a[i];N=n;

    sort(b+,b++N);N=unique(b+,b++N)-b-;

    for(int i=;i<=n;i++)a[i]=lower_bound(b+,b++N,a[i])-b;

    l=;r=;cnt=;

    while(r<n)

    {

        r++;

        if(!cntt[a[r]])cnt++;

        cntt[a[r]]++;

        if(cnt>k+)

        {

            while(cntt[a[l]]!=)cntt[a[l]]--,l++;

            cntt[a[l]]=;l++;

            cnt--;

        }

        if(cntt[a[r]]>ans)ans=cntt[a[r]];

    }

    printf("%d\n",ans);

    return ;

}

　　bzoj2197: [Usaco2011 Mar]Tree Decoration

　　　　久违的金组水题...（MDZZ以后只要空间苟一律开long longQAQ

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int too,pre;}e[maxn];

ll n,fa,mn,tot;

ll ans;

ll c[maxn],nowc[maxn],t[maxn],last[maxn];

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;}

int dfs(int x)

{

    int mn=t[x];

    for(int i=last[x];i;i=e[i].pre)

    mn=min(dfs(e[i].too),mn),nowc[x]-=c[e[i].too];

    if(nowc[x]>)ans+=1ll*nowc[x]*mn;else c[x]-=nowc[x];

    return mn;

}

int main()

{

    read(n);

    for(int i=;i<=n;i++)

    {

        read(fa);read(c[i]);read(t[i]);nowc[i]=c[i];

        if(i!=)add(fa,i);

    }

    dfs();

    printf("%lld\n",ans);

}

　　bzoj3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题

　　　　水题一道就够了怎么来两道啊QAQ

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,v,x,y,z,tot;

int f[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(v);read(n);

    for(int i=;i<=n;i++)

    {

        read(x);

        for(int j=v;j>=x;j--)

        f[j]=max(f[j],f[j-x]+x);

    }

    printf("%d\n",f[v]);

    return ;

}

　　bzoj3887: [Usaco2015 Jan]Grass Cownoisseur

　　　　好题！帮我找出了以前好多的知识漏洞（卡了我好久TAT）

　　　　首先当然是要tarjan缩点。

　　　　预处理1到能到的点记作A集，能到1的点到1记作B集，并bfs求出1到A集，B集到1的最长路，枚举每一条边，如果端点分别是A集和B集，那么就把这条边，反向，两条最长路加起来更新答案。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int x,too,pre;}e[maxn*],e2[maxn*],e3[maxn*];

int n,m,x,y,z,tot,tott,tot2,tot3,top,color,ans;

int len1[maxn],len2[maxn],dfn[maxn],low[maxn],st[maxn],lack[maxn],col[maxn],num[maxn],last[maxn],last2[maxn],last3[maxn],v[maxn],h[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y){e[++tot].x=x;e[tot].too=y;e[tot].pre=last[x];last[x]=tot;}

void add2(int x,int y){e2[++tot2].x=x;e2[tot2].too=y;e2[tot2].pre=last2[x];last2[x]=tot2;}

void add3(int x,int y){e3[++tot3].x=x;e3[tot3].too=y;e3[tot3].pre=last3[x];last3[x]=tot3;}

void tarjan(int x)

{

    dfn[x]=low[x]=++tott;st[++top]=x;lack[x]=top;

    for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)

    if(!dfn[too])tarjan(too),low[x]=min(low[x],low[too]);

    else if(!col[too])low[x]=min(low[x],dfn[too]);

    if(dfn[x]==low[x])for(color++;top>=lack[x];top--)col[st[top]]=color,num[color]++;

}

void dfs1(int x)

{

    v[x]=;

    for(int i=last2[x],too=e2[i].too;i;i=e2[i].pre,too=e2[i].too)dfs1(too);

}

void dfs2(int x)

{

    v[x]=;

    for(int i=last3[x],too=e3[i].too;i;i=e3[i].pre,too=e3[i].too)dfs2(too);

}

void bfs1()

{

    top=;

    int front=,rear=;h[]=col[];len1[col[]]=num[col[]];

    while(front!=rear)

    {

        int now=h[++front];if(front==maxn)front=-;

        for(int i=last2[now];i;i=e2[i].pre)

        {

            h[++rear]=e2[i].too;if(rear==maxn)rear=-;

            len1[e2[i].too]=max(len1[e2[i].too],len1[now]+num[e2[i].too]);

        }

    }

}

void bfs2()

{

    top=;

    int front=,rear=;h[]=col[];len2[col[]]=num[col[]];

    while(front!=rear)

    {

        int now=h[++front];if(front==maxn)front=-;

        for(int i=last3[now];i;i=e3[i].pre)

        {

            h[++rear]=e3[i].too;if(rear==maxn)rear=-;

            len2[e3[i].too]=max(len2[e3[i].too],len2[now]+num[e3[i].too]);

        }

    }

}

int main()

{

    read(n);read(m);

    for(int i=;i<=m;i++)read(x),read(y),add(x,y);

    for(int i=;i<=n;i++)if(!dfn[i])tarjan(i);

    for(int i=;i<=tot;i++)if(col[e[i].x]!=col[e[i].too])add2(col[e[i].x],col[e[i].too]),add3(col[e[i].too],col[e[i].x]);

    dfs1(col[]);dfs2(col[]);

    bfs1();bfs2();

    ans=*num[col[]];

    for(int i=;i<=tot2;i++)

    {

        if((v[e2[i].x]==||e2[i].x==col[])&&(v[e2[i].too]==||e2[i].too==col[]))

        ans=max(ans,len2[e2[i].x]+len1[e2[i].too]);

    }

    printf("%d\n",ans-num[col[]]);

    return ;

}

　　bzoj1727: [Usaco2006 Open]The Milk Queue 挤奶队列

　　　　不会...知道是贪心但是不会贪...题解好喵喵啊

　　　　直接搬Oakley_的题解好了。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{int x,y;}a[maxn];

int n,m,x,y,z,tot;

ll ans,sum,rest;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool cmp(poi a,poi b){return min(a.x,b.y)<min(a.y,b.x);}

int main()

{

    read(n);

    for(int i=;i<=n;i++)read(a[i].x),read(a[i].y),sum+=a[i].y;

    sort(a+,a++n,cmp);

    for(int i=;i<=n;i++)

    {

        if(a[i].x<=rest)rest-=a[i].x;

        else ans+=a[i].x-rest,rest=;

        rest+=a[i].y;

    }

    printf("%lld\n",ans+sum);

    return ;

}

　　bzoj3312: [Usaco2013 Nov]No Change

　　　　看见K<=16就知道要状压DP了...

　　　　f[i]表示硬币状态为i最多能买多少东西。

　　　　f[i]=max(f[i^(1<<(j-1))])+硬币 j 能买接下来的几件东西，二分一波就好了嗯

　　　　又忘记输出-1 WA了一次QAQ

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,k,x,y,z,tot,ans,state;

int coin[maxn],sum[maxn],f[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(k);read(n);

    for(int i=;i<=k;i++)read(coin[i]);

    for(int i=;i<=n;i++)read(sum[i]),sum[i]+=sum[i-];

    state=(<<k)-;memset(f,-,(state+)<<);

    f[]=;

    for(int i=;i<=state;i++)

    {

        for(int j=;j<=k;j++)

        if((i&(<<(j-)))==(<<(j-)))

        {

            int l=f[i^(<<(j-))]+,r=n,summ=sum[l-];

            while(l<r)

            {

                int mid=(l+r+)>>;

                if(sum[mid]-summ<=coin[j])l=mid;

                else r=mid-;

            }

            f[i]=max(f[i],l);

        }

    }

    ans=-inf;

    for(int i=;i<=state;i++)

    {

        if(f[i]!=n)continue;

        int rest=;

        for(int j=;j<=k;j++)

        if(!(i&(<<(j-))))rest+=coin[j];

        ans=max(ans,rest);

    }

    printf("%d\n",ans!=-inf?ans:-);

    return ;

}

　　bzoj2272: [Usaco2011 Feb]Cowlphabet 奶牛文字

　　　　一眼题...因为一个sb错误错了好久（虽然要是没这个错我不会发现自己模数写错两次T_T（1e9+7->987654321->97654321

　　　　f[i][j][k]表示有i个大写字母，j个小写字母，最后一位是k的方案数。注意这个不能和背包一样写。。因为有了那最后一维...

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9,mod=;

int n,u,l,tot,ans;

int f[][][];

char s[][];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool is1(char ch){return (ch<='Z'&&ch>='A');}

bool is2(char ch){return (ch<='z'&&ch>='a');}

int up(int x){return is1(s[x][])+is1(s[x][]);}

int low(int x){return is2(s[x][])+is2(s[x][]);}

int main()

{

    read(u);read(l);read(n);

    for(int i=;i<=n;i++)scanf("%s",s[i]+);

    for(int i=;i<=n;i++)f[up(i)][low(i)][s[i][]]++;

    for(int j=;j<=u;j++)

    for(int k=;k<=l;k++)

    if(j+k>)

    for(int i=;i<=n;i++)

    {

        if(j<is1(s[i][])||k<is2(s[i][]))continue;

                f[j][k][s[i][]]+=f[j-is1(s[i][])][k-is2(s[i][])][s[i][]];

        f[j][k][s[i][]]>=mod&&(f[j][k][s[i][]]-=mod);

    }

    for(int j=;j<=;j++)

    ans+=f[u][l]['a'+j],ans>=mod&&(ans-=mod),ans+=f[u][l]['A'+j],ans>=mod&&(ans-=mod);

    printf("%d\n",ans);

    return ;

}

　　bzoj1750: [Usaco2005 qua]Apple Catching

　　　　一眼题*2....f[i][j][0/1]表示第i分钟，走了j次，在第1/2棵树下的最大收益

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,w,x,y,z,tot,ans;

int f[][][],a[];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(w);

    for(int i=;i<=n;i++)read(a[i]);

    for(int i=;i<=n;i++)

    {

        f[i][][]=f[i-][][]+(a[i]==);

        f[i][][]=f[i-][][]+(a[i]==);

        ans=max(ans,max(f[i][][],f[i][][]));

        for(int j=;j<=min(i,w);j++)

        {

            f[i][j][]=max(f[i-][j][],f[i-][j-][])+(a[i]==);

            f[i][j][]=max(f[i-][j][],f[i-][j-][])+(a[i]==);

            ans=max(ans,max(f[i][j][],f[i][j][]));

        }

    }

    printf("%d\n",ans);

    return ;

}

　　bzoj1736: [Usaco2005 jan]The Wedding Juicer 婚宴的榨汁机

　　　　从四周向中间宽搜，每次出队高度最小的点，并记录来的路上的最大值，拿这个最大值减去当前高度，求和就是答案了。

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9,dx[]={,,,-},dy[]={,,-,};

struct poi{int x,y,h;};

priority_queue<poi>q;

bool operator<(poi a,poi b){return a.h>b.h;}

int n,m,x,y,z,tot;

int h[maxn][maxn];

bool v[maxn][maxn];

ll ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void bfs()

{

    while(!q.empty())

    {

        poi now=q.top();q.pop();

        for(int i=;i<;i++)

        {

            int xx=now.x+dx[i],yy=now.y+dy[i];

            if(xx<||xx>n||yy<||yy>m||v[xx][yy])continue;

            if(h[xx][yy]<now.h)

            {

                ans+=now.h-h[xx][yy];

                h[xx][yy]=now.h;

            }

            v[xx][yy]=;q.push((poi){xx,yy,h[xx][yy]});

        }

    }

}

int main()

{

    read(m);read(n);

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    read(h[i][j]);

    for(int i=;i<=m;i++)

    q.push((poi){,i,h[][i]}),q.push((poi){n,i,h[n][i]}),v[][i]=,v[n][i]=;

    for(int i=;i<n;i++)

    q.push((poi){i,,h[i][]}),q.push((poi){i,m,h[i][m]}),v[i][]=,v[i][m]=;

    bfs();printf("%lld\n",ans);

    return ;

}

　　bzoj1779: [Usaco2010 Hol]Cowwar 奶牛战争

　　　　刷了几题银组刷不下去了。。还是回来刷金组吧TAT

　　　　看这数据范围完全想不到网络流啊，后来才知道如果容量全部为1的话dinic的效率实际上是O(min(n^(2/3),m^(1/2))*m)...所以能跑过

　　　　四分图。

　　　　源点连所有J，J连所有走一步能到的不是T的点和自己所在的点，这些点拆成i和i'，连边，i'和所有相邻的T连边，T和汇点连边，容量都是1，跑最大流。

#include<iostream>

#include<cstdlib>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

using namespace std;

const int inf=1e9,maxn=;

struct poi{int too,pre,cf;}e[],e2[];

int n,m,tot,tot2,ans,x,y,z,front,rear,sum;

int h[maxn],v[maxn],last[maxn],last2[maxn],dis[maxn],cur[maxn];

char s[maxn];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void add(int x,int y)

{

    e[++tot].too=y;e[tot].cf=;e[tot].pre=last[x];last[x]=tot;

    e[++tot].too=x;e[tot].pre=last[y];last[y]=tot;

}

void add2(int x,int y){e2[++tot2].too=y;e2[tot2].pre=last2[x];last2[x]=tot2;}

bool bfs()

{

    for(int i=;i<=sum;i++)v[i]=,dis[i]=-;

    dis[]=;v[]=;h[]=;front=;rear=;

    while(front!=rear)

    {

        int now=h[++front];if(front==maxn)front=-;

        for(int i=last[now];i;i=e[i].pre)

        {

            int too=e[i].too;

            if((!v[too])&&e[i].cf)

            {

                dis[too]=dis[now]+;if(too==sum)return ;

                v[too]=;h[++rear]=too;if(rear==maxn)rear=-;

            }

        }

    }

    return ;

}

int dfs(int x,int f)

{

    int flow=,tmp;

    if(x==sum)return f;

    for(int &i=cur[x];i;i=e[i].pre)

    {

        int too=e[i].too;

        if(dis[too]==dis[x]+&&e[i].cf)

        {

            tmp=dfs(too,min(f-flow,e[i].cf));

            e[i].cf-=tmp;e[i^].cf+=tmp;flow+=tmp;

            if(f==flow)return f;

        }

    }

    return flow;

}

void dinic()

{

    while(bfs())

    {

        for(int i=;i<=sum;i++)cur[i]=last[i];

        ans+=dfs(,inf);

    }

}

int main()

{

    tot=;

    read(n);read(m);sum=(n<<)+;

    scanf("%s",s+);

    for(int i=;i<=m;i++)read(x),read(y),add2(x,y),add2(y,x);

    for(int i=;i<=n;i++)

    {

        if(s[i]=='J')

        {

            add(,i);add(i,i+n);add(i+n,i+(n<<));

            for(int j=last2[i],too=e2[j].too;j;j=e2[j].pre,too=e2[j].too)

            if(s[too]!='T')add(i,too+n);

        }

        else if(s[i]!='T')add(i+n,i+(n<<));

        if(s[i]=='T')

        {

            add(i+n*,sum);

            for(int j=last2[i],too=e2[j].too;j;j=e2[j].pre,too=e2[j].too)

            add(too+(n<<),i+n*);

        }

    }

    dinic();

    printf("%d\n",ans);

    return ;

}

　　bzoj4094: [Usaco2013 Dec]Optimal Milking

　　　　一眼题。。。线段树维护选左边右边，左边，右边，不选的最大值。

　　　　一开始没开long long WA了一发，改完交就AC了，好爽（假·1A

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

struct poi{ll lr,l,r,none;}a[maxn*];

ll n,m,x,y,z,tot;

ll ans;

void read(ll &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

void pushup(int x,int l,int r)

{

    if(l==r)return;

    a[x].lr=max(a[x<<].l+a[x<<|].r,max(a[x<<].lr+a[x<<|].r,a[x<<].l+a[x<<|].lr));

    a[x].l=max(a[x<<].l+a[x<<|].l,max(a[x<<].l+a[x<<|].none,a[x<<].lr+a[x<<|].none));

    a[x].r=max(a[x<<].r+a[x<<|].r,max(a[x<<].none+a[x<<|].r,a[x<<].none+a[x<<|].lr));

    a[x].none=max(a[x<<].r+a[x<<|].none,max(a[x<<].none+a[x<<|].l,a[x<<].none+a[x<<|].none));

}

void build(int x,int l,int r)

{

    if(l==r){read(a[x].lr);return;}

    int mid=(l+r)>>;

    build(x<<,l,mid);build(x<<|,mid+,r);

    pushup(x,l,r);

}

void update(int x,int l,int r,int cx,int delta)

{

    if(l==cx&&r==cx){a[x].lr=delta;return;}

    int mid=(l+r)>>;

    if(cx<=mid)update(x<<,l,mid,cx,delta);

    if(cx>mid)update(x<<|,mid+,r,cx,delta);

    pushup(x,l,r);

}

int main()

{

    read(n);read(m);build(,,n);

    for(int i=;i<=m;i++)

    {

        read(x);read(y);

        update(,,n,x,y);

        ans+=max(a[].lr,max(a[].none,max(a[].l,a[].r)));

    }

    printf("%lld\n",ans);

    return ;

}

　　bzoj3886: [Usaco2015 Jan]Moovie Mooving

　　　　很早就写了一直懒得写题解....

　　　　状压DP f[i]表示电影的状态为i最多能看多长时间，随便转移

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,ans,l,r,mid,L,cnt;

int f[],len[maxn],num[maxn],a[maxn][maxn*];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

bool check(int i,int x){return a[i][mid]<=x+;}

int main()

{

    read(n);read(L);

    for(int i=;i<=n;i++)

    {

        read(len[i]);read(num[i]);

        for(int j=;j<=num[i];j++)

        read(a[i][j]);

    }

    memset(f,-,sizeof(f));f[]=;ans=inf;

    for(int i=;i<(<<n);i++)

    {

        cnt=;

        for(int j=;j<=n;j++)

        if(!(i&(<<(j-))))

        {

            cnt++;

            l=;r=num[j];

            while(l<r)

            {

                mid=(l+r+)>>;

                if(check(j,f[i]))l=mid;

                else r=mid-;

            }

            if(!l)continue;

            f[i|(<<(j-))]=max(f[i|(<<(j-))],a[j][l]+len[j]);

        }

        if(f[i]>=L)ans=min(ans,n-cnt);

    }

    printf("%d\n",ans!=inf?ans:-);

    return ;

}

　　bzoj1915: [Usaco2010 Open]奶牛的跳格子游戏

　　　　DP+单调队列优化

　　　　f[i]表示去的时候跳到i，回来的时候跳到i-1的最大收益。预处理sum表示所有正数的前缀和（因为一个可以自由跳的区间内负数一定不取

　　　　f[i] =max(f[j] + a[i] + a[i-1] + sum[i-2] - sum[j]) {1<=j<i-1&&i-j<=k)

　　　　每次把f[i-1]-sum[i-1]加入单调队列就行了。

　　　　交了5发因为空间开太大没艹上#1....丢人

　　　　#2也是不错的嘿嘿

　　bzoj4393: [Usaco2015 Dec]Fruit Feast

　　　　果然新题如果AC人数少就肯定是水题了...

　　　　显然只有四种情况，不喝水，吃A喝水，吃B喝水，吃AB喝水，记得判一下饱涨值够不够吃

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,n1,n2,n3,A,B,a,b,ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);read(A);read(B);

    a=A>>;b=B>>;

    n1=n-a;n2=n-b;n3=n-a-b;

    for(int i=;i<=n/A;i++)

    ans=max(ans,i*A+B*((n-i*A)/B));

    if(n>=A)

    for(int i=;i<=n1/A;i++)

    ans=max(ans,i*A+B*((n1-i*A)/B)+a);

    if(n>=B)

    for(int i=;i<=n2/A;i++)

    ans=max(ans,i*A+B*((n2-i*A)/B)+b);

    if(n>=A+B)

    for(int i=;i<=n3/A;i++)

    ans=max(ans,i*A+B*((n3-i*A)/B)+a+b);

    printf("%d\n",ans);

    return ;

}

　　bzoj4580: [Usaco2016 Open]248

　　　　久违的1A........

　　　　嗯这题又印证了上题题解的第一句话

　　　　区间DP，f[l][r]=max(f[l][r],f[l][k]+1) (f[l][k]==f[k+1][r])

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#define ll long long

using namespace std;

const int maxn=,inf=1e9;

int n,m,x,y,z,tot,ans;

int f[][];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int main()

{

    read(n);

    memset(f,-,sizeof(f));

    for(int i=;i<=n;i++)read(f[i][i]);

    for(int i=;i<=n;i++)

    for(int j=;i+j-<=n;j++)

    {

        int L=j,R=i+j-;

        for(int k=L;k<R;k++)

        if(f[L][k]==f[k+][R]&&f[L][k]!=-)

        f[L][R]=max(f[L][R],f[L][k]+);

        ans=max(ans,f[L][R]);

    }

    printf("%d\n",ans);

    return ;

}

　　bzoj3939: [Usaco2015 Feb]Cow Hopscotch

　　　　f[i][j]=sigma(f[k][l]) {k<i&&l<j}

　　　　我们让每一次转移都求出相同颜色的方案数，再用总方案数减去就行了。注意是每一次转移都要被总方案数减，否则相当于这条路径上全部都相同，这样的补集是至少有一个不同而不是全都不同。

　　　　显然这个DP方程就是统计一个前缀的和，对每个颜色建一棵线段树动态开点+扫描线就好了。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int maxn=,inf=1e9,mo=1e9+;

struct poi{int sum;}a[maxn*maxn*];

int n,m,K,cnt,cl,cr,cx;

int col[maxn][maxn],tot[maxn][maxn],sum[maxn][maxn],rt[maxn*maxn*],lt[maxn*maxn*],f[maxn][maxn],root[maxn*maxn*];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

inline int mod(int x){return x>=mo?x-mo:x;}

void update(int &x,int l,int r,int delta)

{

    if(!x)x=++cnt;a[x].sum=mod(a[x].sum+delta);

    if(l==r)return;

    int mid=(l+r)>>;

    if(cx<=mid)update(lt[x],l,mid,delta);

    else update(rt[x],mid+,r,delta);

}

int query(int x,int l,int r)

{

    if(!x)return ;

    if(cl<=l&&r<=cr)return a[x].sum;

    int mid=(l+r)>>,ret=;

    if(cl<=mid)ret+=query(lt[x],l,mid);

    if(cr>mid)ret+=query(rt[x],mid+,r);

    ret=mod(ret);return ret;

}

int main()

{

    read(n);read(m);read(K);

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    read(col[i][j]);

    sum[][]=f[][]=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            if(i==&&j==)continue;

            cl=,cr=j-;

            f[i][j]=mod(sum[i-][j-]+mo-query(root[col[i][j]],,m));

            sum[i][j]=(1ll*sum[i][j-]+1ll*sum[i-][j]-1ll*sum[i-][j-]+1ll*f[i][j]+mo)%mo;

        }

        for(int j=;j<=m;j++)

        cx=j,update(root[col[i][j]],,m,f[i][j]);

    }

    printf("%d\n",f[n][m]);

}

　　bzoj1737: [Usaco2005 jan]Naptime 午睡时间

　　　　不考虑环的话则有 f[i][j][1]=max(f[i-1][k][1]+a[j],f[i-1][k][0]){k<j}

　　　　　　　　　　　　 f[i][j][0]=max(f[i-1][k][1],f[i-1][k][0])

　　　　　　　　　　　　初始状态f[1][1][1]=f[1][0][0]=0;

　　　　对于环多考虑一种跨环的情况，也就是1必须睡觉，强制跨环的话初始状态为f[1][1][1]=0 最后答案为f[n][m][1]+a[1]

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=,inf=1e9;

int n,m,ans;

int a[maxn],f[][maxn][];

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int max(int a,int b){return a>b?a:b;}

int main()

{

    read(n);read(m);

    for(int i=;i<=n;i++)read(a[i]);

    memset(f,,sizeof(f));

    f[][][]=f[][][]=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            if(j)f[i&][j][]=max(f[(i&)^][j-][],f[(i&)^][j-][]+a[i]);

            f[i&][j][]=max(f[(i&)^][j][],f[(i&)^][j][]);

        }

        ans=max(ans,max(f[i&][m][],f[i&][m][]));

    }

    memset(f,,sizeof(f));

    f[][][]=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            if(j)f[i&][j][]=max(f[(i&)^][j-][],f[(i&)^][j-][]+a[i]);

            f[i&][j][]=max(f[(i&)^][j][],f[(i&)^][j][]);

        }

    }

    ans=max(ans,f[n&][m][]+a[]);

    printf("%d\n",ans);

}

bzoj Usaco补完计划(优先级 Gold>Silver>资格赛)

bzoj Usaco补完计划(优先级 Gold>Silver>资格赛)的相关教程结束。

相关推荐

[转]Mysql中的SQL优化与执行计划

bzoj千题计划162：bzoj2006: [NOI2010]超级钢琴

[UR #14]人类补完计划

TiDB与MySQL的SQL差异及执行计划简析

TiDB与MySQL的SQL差异及执行计划简析

【C语言】函数指针与回调函数

NOIP 2021 备战计划

MySql中执行计划如何来的——Optimizer Trace