JZTXT

【考后总结】NOI 统一省选 2023

发布时间 2023-04-17 15:44:01作者: SoyTony

文化课补完了，但是考试考炸了，所以来补题。

D1T1 火车站 station

实际上只需要判断从 \(x\) 能否一直向一个方向移动且每个位置能不能作为这个方向的终点站。

区间覆盖差分一下即可。

点击查看代码 
int n,m,x;
int st[maxn][2],cov[maxn];
bool vis[maxn];

int main(){
    freopen("station.in","r",stdin);
    freopen("station.out","w",stdout);
    n=read(),m=read(),x=read();
    for(int i=1;i<=m;++i){
        int l=read(),r=read();
        st[l][0]=1,st[r][1]=1;
        ++cov[l],--cov[r];
    }
    for(int i=1;i<n;++i) cov[i]+=cov[i-1];
    for(int i=x-1;i>=1;--i){
        if(!cov[i]) break;
        if(st[i][0]) vis[i]=1;
    }
    for(int i=x+1;i<=n;++i){
        if(!cov[i-1]) break;
        if(st[i][1]) vis[i]=1;
    }
    for(int i=1;i<=n;++i){
        if(vis[i]) printf("%d ",i);
    }
    printf("\n");
    return 0;
}

D2T2 城市建造 cities

一个连通块中只能有一个点被选中。

由于连通块大小是 \(\left\lfloor n/cnt\right\rfloor\) 和 \(\left\lceil n/cnt\right\rceil\)，只有 \(O(\sqrt{n})\) 中，可以枚举连通块大小。

考虑树上怎么做，假设当前枚举的连通块大小 \(siz\)，可能的连通块个数 \(cnt\)，那么有 \(cnt\) 个节点被选中，且断边后断成了 \(cnt\) 个连通块，也就是 \(cnt\) 个节点有 \(cnt-1\) 条边，因此合法方案实际上是一棵树（这个性质在考场上认为是菊花或是链之类的，没拿到部分分）。

考虑一个树形 DP，设 \(f_v\) 为 \(v\) 与父亲的连边被断开，即 \(v\) 子树内部划分成大小为 \(siz\) 或 \(siz+1\) 的连通块的方案数。

一棵树的性质同样揭示了另一个事实：如果 \(v\) 与父亲的连边不断开，那么 \(v\) 一定是整体并入其父亲所在连通块的，也就只和子树大小 \(siz_v\) 有关了。

这样对于 \(u\) 的儿子 \(v\)，不同的 \(siz_v\) 直接对应不同的处理方式：

  • \(siz_v>siz\)，不可能与 \(u\) 在同一连通块，\((u,v)\) 必须断开。

  • \(siz_v=siz\)，既可能与 \(u\) 在同一连通块，也可能单独成连通块。

  • \(siz_v<siz\)，一定与 \(u\) 在同一连通块。

这样我们只需要统计第一种情况是否内部划分都合法，第三种情况之和与 \(u\) 拼在一起是否合法，同时将的第一种情况的方案数累成即为答案。还有一同时情况为：不存在小于 \(siz\) 的，此时若 \(siz=1\) 或存在等于 \(siz\) 的子树 \(v\) 才合法，且方案数乘上满足条件的 \(v\) 的个数（如果 \(u\) 单独成块也合法也要计入）。

这样在每个节点统计答案，默认其父亲及其他子树都不断开。

放到图上，由于删去选中节点的全部连边后不连通，容易想到点双连通分量，这样一个点双内如果选取超过一个且有没有选取的，无法达到不连通的条件。因此一个点双要么全不选，要么全选，要么选一个。反映到圆方树上就是选取点击构成的树，叶子节点一定全是圆点。

根据这个性质同样可以讨论圆点方点后 DP，\(f_u\) 定义相同。

