AtCoder Beginner Contest 213

https://atcoder.jp/contests/abc213

E - Stronger Takahashi

题意

有一张 $h\times w$ 的网格图，一些格子有障碍。高桥每次可以摧毁一个 $2\times2$ 的区域内所有障碍，求从 $(1,1)$ 走到 $(h,w)$ 所需要的最小摧毁次数。

数据范围：$2\leq h,w\leq 500$。

题解

考虑从起点出发进行01bfs。当到达某个点时，可以选择不进行摧毁操作，到达相邻的 $4$ 个点中没有障碍的那些点，也可以选择进行摧毁操作。

.ooo.
ooooo
ooxoo
ooooo
.ooo.
x为当前位置，o为进行一次摧毁操作可以到达的点。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=505;
char s[N][N];
int h,w,dir[4][2]={-1,0,0,-1,1,0,0,1};
int dis[N][N];
bool inside(int x,int y) {return x>=1&&x<=h&&y>=1&&y<=w;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>h>>w;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++) cin>>s[i][j];
    memset(dis,0x3f,sizeof(dis));
    dis[1][1]=0;
    deque<pii> q;q.push_front({1,1});
    while(!q.empty())
    {
        auto a=q.front();q.pop_front();
        for(int i=0;i<4;i++)
        {
            int x=a.first+dir[i][0],y=a.second+dir[i][1];
            if(!inside(x,y)||s[x][y]=='#') continue;
            if(dis[a.first][a.second]<dis[x][y]) 
            {
                dis[x][y]=dis[a.first][a.second];
                q.push_front({x,y});
            }
        }
        for(int i=-2;i<=2;i++)
            for(int j=-2;j<=2;j++)
                if(abs(i)+abs(j)<4)
                {
                    int x=a.first+i,y=a.second+j;
                    if(!inside(x,y)) continue;
                    if(dis[a.first][a.second]+1<dis[x][y])
                    {
                        dis[x][y]=dis[a.first][a.second]+1;
                        q.push_back({x,y});
                    }
                }
    }
    cout<<dis[h][w]<<'\n';
    return 0;
}

F - Common Prefixes

题意

给定字符串 $s$，记 $s_i$ 为 $s[i:n]$，对于 $k=1,2\cdots,n$，求 $\sum\limits_{i=1}^nlcp(s_k,s_i)$。

数据范围：$1\leq|s|\leq 10^6$。

题解

SA中的 $height$ 数组有个重要的性质：$lcp(sa_i,sa_j)=\min(height_{i+1},\cdots,height_j)$。那么只需要考虑对于 $k=1,2,\cdots,n$，求出 $g(1,k),g(2,k)+\cdots+g(k-1,k)+g(k,k+1)+\cdots+g(k,n)$，其中 $g(i,j)=\min(height_{i+1},\cdots,height_j)$。这个问题基本等价于： 给定数组 $a$，对于每个 $i$，求出所有以 $i$ 为一个端点的区间内最小值之和。

