2019 7 8 HL 模拟赛

　　今天很不爽昨天晚上没有睡好觉大约2点才睡着吧反正翻来覆去睡不着不知道为什么可能可行流或者可行费用流并没有深刻理解。我不会写让我心情非常的焦躁。

大凶顺理成章的被3位强者吊着锤（妈呀我想吊锤他们啊。。

第一题哇这不是求两点之间的最短路径么？圆方树直接上啊。。好像正解不需要但是多了也不多。

然后成功挂掉了可能心情很烦躁然后没有多想直接样例过了丢了没管

犯得错误是没有输出0 直接输出换行了然后应该输出0再输出换行的真菜题都没读清。

还有一点是输出0了没输出换行真菜这都不知道哎结果挂掉一堆分数要不应该能得到一个自己满意的成绩第一题挂彩了。

//#include<bits/stdc++.h>

#include<iomanip>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<deque>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<stack>

#include<algorithm>

#include<vector>

#include<cctype>

#include<utility>

#include<set>

#include<bitset>

#include<map>

#define INF 1000000000

#define ll long long

#define min(x,y) ((x)>(y)?(y):(x))

#define max(x,y) ((x)>(y)?(x):(y))

#define RI register ll

#define db double

#define EPS 1e-8

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const int MAXN=<<,maxn=MAXN<<;

//m<=2n 且双向边 加上方边 空间8倍

int T;

int n,m,num,cnt,top,len,len1,t,h,flag;

int s[maxn],q[maxn],vis[maxn],pre[maxn];

int lin[maxn],ver[maxn],nex[maxn];

int dfn[maxn],low[maxn];

int lin1[maxn],ver1[maxn],nex1[maxn];

inline void add(int x,int y)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

}

inline void add1(int x,int y)

{

    ver1[++len1]=y;

    nex1[len1]=lin1[x];

    lin1[x]=len1;

}

inline void tarjan(int x)

{

    dfn[x]=low[x]=++num;

    s[++top]=x;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(!dfn[tn])

        {

            tarjan(tn);

            low[x]=min(low[x],low[tn]);

            if(low[tn]==dfn[x])

            {

                ++cnt;

                for(int y=;y!=tn;--top)

                {

                    y=s[top];

                    add1(cnt,y);

                    add1(y,cnt);

                }

                add1(x,cnt);

                add1(cnt,x);

            }

        }

        else low[x]=min(low[x],dfn[tn]);

    }

}

inline void bfs()