对于圆点，和上面树的情况讨论是一致的；对于方点，如果断开了其与父亲的连边，那么意味着其与儿子连边要么不断开要么全部断开，因此在对方点 DP 时，只需要考虑全部断开是否合法即可。

要注意的是，图上和树上不同之处在于即便 \(siz_v=siz\)，断开 \((u,v)\) 后不一点合法，因为这代表着 \(v\) 对应所有圆点连边都将断开，而不是像树上作为一个整体。

这样大致就是全部算法流程，还存在的问题是枚举到 \(\left\lfloor n/cnt\right\rfloor\) 时有可能存在方案至划分成了大小为 \(\left\lceil n/cnt\right\rceil\) 的连通块，这样会算重。可以容斥，减去 \(\left\lceil n/cnt\right\rceil\) 对应 \(k=0\) 的情况。

点击查看代码（不卡常版本） 
int n,m,k;
vector<int> E[maxn];
struct edge{
    int to,nxt;
}e[maxm<<1];
int head[maxm],cnt;
inline void add_edge(int u,int v){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
    e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int dfn[maxn],dfncnt,low[maxn];
int st[maxn],top;
int tot;
void Tarjan(int u){
    dfn[u]=++dfncnt,low[u]=dfn[u];
    st[++top]=u;
    for(int v:E[u]){
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                ++tot;
                while(st[top]!=v){
                    add_edge(st[top],tot);
                    --top;
                }
                add_edge(v,tot);
                --top;
                add_edge(u,tot);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
int siz[maxm];
void dfs(int u,int fa){
    siz[u]=(u<=n);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u); 
        siz[u]+=siz[v];
    }
}
int ans0[maxn],ans1[maxn],ans;
int f[maxm];
bool g[maxm],h[maxm];
void solve0(int u,int fa,int SIZ){
    f[u]=1,g[u]=1;
    if(u<=n){
        int sumsiz=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(v==fa) continue;
            solve0(v,u,SIZ);
            if(siz[v]>=SIZ) f[u]=1ll*f[u]*f[v]%mod,g[u]&=g[v];
            else sumsiz+=siz[v];
        }
        if(g[u]){
            if(sumsiz+(n-siz[u])+1==SIZ) ans0[SIZ]=(ans0[SIZ]+f[u])%mod;
        }
        g[u]&=(sumsiz+1==SIZ);
        if(!g[u]) f[u]=0;
    }
    else{
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(v==fa) continue;
            solve0(v,u,SIZ);
            f[u]=1ll*f[u]*f[v]%mod,g[u]&=g[v];
        }
    }
}
void solve1(int u,int fa,int SIZ){
    f[u]=1,g[u]=1;
    if(u<=n){
        int sumsiz=0,cnt=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(v==fa) continue;
            solve1(v,u,SIZ);
            if(siz[v]>SIZ) f[u]=1ll*f[u]*f[v]%mod,g[u]&=g[v];
            else if(siz[v]==SIZ&&g[v]) ++cnt;
            else sumsiz+=siz[v];
        }
        cnt+=(SIZ==1);
        if(g[u]){
            if(!(sumsiz+(n-siz[u]))) ans1[SIZ]=(ans1[SIZ]+1ll*f[u]*cnt%mod)%mod;
            else{
                if(sumsiz+(n-siz[u])+1>=SIZ&&sumsiz+(n-siz[u])+1<=SIZ+1) ans1[SIZ]=(ans1[SIZ]+f[u])%mod;
            }
        }
        if(!sumsiz) f[u]=1ll*f[u]*cnt%mod,g[u]&=(cnt!=0);
        else g[u]&=(sumsiz+1>=SIZ&&sumsiz+1<=SIZ+1);
        if(!g[u]) f[u]=0;
    }
    else{
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(v==fa) continue;
            solve1(v,u,SIZ);
            f[u]=1ll*f[u]*f[v]%mod,g[u]&=g[v];
        }
    }
}
int main(){
    freopen("cities.in","r",stdin);
    freopen("cities.out","w",stdout);
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        E[u].push_back(v);
        E[v].push_back(u);
    }
    tot=n;
    Tarjan(1);
    dfs(1,0);
    for(int i=1;i*i<=n;++i){
        if(n%i) continue;
        solve0(1,0,i);
        if(i==1||i*i==n) continue;
        solve0(1,0,n/i);
    }
    for(int i=1;i<=n;++i) ans=(ans+ans0[i])%mod;
    if(k){
        for(int l=2,r;l<=n;l=r+1){
            r=n/(n/l);
            solve1(1,0,n/l);
            ans=((ans+ans1[n/l]-ans0[n/l]-ans0[n/l+1])%mod+mod)%mod;
        }
    }
    printf("%d\n",ans);
    return 0;
}

