难度:省选?

Problem A: Maze

题意:

考虑一个n*m的网格,每个网格要么是空的,要么是障碍物。整个网格四周都是墙壁(即第1行和第n行,第1列和第m列都是墙壁),墙壁有且仅有两处开口,分别代表起点和终点。起点总是在网格左边,终点总是在网格右边。你只能朝4个方向移动:上下左右。数据保证从起点到终点至少有一条路径。

从起点到终点可能有很多条路径,请找出有多少个网格是所有路径的必经网格。

n,m \leq 1000

题解:

我是先建无向图,跑一遍割点,从s开始跑,特判t是否在割点的子树中。

解法2不会证。

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 2005
using namespace std;
il ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int t,nt;
}e[Max*Max*4];
int head[Max*Max],tot;
il void add2(int u,int v)
{
    e[++tot].t=v;
    e[tot].nt=head[u];
    head[u]=tot;
}
il void add(int u,int v)
{
    //cout<<u<<' '<<v<<endl;
    add2(u,v),add2(v,u);
}
int n,m,s,t,dfn[Max*Max],low[Max*Max],cut[Max*Max],cnt,ans,sn[Max*Max];
il void tarjan(int u)
{
    //cout<<u<<endl;
    if(u==t) sn[u]=1;
    dfn[u]=low[u]=++cnt;
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
            sn[u]|=sn[v];
            if(low[v]>=dfn[u]&&u!=s&&u!=t&&sn[v]) cut[u]=1;
        }
        low[u]=min(low[u],dfn[v]);
    }
}
char mp[Max][Max];
int tx[4]={0,-1,1,0};
int ty[4]={1,0,0,-1};
signed main()
{
    //freopen("A.in","r",stdin);
    n=read(),m=read();
    s=n*m+1,t=n*m+2;
    //puts("qwq");
    for(int i=1;i<=n;i++)
    {
        scanf("%s",mp[i]+1);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(mp[i][j]=='.')
            {
                int id=(i-1)*(m)+j;
                if(j==1) add(s,id);
                if(j==m) add(t,id);
                for(int k=0;k<=3;k++)
                {
                    int nx=i+tx[k],ny=j+ty[k];
                    if(nx<1||ny<1||nx>n||ny>m||mp[nx][ny]=='#') continue;
                    int idn=(m)*(nx-1)+ny;
                    add(id,idn);
                }
            }
        }
    }
    //puts("qwq");
    tarjan(s);
    //puts("qwq");
    for(int i=1;i<=n*m;i++) if(cut[i]) ans++;
    cout<<ans<<endl;
}

Problem B: 懒人跑步

题意:

T \leq 10

题解:

很神奇的一题。

先找一个最短的跑完能回到2的路,对长度建立一个剩余系跑最短路。

我这辈子都想不到的做法。

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 300005
#define int long long
#define inf 1926081711451419810ll
#define dg puts("qwq")
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int d[4][Max],n,ans,k,l[4],w,vst[4][Max];
struct node
{
    int x,id;
};
queue<node> q;
il void spfa()
{
    for(int i=0;i<4;i++)
        for(int j=0;j<w;j++)
            d[i][j]=inf,vst[i][j]=0;
    while(!q.empty()) q.pop();
    q.push((node){0,1});
    d[1][0]=0;
    node qwq;
    while(!q.empty())
    {
        //dg;
        qwq=q.front(),q.pop();
        int v=qwq.id,wt=qwq.x;
        int u=(v+1)%4,nw=(wt+l[v])%w;
        if(d[u][nw]>d[v][wt]+l[v])
        {
            d[u][nw]=d[v][wt]+l[v];
            if(!vst[u][nw]) vst[u][nw]=1,q.push((node){nw,u});
        }
        //dg;
        u=(v+3)%4,nw=(wt+l[u])%w;
        if(d[u][nw]>d[v][wt]+l[u])
        {
            d[u][nw]=d[v][wt]+l[u];
            if(!vst[u][nw]) vst[u][nw]=1,q.push((node){nw,u});
        }
        vst[v][wt]=0;
        //dg;
        //cout<<v<<endl;
    }
}
signed main()
{
    int T=read();
    while(T--)
    {
        k=read();
        for(int i=0;i<4;i++) l[i]=read();
        w=2*min(l[0],l[1]);
        spfa();
        ans=k;
        while(d[1][ans%w]>ans) ans++;
        cout<<ans<<endl;
    }
}

Problem C: 道路建设

题意:

题解:

没什么好说的。。。

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
//#define int long long
#define Max 200005
#define Max2 4000005
#define ls(x) e[x].s[0]
#define rs(x) e[x].s[1]
#define fa(x) e[x].f
#define r(x) e[x].rv
#define mx(x) mx[x]
using namespace std;
il ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct lct
{
    int f,s[2],rv;
}e[Max];
int v[Max],mx[Max];
il void pushup(int x)
{
    mx(x)=x;
    if(ls(x)&&v[mx(ls(x))]>v[mx(x)]) mx(x)=mx(ls(x));
    if(rs(x)&&v[mx(rs(x))]>v[mx(x)]) mx(x)=mx(rs(x));
}
il void pushdown(int x)
{
    if(r(x))
    {
        r(x)=0;
        swap(ls(x),rs(x));
        if(ls(x)) r(ls(x))^=1;
        if(rs(x)) r(rs(x))^=1;
    }
}
il bool isroot(int x)
{
    return ls(fa(x))!=x&&rs(fa(x))!=x;
}
il bool rlt(int x)
{
    return rs(fa(x))==x;
}
il void ct(int x,int f,int k)
{
    fa(x)=f;
    e[f].s[k]=x;
}
il void rot(int x)
{
    int y=fa(x),z=fa(y),ys=rlt(x),zs=rlt(y),k=e[x].s[ys^1];
    fa(x)=z;
    if(!isroot(y)) ct(x,z,zs);
    ct(k,y,ys),ct(y,x,ys^1);
    pushup(y),pushup(x);
}
il void pushall(int x)
{
    if(!isroot(x)) pushall(fa(x));
    pushdown(x);
}
il void splay(int x)
{
    pushall(x);
    for(int y=fa(x);!isroot(x);rot(x),y=fa(x))
        if(!isroot(y))
            rot(rlt(x)==rlt(y)?x:y);
}
il void access(int x)
{
    for(int y=0;x;x=fa(y=x))
        splay(x),rs(x)=y,pushup(x);
}
il void makeroot(int x)
{
    access(x);
    splay(x);
    r(x)^=1;
    pushdown(x);
}
il void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
}
il void link(int x,int y)
{
    makeroot(x);
    fa(x)=y;
}
il int cut(int x,int y)
{
    split(x,y);
    x=mx(y);
    splay(x);
    fa(ls(x))=fa(rs(x))=0;
    ls(x)=rs(x)=0;
    return x;
}
struct node
{
    int u,v,w;
}ed[Max];
il bool cmp(node a,node b)
{
    return a.w>b.w;
}
int n,m,q,ff[Max],rt[Max],ls[Max2],rs[Max2],t[Max2],cnt,ans;
il int getf(int x)
{
    return ff[x]==x?x:(ff[x]=getf(ff[x]));
}
il void merge(int x,int y)
{
    ff[getf(x)]=getf(y);
}
il void ins(int o,int &x,int l,int r,int p,int v)
{
    x=++cnt;
    t[x]=t[o];ls[x]=ls[o],rs[x]=rs[o];
    t[x]+=v;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(p<=mid) ins(ls[o],ls[x],l,mid,p,v);
    else ins(rs[o],rs[x],mid+1,r,p,v);
}
il int qry(int x,int l,int r,int ql,int qr)
{
    if(!x) return 0;
    if(ql<=l&&r<=qr) return t[x];
    int mid=(l+r)>>1,res=0;
    if(ql<=mid) res+=qry(ls[x],l,mid,ql,qr);
    if(qr>mid) res+=qry(rs[x],mid+1,r,ql,qr);
    return res;
}
signed main()
{
    n=read(),m=read();
    int ol=read(),N;
    for(int i=1;i<=m;i++)
    {
        ed[i].u=read(),ed[i].v=read();ed[i].w=read();
    }
    for(int i=1;i<=n;i++) ff[i]=i;
    sort(ed+1,ed+1+m,cmp);
    N=ed[1].w;
    for(int i=1;i<=m;i++)
    {
        rt[ed[i].w]=rt[ed[i-1].w];
        if(getf(ed[i].u)==getf(ed[i].v))
        {
            //puts("qwq1");
            q=cut(ed[i].u,ed[i].v);
            ins(rt[ed[i].w],rt[ed[i].w],1,N,v[q],-v[q]);
        }
        else
        {
            //puts("qwq2");
            merge(ed[i].u,ed[i].v);
            q=n+i;
        }
        v[q]=ed[i].w;
        mx[q]=q;
        link(ed[i].u,q);
        link(q,ed[i].v);
        ins(rt[ed[i].w],rt[ed[i].w],1,N,ed[i].w,ed[i].w);
        //cout<<"qwq! "<<i<<' '<<rt[ed[i].w]<<' '<<q<<endl;
    }
    for(int i=N-1;i>=1;i--)
    {
        if(!rt[i]) rt[i]=rt[i+1];
        //cout<<i<<' '<<rt[i]<<endl;
    }
    //puts("qwq");
    q=read();
    while(q--)
    {
        int l=read(),r=read();
        l-=ans*ol;
        r-=ans*ol;
        ans=qry(rt[l],1,N,1,r);
        printf("%d\n",ans);
    }
}