这是一个经典的问题。先考虑前一部分：令 $B_k=g(1,k)+\cdots+g(k-1,k)$，考虑 $B_{k+1}=\min(g(1,k),height_{k+1})+\cdots+\min(g(k-1,k),height_{k+1})+height_{k+1}$，所以我们只需要维护一个集合，每次将集合内的数与 $height$ 取 $\min$，将 $height$ 加入集合中，然后集合内所有数的和就是 $B$。集合内本质不同的数只有 $O(n)$ 个，且每次加入的数都不小于集合内原有的数，可以使用单调栈进行维护。后一部分同理可得。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int sa[N],rk[N],oldrk[2*N],tmp[N],cnt[N],height[N];
int tp,stk[N];
ll pre[N],suf[N];
bool cmp(int x,int y,int w) {return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    string s;cin>>s;
    int m=127,p;
    for(int i=1;i<=n;i++) cnt[rk[i]=s[i-1]]++;
    for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
    for(int i=n;i;i--) sa[cnt[rk[i]]--]=i;
    for(int i,w=1;;w<<=1,m=p)
    {
        for(p=0,i=n;i>n-w;i--) tmp[++p]=i;
        for(i=1;i<=n;i++) 
            if(sa[i]>w) tmp[++p]=sa[i]-w;
        memset(cnt,0,sizeof(cnt));
        for(i=1;i<=n;i++) cnt[rk[i]]++;
        for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
        for(int i=n;i;i--) sa[cnt[rk[tmp[i]]]--]=tmp[i];
        memcpy(oldrk+1,rk+1,n*sizeof(int));
        for(p=0,i=1;i<=n;i++) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
        if(p==n) break;
    }
    for(int i=1,k=0;i<=n;i++)
    {
        if(rk[i]==0) continue;
        if(k) k--;
        while(s[i+k-1]==s[sa[rk[i]-1]+k-1]) k++;
        height[rk[i]]=k;
    }
    stk[tp=0]=1;
    for(int i=2;i<=n;i++)
    {
        pre[i]=pre[i-1];
        while(tp&&height[i]<height[stk[tp]])
        {
            pre[i]-=1ll*(stk[tp]-stk[tp-1])*height[stk[tp]];
            tp--;
        }
        pre[i]+=1ll*(i-stk[tp])*height[i];
        stk[++tp]=i;
    }
    stk[tp=0]=n+1;
    for(int i=n;i>1;i--)
    {
        suf[i]=suf[i+1];
        while(tp&&height[i]<height[stk[tp]])
        {
            suf[i]-=1ll*(stk[tp-1]-stk[tp])*height[stk[tp]];
            tp--;
        }
        suf[i]+=1ll*(stk[tp]-i)*height[i];
        stk[++tp]=i;
    }
    for(int i=1;i<=n;i++) cout<<pre[rk[i]]+suf[rk[i]+1]+n-i+1<<'\n';
    return 0;
}

G - Connectivity 2

题意

给定一张 $n$ 个点 $m$ 条边的图。对于点 $2,3,\cdots,n$，求所有删边方案中该点和 $1$ 号点连通的方案数。答案对 $998244353$ 取模。

数据范围：$2\leq n\leq17,0\leq m\leq \dfrac{n(n-1)}{2}$。

题解

记 $f_S$ 为点集 $S$ 的连通子图数，$g_S$ 为点集 $S$ 的子图数，则

$$ans_i=\sum_{\{1,i\}\in S}f_Sg_{C_FS}$$

其中 $C_FS$ 为全集 $F$ 关于 $S$ 的补集。

$g_S$ 是容易求的，记 $i$ 为端点均在 $S$ 内的边的数量，则

$$g_S=2^i$$

然后求 $f_S$。利用容斥，即用子图数量减去不连通的子图数量。考虑钦定一个连通块 $T$，则剩下的点集可以任意连边。为了避免重复，可以钦定 $1$ 号点属于连通块 $T$，则

$$f_S=g_S-\sum_{1\in T,T\subsetneq S}f_Tg_{C_ST}$$

然后就做完了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=20;
const int p=998244353;
pii e[N*N];
ll ans[N],f[1<<N],g[1<<N],P2[1<<N];
void init()
{
    P2[0]=1;
    for(int i=1;i<(1<<N);i++) P2[i]=P2[i-1]*2%p;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;cin>>a>>b;
        e[i]=make_pair(a,b);
    }
    for(int S=0;S<(1<<n);S++)
    {
        for(int j=1;j<=m;j++)
            if((S>>(e[j].first-1)&1)&&(S>>(e[j].second-1)&1)) g[S]++;
        g[S]=P2[g[S]];
    }
    f[0]=1;
    for(int S=1;S<(1<<n);S++)
    {
        for(int T=(S-1)&S;T;T=(T-1)&S)
            if(T&1) f[S]=(f[S]+f[T]*g[S^T])%p;
        f[S]=(g[S]-f[S]+p)%p;
    }
    for(int i=2;i<=n;i++)
        for(int S=0;S<(1<<n);S++)
            if((S&1)&&(S>>(i-1)&1)) ans[i]=(ans[i]+f[S]*g[S^((1<<n)-1)])%p;
    for(int i=2;i<=n;i++) cout<<ans[i]<<'\n';
    return 0;
}