{

    t=h=;

    memset(vis,,sizeof(vis));

    q[++t]=n;s[t]=;

    while(h++<t)

    {

        int x=q[h];vis[x]=;

        if(x==)return;

        for(int i=lin1[x];i;i=nex1[i])

        {

            int tn=ver1[i];

            if(vis[tn])continue;

            pre[tn]=x;q[++t]=tn;

            s[t]=s[h]+(tn<=n?:);

        }

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    freopen("home.in","r",stdin);

    freopen("home.out","w",stdout);

    T=read();

    while(T--)

    {

        len=len1=top=num=cnt=flag=;

        memset(lin1,,sizeof(lin1));

        memset(lin,,sizeof(lin));

        memset(dfn,,sizeof(dfn));

        n=read();m=read();cnt=n;

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

        {

            int x,y;

            x=read();y=read();

            if(x==y)continue;

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

            if(x==&&y==n)flag=;

            if(y==&&x==n)flag=;

        }

        tarjan();

        if(!dfn[n]||flag){printf("%d\n",);puts("");continue;}

        bfs();--s[h];

        //cout<<h<<' '<<s[h]<<endl;

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

        if(!s[h]){puts("");continue;}

        memset(vis,,sizeof(vis));

        int x=pre[];

        while(x!=n)

        {

            vis[x]=;

            x=pre[x];

        }

        int last=;

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

            if(vis[i])

            {

                if(last)printf("%d ",last);

                last=i;

            }

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

    }

    return ;

}

第二题植物大战僵尸可还行题目比较复杂把模型拿出来就比较简单了注意判环即可。没挂还好。这个不对劲的人终于获得了欣慰。

//#include<bits/stdc++.h>

#include<iomanip>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<deque>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<stack>

#include<algorithm>

#include<vector>

#include<cctype>

#include<utility>

#include<set>

#include<bitset>

#include<map>

#define INF 1000000000

#define ll long long

#define min(x,y) ((x)>(y)?(y):(x))

#define max(x,y) ((x)>(y)?(x):(y))

#define RI register ll

#define db double

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

//空间只有64MB

const int MAXN=,maxn=MAXN*MAXN*MAXN*MAXN;

int n,m,cnt,len,t,h,S,T,len1=,sum,maxflow;

int pos[MAXN][MAXN];

int a[MAXN*MAXN],vis[MAXN*MAXN];

int ru[MAXN*MAXN],q[MAXN*MAXN];

int lt[MAXN*MAXN],vt[maxn],nt[maxn];

int lin[MAXN*MAXN],ver[maxn<<],nex[maxn<<],e[maxn<<];

inline void add(int x,int y)

{

    vt[++len]=y;nt[len]=lt[x];lt[x]=len;

}

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

{

    ver[++len1]=y;nex[len1]=lin[x];lin[x]=len1;e[len1]=z;

    ver[++len1]=x;nex[len1]=lin[y];lin[y]=len1;e[len1]=;

}

inline void topsort()

{

    t=h=;

    for(int i=;i<=cnt;++i)if(ru[i]==)q[++t]=i;

    while(h++<t)

    {

        int x=q[h];

        for(int i=lt[x];i;i=nt[i])

        {

            int tn=vt[i];

            --ru[tn];

            add(tn,x,INF);

            if(!ru[tn])q[++t]=tn;

        }

    }

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

    {

        if(ru[i])continue;

        if(a[i]<)add(i,T,-a[i]);

        else add(S,i,a[i]),sum+=a[i];

    }

}

inline int bfs()

{

    memset(vis,,sizeof(vis));

    t=h=;q[++t]=S;vis[S]=;

    while(h++<t)

    {

        int x=q[h];

        for(int i=lin[x];i;i=nex[i])

        {

            int tn=ver[i];

            if(!e[i]||vis[tn])continue;

            vis[tn]=vis[x]+;

            q[++t]=tn;

            if(tn==T)return ;

        }

    }

    return ;

}

inline int dinic(int x,int flow)

{

    if(x==T)return flow;

    int rest=flow,k;

    for(int i=lin[x];i&&rest;i=nex[i])

    {

        int tn=ver[i];

        if(vis[tn]==vis[x]+&&e[i])

        {

            k=dinic(tn,min(e[i],rest));

            if(!k){vis[tn]=;continue;}

            e[i]-=k;e[i^]+=k;rest-=k;

        }

    }

    return flow-rest;

}

int main()

{

    //freopen("1.in","r",stdin);

    freopen("B.in","r",stdin);

    freopen("B.out","w",stdout);

    n=read();m=read();

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

        for(int j=;j<=m;++j)pos[i][j]=++cnt;

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

    {

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

        {

            a[pos[i][j]]=read();

            if(j>)

            {

                add(pos[i][j],pos[i][j-]);

                ++ru[pos[i][j-]];

            }

            int w=read();

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

            {

                int x,y;

                x=read()+;y=read()+;

                ++ru[pos[x][y]];

                add(pos[i][j],pos[x][y]);

            }

        }

    }

    S=cnt+;T=S+;

    topsort();

    int flow=;

    while(bfs())while((flow=dinic(S,INF)))maxflow+=flow;

    printf("%d\n",max(,sum-maxflow));

    return ;

}

第三题区间操作感觉是一流对多流？好像不太行仔细发现还是可以差分的变成单点操作。

发现是一张二分图我是差分后想到了二分一个值区间最小值然后维护整个区间都>=二分这个值即可。

然后乱建边最后发现好像是个单峰函数事实上这已经是我的败笔了因为单峰函数一出现三分随之而来且非常不好写应该停下但是我仍然刚了1h 然后最后无奈拿到30分的辛苦分。我服了。

因为根本不需要知道那个最小值是多少因为第一个值好像没什么卵用。只要后面的数比这个数大就好了二分或者三分这个值意义并不大。

下面说中午我稍微思考了一下想到的正解真的比较简单。对于一个差分过后数列来说我想到的是每一个位置上的数字如果小于0的话一定是不和法的我们期望的是将这个序列上的所有数字都>=0这样就好了，

观察+操作发现l+1 (r+1)-1 这样 r如果是正数其实就是负数向正数要1 显然正数和负数形成了二分图具体做法就是这样。显然对于一个负数是拥有下界全部连向源点下界成功被转换了。

再跑费用流即可。

//#include<bits/stdc++.h>

#include<iomanip>

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<deque>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<stack>

#include<algorithm>

#include<vector>

#include<cctype>

#include<utility>

#include<set>

#include<bitset>

#include<map>

#define INF 1000000000

#define ll long long

#define min(x,y) ((x)>(y)?(y):(x))

#define max(x,y) ((x)>(y)?(x):(y))

#define RI register ll

#define db double

#define EPS 1e-8

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const ll MAXN=,maxn=MAXN*MAXN<<;

ll n,m,minn=INF,maxx,S,T,T1,len=,h,t1,p;

ll a[MAXN],b[MAXN];

ll pre[MAXN],in[MAXN],vis[MAXN],q[maxn<<],dis[maxn];

ll lin[MAXN],ver[maxn<<],nex[maxn<<],e[maxn<<],e1[maxn<<];

struct wy

{

    ll op,l,c;

}t[MAXN];

inline void add(ll x,ll y,ll z,ll z1)

{

    ver[++len]=y;nex[len]=lin[x];lin[x]=len;e[len]=z;e1[len]=z1;

    ver[++len]=x;nex[len]=lin[y];lin[y]=len;e[len]=;e1[len]=-z1;

}

inline ll spfa()

{

    for(ll i=;i<=T;++i)dis[i]=INF;

    h=t1=;

    dis[S]=;vis[S]=;in[S]=INF;q[++t1]=S;

    while(h++<t1)

    {

        ll x=q[h];vis[x]=;

        for(ll i=lin[x];i;i=nex[i])

        {

            ll tn=ver[i];

            if(!e[i])continue;

            if(dis[tn]>dis[x]+e1[i])

            {

                dis[tn]=dis[x]+e1[i];

                in[tn]=min(in[x],e[i]);

                pre[tn]=i;

                if(!vis[tn])q[++t1]=tn,vis[tn]=;

            }

        }

    }

    return dis[T]!=INF;

}

inline ll EK()

{

    ll maxflow=,sum=;

    while(spfa())

    {

        ll x=T,i=pre[x];

        sum+=dis[x]*in[T];

        maxflow+=in[T];

        while(x!=S)

        {

            e[i]-=in[T];

            e[i^]+=in[T];

            x=ver[i^];i=pre[x];

        }

    }

    if(maxflow!=p)return -;

    return sum;

}

int main()

{

    //freopen("1.in","r",stdin);

    freopen("seq.in","r",stdin);

    freopen("seq.out","w",stdout);

    n=read();m=read();T1=n+;S=T1+;T=S+;

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

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

    {

        char op;ll x,y;

        op=getc();

        while(op==' '||op=='\n')op=getc();

        x=read();y=read();

        t[i]=(wy){op=='-'?:,x,y};

    }

    if(n==){printf("%d\n",);return ;}

    for(ll i=;i<=n;++i)b[i]=a[i]-a[i-];

    b[T1]=INF;

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

    {

        if(b[i]>)add(i,T,b[i],);

        else add(S,i,-b[i],),p+=-b[i];

    }

    add(,T,INF,);

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

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

        {

            if(t[j].op)

            {

                ll l=i,r=i+t[j].l;

                if(r>T1)continue;

                add(l,r,INF,t[j].c);

            }

            else

            {

                ll l=i,r=l+t[j].l;

                if(r>T1)continue;

                add(r,l,INF,t[j].c);

            }

        }

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

    return ;

}

GG 总有一天我将会AK的（突然WN附体嘻嘻。

巴特西

2019 7 8 HL 模拟赛

最新文章

热门文章