由于复杂度一定拉满，需要大面积卡常：

  • 只在重心位置统计答案，重心一定会被选中，否则被选中的部分是其一个子树，大小不超过一半，也就和其余部分大小相差 \(1\) 以上。

  • DFS 时按照 DFS 序重标号，\(O(\sqrt{n})\) 次 DFS 使用非递归 DFS。

  • 使用邻接表而不是 vector。

  • 如果存在大小大于 \(siz\) 的子树内部不合法或是大小小于 \(siz\) 的子树大小之和超过了 \(siz\)，一定没有合法方案，可以不再枚举子树。

  • 如果 \(siz_u<siz\)，一定没有合法方案，这一处能带来极大的优化。

点击查看代码 
int n,m,k;
vector<int> E[maxn];
struct edge{
    int to,nxt;
}e[maxm<<1];
int head[maxm],cnt;
inline void add_edge_e(int u,int v){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
    e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int dfn[maxm],dfncnt,low[maxn];
int st[maxn],top;
int tot;
inline void Tarjan(int u){
    dfn[u]=++dfncnt,low[u]=dfn[u];
    st[++top]=u;
    for(int v:E[u]){
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                ++tot;
                while(st[top]!=v){
                    add_edge_e(st[top],tot);
                    --top;
                }
                add_edge_e(v,tot);
                --top;
                add_edge_e(u,tot);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
int rt;
int siz[maxm],maxsiz[maxm],id[maxm];
inline void dfs1(int u,int fa){
    siz[u]=(u<=n),maxsiz[u]=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs1(v,u);
        siz[u]+=siz[v],maxsiz[u]=max(maxsiz[u],siz[v]);
    }
    maxsiz[u]=max(maxsiz[u],n-siz[u]);
    if(maxsiz[u]<maxsiz[rt]&&u<=n) rt=u; 
}
inline void dfs2(int u,int fa){
    siz[u]=(u<=n),dfn[u]=++dfncnt,id[dfncnt]=u;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs2(v,u); 
        siz[u]+=siz[v];
    }
}
int ans0[maxn],ans1[maxn];
int f[maxm];
bool g[maxm];
inline void solve0(int SIZ){
    for(int i=tot;i>=1;--i){
        int u=id[i];
        f[u]=1,g[u]=1;
        if(siz[u]<SIZ){
            f[u]=g[u]=0;
            continue;
        }
        if(u<=n){
            int sumsiz=0;
            for(int j=head[u];j;j=e[j].nxt){
                int v=e[j].to;
                if(dfn[v]<dfn[u]) continue;
                if(siz[v]>=SIZ) f[u]=1ll*f[u]*f[v]%mod,g[u]&=g[v];
                else sumsiz+=siz[v];
                if(sumsiz+1>SIZ){
                    g[u]=0;
                    break;
                }
                if(!g[u]) break;
            }
            if(i==1&&g[u]){
                if(sumsiz+1==SIZ) ans0[SIZ]=f[u];
            }
            g[u]&=(sumsiz+1==SIZ);
            if(!g[u]) f[u]=0;
        }
        else{
            for(int j=head[u];j;j=e[j].nxt){
                int v=e[j].to;
                if(dfn[v]<dfn[u]) continue;
                f[u]=1ll*f[u]*f[v]%mod,g[u]&=g[v];
                if(!g[u]) break;
            }
        }
    }
}
inline void solve1(int SIZ){
    for(int i=tot;i>=1;--i){
        int u=id[i];
        f[u]=1,g[u]=1;
        if(siz[u]<SIZ){
            f[u]=g[u]=0;
            continue;
        }
        if(u<=n){
            int sumsiz=0,cnt=0;
            for(int j=head[u];j;j=e[j].nxt){
                int v=e[j].to;
                if(dfn[v]<dfn[u]) continue;
                if(siz[v]>SIZ) f[u]=1ll*f[u]*f[v]%mod,g[u]&=g[v];
                else if(siz[v]==SIZ&&g[v]) ++cnt;
                else sumsiz+=siz[v];
                if(!g[u]) break;
                if(sumsiz+1>SIZ+1){
                    g[u]=0;
                    break;
                }
            }
            cnt+=(SIZ==1);
            if(i==1&&g[u]){
                if(!sumsiz) ans1[SIZ]=1ll*f[u]*cnt%mod;
                else{
                    if(sumsiz+1>=SIZ&&sumsiz+1<=SIZ+1) ans1[SIZ]=f[u];
                }
            }
            if(!sumsiz) f[u]=1ll*f[u]*cnt%mod,g[u]&=(cnt!=0);
            else g[u]&=(sumsiz+1>=SIZ&&sumsiz+1<=SIZ+1);
            if(!g[u]) f[u]=0;
        }
        else{
            for(int j=head[u];j;j=e[j].nxt){
                int v=e[j].to;
                if(dfn[v]<dfn[u]) continue;
                f[u]=1ll*f[u]*f[v]%mod,g[u]&=g[v];
                if(!g[u]) break;
            }
        }
    }
}
unsigned long long ans;
int main(){
    freopen("cities.in","r",stdin);
    freopen("cities.out","w",stdout);
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        E[u].push_back(v),E[v].push_back(u);
    }
    tot=n;
    Tarjan(1);
    rt=0,maxsiz[0]=inf;
    dfs1(1,0);
    dfncnt=0;
    dfs2(rt,0);
    if(!k){
        for(int i=1;i*i<=n;++i){
            if(n%i) continue;
            solve0(i);
            if(i==1||i*i==n) continue;
            solve0(n/i);
        }
        for(int i=1;i<=n;++i) ans+=ans0[i];
    }
    else{
        for(int l=2,r;l<=n;l=r+1){
            r=n/(n/l);
            solve1(n/l);
            if(ans1[n/l]&&n%(n/l+1)==0) solve0(n/l+1);
            ans+=ans1[n/l]-ans0[n/l+1];
        }
    }
    ans%=mod;
    printf("%llu\n",ans);
    return 0;
}

