儿童节快乐捏

捉迷藏

Zayin和Ziyin在一棵\(n\)个节点的树上，Zayin从\(a\)节点开始，每次可以走\(da\)步，Ziyin从\(b\)节点开始，每次可以走\(db\)步，走到了另一个人所在的节点的人获胜。求在最优策略下，两者谁会获胜。

题解：

令\(a\)和\(b\)之间的距离是\(dis\)

简单易得

当\(dis<da\)时，Zayin胜

否则，当\(da>db\)时，Zayin胜

否则，当\(da=db\)时，平局

否则，当\(da<db\)时，Ziyin胜

其中\(dis\)使用倍增求\(lca\)求解

代码

#include<cstdio>
#include<cstring>
const int N=1000005;
int n,head[N],pedge,dep[N],fa[N][22],t,q;
struct Edge{
    int to,next;
}edge[N<<1];
inline void Ins(int u,int v){edge[++pedge]={v,head[u]},head[u]=pedge;}
inline void ins(int u,int v){Ins(u,v),Ins(v,u);}
inline void swap(int&x,int&y){x^=y^=x^=y;}
void prework(int u,int father){
    fa[u][0]=father,dep[u]=dep[father]+1;
    for(int i=1;1<<i<=dep[u];i++)fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int e=head[u];e;e=edge[e].next){
        int v=edge[e].to;
        if(v^father)prework(v,u);
    }
}
inline int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=20;~i;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
    if(u==v)return u;
    for(int i=20;~i;i--)if(fa[u][i]^fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int main(){
    for(scanf("%*d%d",&t);t--;){
        scanf("%d%d",&n,&q),memset(head+1,0,n<<2);
        for(int i=1;i<=n;i++)memset(fa[i],0,84);
        for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),ins(u,v);
        prework(1,0);
        for(int a,b,da,db,dis;q--;){
            scanf("%d%d%d%d",&a,&b,&da,&db),dis=dep[a]+dep[b]-dep[lca(a,b)]*2;
            if(dis<=da||da>db)puts("Zayin");
            else if(da<db)puts("Ziyin");
            else puts("Draw");
        }
    }
    return 0;
}

读书

题面：

每次读书的第\(i\)个章节，都需要至少已经阅读其他的\(a_i\)个章节，每天从头到尾读书，把能读的章节读了，最少需要几天，读不完输出\(-1\)。

题解：

每天内读书相当与找一个最小值\(min\)，若\(min\le0\)那么可以读书并将其后面的\(a_i\)全部减\(1\)，将这个\(a_i\)赋值成\(\infty\)，在没有\(min\le0\)后，把每个设置成\(\infty\)的数前面也减去\(1\)并进入下一天。

如果\(n\)天结束还没有读完书，那么就读不完了。

使用线段树维护区间加最小值。

代码