D2T1 过河卒 zu

不是博弈论，是博弈论暴搜。

图很小，可以压成 \(10^6\) 的状态记录三个棋子的位置，合法转移直接连边。

不好解决的问题是可能出现平局——成环，这样不能从起始状态开始搜。改成从每个结束状态开始搜，由于根据步数的奇偶性可以判断出当前是谁的回合，我们只需要拓扑转移即可。

如果一个状态当前被转移到的都是必败状态，那么一直取步数的 \(\max\)，一旦出现必胜决策可以直接入队，由于 BFS，此时步数一定最小，且在当前位置决策者一定会选这种必胜决策。也就是魔改了一下拓扑排序。

在答案处要注意的是，如果是必败状态且初始状态处于一个环中，那么会选择走环来达到不败的情况，要特判一下。（在转移过程中由于没有被完全剥出的节点不会入队，实际上也是存在不败一定选不败）

点击查看代码 
int t,n,m;
char s[15][15];
pii B,R1,R2;
struct state{
    pii bp,rp1,rp2;
    //0->B 1->R
    state()=default;
    state(pii bp_,pii rp1_,pii rp2_):bp(bp_),rp1(rp1_),rp2(rp2_){}
}S[maxn];
bool opt[maxn];
int winchk[maxn];
int mp[11][11][11][11][11][11];
int tot,mark;
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};

struct edge{
    int to,nxt;
}e[maxn<<3];
int head[maxn],cnt;
int deg[maxn];
inline void add_edge(int u,int v){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
    ++deg[v];
}

queue<int> q;
int dp[maxn];

int main(){
    freopen("zu.in","r",stdin);
    freopen("zu.out","w",stdout);
    read(),t=read();
    while(t--){
        n=read(),m=read();
        for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
        B=R1=R2=make_pair(0,0);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(s[i][j]=='X') B=make_pair(i,j);
                if(s[i][j]=='O'){
                    if(!R1.x) R1=make_pair(i,j);
                    else R2=make_pair(i,j);
                }
            }
        }
        tot=0;
        memset(mp,0,sizeof(mp));
        for(int bx=1;bx<=n;++bx){
            for(int by=1;by<=m;++by){
                for(int rx1=1;rx1<=n;++rx1){
                    for(int ry1=1;ry1<=m;++ry1){
                        for(int rx2=1;rx2<=n;++rx2){
                            for(int ry2=1;ry2<=m;++ry2){
                                pii bnow=make_pair(bx,by),rnow1=make_pair(rx1,ry1),rnow2=make_pair(rx2,ry2);
                                if(bx>B.x) continue;
                                if(s[bnow.x][bnow.y]=='#'||s[rnow1.x][rnow1.y]=='#'||s[rnow2.x][rnow2.y]=='#') continue;
                                if(rnow1==rnow2) continue;
                                int sumstep=abs(B.x-bx)+abs(B.y-by)+abs(R1.x-rx1)+abs(R1.y-ry1)+abs(R2.x-rx2)+abs(R2.y-ry2);
                                S[++tot]=state(bnow,rnow1,rnow2),opt[tot]=sumstep&1^1,winchk[tot]=-1;
                                if(bnow.x==1) winchk[tot]=0;
                                else if(bnow==rnow1||bnow==rnow2) winchk[tot]=opt[tot]^1;
                                else{
                                    if(!opt[tot]){
                                        bool chk=1;
                                        for(int i=0;i<3;++i){
                                            int xx=bnow.x+dx[i],yy=bnow.y+dy[i];
                                            if(xx<1||xx>n||yy<1||yy>m) continue;
                                            if(s[xx][yy]!='#') chk=0;
                                        }
                                        if(chk) winchk[tot]=1;
                                    }
                                    else{
                                        bool chk=1;
                                        for(int i=0;i<4;++i){
                                            int xx=rnow1.x+dx[i],yy=rnow1.y+dy[i];
                                            if(xx<1||xx>n||yy<1||yy>m) continue;
                                            if(s[xx][yy]!='#'&&make_pair(xx,yy)!=rnow2) chk=0;
                                        }
                                        for(int i=0;i<4;++i){
                                            int xx=rnow2.x+dx[i],yy=rnow2.y+dy[i];
                                            if(xx<1||xx>n||yy<1||yy>m) continue;
                                            if(s[xx][yy]!='#'&&make_pair(xx,yy)!=rnow1) chk=0;
                                        }
                                        if(chk) winchk[tot]=0;
                                    }
                                }
                                mp[bx][by][rx1][ry1][rx2][ry2]=tot;
                                // printf("%d (%d %d) (%d %d) (%d %d)\n",tot,S[tot].bp.x,S[tot].bp.y,S[tot].rp1.x,S[tot].rp1.y,S[tot].rp2.x,S[tot].rp2.y);
                                if(bnow==B&&rnow1==R1&&rnow2==R2) mark=tot;
                            }
                        }
                    }
                }
            }
        }
        // printf("%d\n",mark);
        for(int i=1;i<=tot;++i) head[i]=0,deg[i]=0;
        cnt=0;
        for(int i=1;i<=tot;++i){
            if(winchk[i]!=-1) q.push(i);
            pii bnow=S[i].bp,rnow1=S[i].rp1,rnow2=S[i].rp2;
            if(!opt[i]){
                //move R
                for(int j=0;j<4;++j){
                    int xx=rnow1.x+dx[j],yy=rnow1.y+dy[j];
                    if(xx<1||xx>n||yy<1||yy>m) continue;
                    if(mp[bnow.x][bnow.y][xx][yy][rnow2.x][rnow2.y]){
                        int nxt=mp[bnow.x][bnow.y][xx][yy][rnow2.x][rnow2.y];
                        if(winchk[nxt]!=-1) continue;
                        add_edge(i,nxt);
                    }
                }
                for(int j=0;j<4;++j){
                    int xx=rnow2.x+dx[j],yy=rnow2.y+dy[j];
                    if(xx<1||xx>n||yy<1||yy>m) continue;
                    if(mp[bnow.x][bnow.y][rnow1.x][rnow1.y][xx][yy]){
                        int nxt=mp[bnow.x][bnow.y][rnow1.x][rnow1.y][xx][yy];
                        if(winchk[nxt]!=-1) continue;
                        add_edge(i,nxt);
                    }
                }
            }
            else{
                //move B
                for(int j=1;j<4;++j){
                    int xx=bnow.x+dx[j],yy=bnow.y+dy[j];
                    if(xx<1||xx>n||yy<1||yy>m) continue;
                    if(mp[xx][yy][rnow1.x][rnow1.y][rnow2.x][rnow2.y]){
                        int nxt=mp[xx][yy][rnow1.x][rnow1.y][rnow2.x][rnow2.y];
                        if(winchk[nxt]!=-1) continue;
                        add_edge(i,nxt);
                    }
                }
            }
        }
        for(int i=1;i<=tot;++i) dp[i]=0;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            // printf("%d (%d %d) (%d %d) (%d %d) opt:%d winchk:%d dp:%d\n",u,S[u].bp.x,S[u].bp.y,S[u].rp1.x,S[u].rp1.y,S[u].rp2.x,S[u].rp2.y,opt[u],winchk[u],dp[u]);
            for(int i=head[u];i;i=e[i].nxt){
                int v=e[i].to;
                if(winchk[u]==opt[u]){
                    //必败策略
                    if(winchk[v]==opt[v]) continue;
                    winchk[v]=opt[v]^1,dp[v]=max(dp[v],dp[u]+1);
                    --deg[v];
                    if(!deg[v]) q.push(v);
                }
                else{
                    //必胜策略
                    if(winchk[v]==opt[v]) continue;
                    winchk[v]=opt[v],dp[v]=dp[u]+1;
                    deg[v]=0;
                    q.push(v);
                }
            }
        }
        if(winchk[mark]==-1) printf("Tie\n");
        else if(winchk[mark]==opt[mark]) printf("Red %d\n",dp[mark]);
        else if(!deg[mark]) printf("Black %d\n",dp[mark]);
        else printf("Tie\n");
    }
    return 0;
}

没有做出的问题在于如何处理平局以及压成状态建图搜索的简单转换。

差不多的题：AtCoder-ABC261Ex Game on Graph

不用压状态了，但是要区分走到这个节点是谁的回合，可以把点拆开，建反图之类的的操作和上面类似。

有边权，所以后手一定是类似拓扑排序地所有点的值取 \(\max\) 才入队，否则会选择平局；先手则是取 \(\min\)，但是不能保证第一次更新就是 \(\min\)，而多次更新的复杂度不能保证，把队列改成堆就可以了。