#include<cstdio>
const int N=500005,INF=0x3f3f3f3f;
int n,a[N],tot,stk[N],top;
struct Tree{
    int l,r,minn,pos,tag;
}tr[N<<2];
inline int min(int x,int y){return x<y?x:y;}
inline int ls(int u){return u<<1;}
inline int rs(int u){return u<<1|1;}
inline void pushup(int u){
    if(tr[ls(u)].minn>tr[rs(u)].minn)tr[u].minn=tr[rs(u)].minn,tr[u].pos=tr[rs(u)].pos;
    else tr[u].minn=tr[ls(u)].minn,tr[u].pos=tr[ls(u)].pos;
}
inline void push(int u,int x){
    tr[u].minn+=x,tr[u].tag+=x;
}
inline void pushdown(int u){
    if(tr[u].tag)push(ls(u),tr[u].tag),push(rs(u),tr[u].tag),tr[u].tag=0;
}
void build(int u,int l,int r){
    tr[u].l=l,tr[u].r=r;
    if(l==r)return tr[u].minn=a[l],tr[u].pos=l,void();
    int mid=(l+r)>>1;
    build(ls(u),l,mid),build(rs(u),mid+1,r),pushup(u);
}
void modify(int u,int l,int r,int x){
    if(l<=tr[u].l&&r>=tr[u].r)return push(u,x);
    int mid=(tr[u].l+tr[u].r)>>1;
    pushdown(u);
    if(l<=mid)modify(ls(u),l,r,x);
    if(r>mid)modify(rs(u),l,r,x);
    pushup(u);
}
int main(){
    scanf("%*d%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    build(1,1,n);
    for(int i=1;i<=n+1;modify(1,1,n,-top),top=0,i++){
        if(i==n+1){
            puts("-1");
            break;
        }
        for(;tr[1].minn<=0;){
            int p=tr[1].pos;
            if(p^n)modify(1,p+1,n,-1);
            modify(1,p,p,INF),stk[++top]=p,tot++;
            if(tot==n)break;
        }
        if(tot==n){
            printf("%d\n",i);
            break;
        }
        for(int i=1;i<=top;i++)if(stk[i]^n)modify(1,stk[i]+1,n,1);
    }
    return 0;
}

正方形拓展

每个点会按正方形拓展，两个图形相遇后不再拓展，有\(n\)个起始点，问哪些点可以无限拓展，哪些点不能。

可以无限拓展的点只需要在上下左右任何一个方向可以无限拓展，不能无限拓展的点在四个方向都不能无限拓展。

考虑每个点和一个方向如向上

当这个点不能沿着这个方向拓展时，有两种情况

第一种情况是另一个点在这个点的正上方，如图（蓝色点为讨论的点，红色点为阻拦的点，黑色为分界线）

第二种情况下，先讨论两个不在一条竖直直线上时，形成的图形，如图

在有两个点阻拦的情况下，有如下两种情况（绿色点为另一个阻拦的点）

所以在第二种情况中，右边与左上方有点，左边与右上方有点，左上方与右上方有点的三种方法都可以阻拦向上无限拓展。

所以对每个点分别维护它的上，下，左，右，左上，左下，右上，右下的八个方向是否分别有点，并结合八个方向上是否有点，得出该点是否可以无限拓展。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
const int N=1000005;
int n,tx[N],nx,ty[N],ny,tr[N];
bool u[N],d[N],l[N],r[N],lu[N],ld[N],ru[N],rd[N],res[N],ans[N];
struct Point{
    int x,y,id;
    Point(){}
    Point(int _x,int _y){x=_x,y=_y;}
}a[N];
inline bool cmp(const Point&a,const Point&b){return a.x^b.x?a.x<b.x:a.y<b.y;}
inline void add(int p,int x){for(;p<=ny;p+=p&-p)tr[p]+=x;}
inline int que(int p){
    int res=0;
    for(;p;p-=p&-p)res+=tr[p];
    return res;
}
inline int sum(int l,int r){return que(r)-que(l-1);}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",tx+i,ty+i),a[i]=Point(tx[i],ty[i]);
    std::sort(tx+1,tx+n+1),nx=std::unique(tx+1,tx+n+1)-tx-1,std::sort(ty+1,ty+n+1),ny=std::unique(ty+1,ty+n+1)-ty-1;
    for(int i=1;i<=n;i++)a[i]=Point(std::lower_bound(tx+1,tx+nx+1,a[i].x)-tx,std::lower_bound(ty+1,ty+ny+1,a[i].y)-ty),a[i].id=i;
    std::sort(a+1,a+n+1,cmp);
    for(int i=1,j;i<=n;i=j+1){
        for(j=i;a[j+1].x==a[i].x;j++);
        for(int k=i;k<=j;k++){
            if(sum(1,a[k].y-1))ld[k]=true;
            if(sum(a[k].y+1,ny))lu[k]=true;
            if(sum(a[k].y,a[k].y))l[k]=true;
        }
        for(int k=i;k<=j;k++)add(a[k].y,1);
    }
    memset(tr,0,sizeof(tr));
    for(int i=n,j;i;i=j-1){
        for(j=i;a[j-1].x==a[i].x;j--);
        for(int k=j;k<=i;k++){
            if(sum(1,a[k].y-1))rd[k]=true;
            if(sum(a[k].y+1,ny))ru[k]=true;
            if(sum(a[k].y,a[k].y))r[k]=true;
        }
        for(int k=j;k<=i;k++)add(a[k].y,1);
    }
    memset(tr,0,sizeof(tr));
    for(int i=1,j;i<=n;i=j+1){
        for(j=i;a[j+1].x==a[i].x;j++);
        for(int k=i;k<=j;k++)add(a[k].y,1);
        for(int k=i;k<=j;k++){
            if(sum(1,a[k].y-1))d[k]=true;
            if(sum(a[k].y+1,ny))u[k]=true;
        }
        for(int k=i;k<=j;k++)add(a[k].y,-1);
    }
    for(int i=1;i<=n;i++){
        if(lu[i]&&ru[i]||lu[i]&&r[i]||ru[i]&&l[i])u[i]=true;
        if(lu[i]&&ld[i]||lu[i]&&d[i]||ld[i]&&u[i])l[i]=true;
        if(ru[i]&&rd[i]||ru[i]&&d[i]||rd[i]&&u[i])r[i]=true;
        if(ld[i]&&rd[i]||ld[i]&&r[i]||rd[i]&&l[i])d[i]=true;
        if(l[i]&&u[i]&&r[i]&&d[i])res[i]=true;
    }
    for(int i=1;i<=n;i++)ans[a[i].id]=res[i];
    for(int i=1;i<=n;i++)putchar(ans[i]?'0':'1');
    return puts(""),0;
}

最后，还是儿童节快乐捏。