2023牛客暑期多校训练营3

F World Fragments II

题意

有 $q$ 次询问。每次询问给定两个数 $x,y$ ，每次可以对 $x$ 进行操作：选定 $x$ 的一个数码，令 $x\leftarrow x+b$ 或 $x\leftarrow x-b$ 。求 $x$ 变成 $y$ 的最小操作次数。强制在线。

数据范围： $1\leq q\leq 3\times 10^5,0\leq x,y\leq 3\times 10^5$ 。

题解

首先，有一个朴素的想法：对每个点，向它经一次操作能得到的数连一条边， $x$ 到 $y$ 的最短路就是最小操作次数。但这样时间复杂度不对。

注意到从一个数出发，我们至多增加或减少 $9$ ，所以我们可以这样考虑：对于一个区间 $[l,r]$ ，我们希望求解出两两之间的最短路。令 $m=\lfloor\dfrac{l+r}{2}\rfloor,L=\max(l,m-4),R=\min(r,m+4)$ ，则对于位居 $[L,R]$ 两侧的两点，它们的最短路径必然经过 $[L,R]$ 。所以，我们可以以该区间内的所有点为源点，跑一遍最短路。求解 $p,q$ 两点间最短路时，枚举中转点 $i$ ， $p$ 到 $q$ 的最短路就是 $p$ 到 $i$ 再加上 $i$ 到 $q$ 。为此，我们需要建出反图，以分别求出区间内点到所有点和所有点到区间内点的最短路。对于位居 $[L,R]$ 一侧的点，我们递归求解。

查询的过程类似线段树，我们递归遍历包含 $x,y$ 的区间，利用区间内的中转点来更新答案。具体实现参考代码。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+100+5;
const int inf=0x3f3f3f3f;
vector<int> g[2][N];
struct node
{
    int l,r,len;
    int L,R;
    array<vector<int>,2> d[9];
}tr[N<<2];
int dfn,vis[N],dis[N];
void build(int u,int l,int r)
{
    if(l>r) return;
    int m=(l+r)>>1,len=r-l+1;
    int L=max(l,m-4),R=min(r,m+4);
    tr[u]={l,r,len,L,R};
    auto &d=tr[u].d;
    for(int i=0;i<R-L+1;i++)
    {
        d[i][0].reserve(len),d[i][1].reserve(len);
        for(auto u:{0,1})
        {
            dfn++;
            queue<int> q;
            q.push(L+i);vis[i+L]=dfn;dis[L+i]=0;
            while(!q.empty())
            {
                int x=q.front();q.pop();
                for(auto v:g[u][x])
                {
                    if(vis[v]==dfn) continue;
                    if(v<l||v>r) continue;
                    q.push(v);vis[v]=dfn;dis[v]=dis[x]+1;
                }
            }
            for(int j=0;j<len;j++)
            {
                if(vis[l+j]==dfn) d[i][u][j]=dis[l+j];
                else d[i][u][j]=inf;
            }
        }
    }
    build(u<<1,l,L-1);
    build(u<<1|1,R+1,r);
}
int query(int u,int x,int y)
{
    if(x<tr[u].l||y<tr[u].l||x>tr[u].r||y>tr[u].r) return inf;
    auto &d=tr[u].d;
    int res=inf;
    for(int i=0;i<tr[u].R-tr[u].L+1;i++)
    {
        int p=x-tr[u].l,q=y-tr[u].l;
        res=min(res,d[i][1][p]+d[i][0][q]);
    }
    if(x<tr[u].L&&y<tr[u].L) res=min(res,query(u<<1,x,y));
    if(x>tr[u].R&&y>tr[u].R) res=min(res,query(u<<1|1,x,y));
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n=3e5+100;
    for(int i=0;i<=n;i++)
    {
        int x=i;
        while(x)
        {
            int y=x%10;
            if(y)
            {
                g[0][i].push_back(i-y);
                g[1][i-y].push_back(i);
                if(i+y<=n)
                {
                    g[0][i].push_back(i+y);
                    g[1][i+y].push_back(i);
                }
            }
            x/=10;
        }
    }
    build(1,0,n);
    int q;cin>>q;
    int lst=0;
    while(q--)
    {
        int x,y;cin>>x>>y;
        x^=(lst+1),y^=(lst+1);
        int res=query(1,x,y);
        if(res==inf) res=-1;
        cout<<(lst=res)<<'\n';
    }
    return 0;
}

G Beautiful Matrix

题意

给出一个 $n\times m$ 的字符矩阵。定义一个 $n\times m$ 的矩阵 $s$ 是美丽的，当且仅当 $n=m$ 且 $\forall i,j\in [1,n],s_{i,j}=s_{n-i+1,m-j+1}$ 。计算给定的矩阵中有多少美丽的子矩阵。

题解

感觉是很板的一道题目。

我们枚举子矩阵的对称行，分为奇对称和偶对称两种情况。考虑枚举当前行，我们对该行做Manacher，不过Manacher的扩展条件变成了子矩阵是否对称，这个可以用二维哈希进行判断（对原矩阵和对称矩阵分别求哈希值，比较该矩阵的哈希值和对称矩阵中的对应矩阵的哈希值是否相等）。

具体实现参考代码。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005;
const ll m1=233;
const ll m2=1949;
const ll p=998244353;
int n,m,d1[N][N],d2[N][N];
ll base1[N],base2[N],hsh1[N][N],hsh2[N][N];
char g[N][N];
void init()
{
    base1[0]=base2[0]=1;
    for(int i=1;i<N;i++) base1[i]=base1[i-1]*m1%p,base2[i]=base2[i-1]*m2%p;
}
ll query(int x1,int y1,int x2,int y2,int op)
{
    if(op==1) return ((hsh1[x2][y2]+hsh1[x1-1][y1-1]*base1[x2-x1+1]%p*base2[y2-y1+1]-hsh1[x1-1][y2]*base1[x2-x1+1]-hsh1[x2][y1-1]*base2[y2-y1+1])%p+p)%p;
    else return ((hsh2[x2][y2]+hsh2[x1-1][y1-1]*base1[x2-x1+1]%p*base2[y2-y1+1]-hsh2[x1-1][y2]*base1[x2-x1+1]-hsh2[x2][y1-1]*base2[y2-y1+1])%p+p)%p;
}
bool check(int x1,int y1,int x2,int y2)
{
    return query(x1,y1,x2,y2,1)==query(n-x2+1,m-y2+1,n-x1+1,m-y1+1,2);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>g[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
        {
            hsh1[i][j]=((hsh1[i-1][j]*m1+hsh1[i][j-1]*m2-hsh1[i-1][j-1]*m1%p*m2+g[i][j])%p+p)%p;
            hsh2[i][j]=((hsh2[i-1][j]*m1+hsh2[i][j-1]*m2-hsh2[i-1][j-1]*m1%p*m2+g[n-i+1][m-j+1])%p+p)%p;
        }
    ll ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1,l=1,r=0;j<=m;j++)
        {
            int k=(j>r?1:min(d1[i][l+r-j],r-j+1));
            while(i-k>=1&&i+k<=n&&j-k>=1&&j+k<=m&&check(i-k,j-k,i+k,j+k)) k++;
            d1[i][j]=k--;
            ans+=d1[i][j];
            if(j+k>r) l=j-k,r=j+k;
        }
    for(int i=1;i<=n;i++)
        for(int j=1,l=1,r=0;j<=m;j++)
        {
            int k=(j>r?0:min(d2[i][l+r-j+1],r-j+1));
            while(i-k-1>=1&&i+k<=n&&j-k-1>=1&&j+k<=m&&check(i-k-1,j-k-1,i+k,j+k)) k++;
            d2[i][j]=k--;
            ans+=d2[i][j];
            if(j+k>r) l=j-k-1,r=j+k;
        }
    cout<<ans<<'\n';
    return 0;
}

I To the Colors of the Dreams of Electric Sheep

题意

给定一棵 $n$ 个结点的树，每个结点有一个权值 $c_i$ ，第 $i$ 位为 $1$ 表示该结点有颜色 $i$ 。有 $q$ 次询问，给出起点 $x$ 和终点 $y$ ，初始可以选定一种颜色（必须是起点具有的颜色），每次可以进行以下两种操作之一：

记当前颜色为 $c$ ，移动到一个相邻的具有颜色 $c$ 的结点。
改变颜色为 $c'$ ，当前结点必须具有颜色 $c'$ 。

求从 $x$ 到 $y$ 的最小操作数。

数据范围： $2\leq n\leq 5\times 10^5,1\leq q\leq 5\times 10^5$ 。

题解

首先可以确定，从 $x$ 到 $y$ 经过的结点一定是它们两点的树上路径，其次，在行走过程中，颜色一定是能不变就不变。基于这两点，问题就容易解决了：

我们对每个点，倍增求出改变 $2^i$ 次颜色能够到达的点。（可以对每个颜色分别求解，然后取 $\max$ ）在求解答案时，先让 $x,y$ 跳到 $lca$ 的下面一个位置，然后检查一下是否有同一种颜色，使得它们能够跳到 $lca$ ，这样就不需要多改变颜色了。

具体实现参考代码。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int d[N],col[60][N],jmp[N][25],f[N][25];
ll c[N];
vector<int> g[N];
void dfs(int u,int fa)
{
    d[u]=d[fa]+1;
    f[u][0]=fa;
    int up=-1;
    for(int i=0;i<60;i++)
    {
        if(c[u]>>i&1)
        {
            if(col[i][fa]!=-1) col[i][u]=col[i][fa];
            else col[i][u]=u;
            if(up==-1||d[col[i][u]]<d[up]) up=col[i][u];
        }   
        else col[i][u]=-1;
    }
    jmp[u][0]=up;
    for(int i=0;i<20;i++)
    {
        f[u][i+1]=f[f[u][i]][i];
        if(jmp[u][i]!=-1) jmp[u][i+1]=jmp[jmp[u][i]][i];
    }
    for(auto v:g[u])
        if(v!=fa) dfs(v,u); 
}
int lca(int x,int y)
{
    if(d[x]<d[y]) swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(d[f[x][i]]>=d[y]) x=f[x][i];
        if(x==y) return x;
    }
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int query(int x,int y)
{
    int l=lca(x,y);
    int ans=d[x]+d[y]-d[l]*2;
    if(x==l) swap(x,y);
    if(x==l) return 0;
    if(y==l)
    {
        for(int i=20;i>=0;i--)
            if(jmp[x][i]!=-1&&d[jmp[x][i]]>d[l])
            {
                ans+=1<<i;
                x=jmp[x][i];
            }
        if(c[x]&c[f[x][0]]) return ans;
        else return -1;
    }
    for(int i=20;i>=0;i--)
        if(jmp[x][i]!=-1&&d[jmp[x][i]]>d[l])
        {
            ans+=1<<i;
            x=jmp[x][i];
        }
    for(int i=20;i>=0;i--)
        if(jmp[y][i]!=-1&&d[jmp[y][i]]>d[l])
        {
            ans+=1<<i;
            y=jmp[y][i];
        }
    if(jmp[x][0]==-1||d[jmp[x][0]]>d[l]||jmp[y][0]==-1||d[jmp[y][0]]>d[l]) return -1;
    bool flag=0;
    for(int i=0;i<60;i++)
        if(col[i][x]!=-1&&col[i][y]!=-1)
        {
            if(d[col[i][x]]<=d[l]&&d[col[i][y]]<=d[l]) flag=true;
        }
    if(flag) return ans;
    else return ans+1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(col,-1,sizeof(col)),memset(jmp,-1,sizeof(jmp));
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    dfs(1,0);
    while(q--)
    {
        int x,y;cin>>x>>y;
        cout<<query(x,y)<<'\n';
    }
    return 0;
}

ACM

#哈希 #倍增 #最短路 #2023牛客多校 #Manacher #分治

2023牛客暑期多校训练营3

https://je3ter.github.io/2023/08/22/ACM/2023牛客暑期多校训练营3/

作者

Je3ter

发布于

2023年8月22日

许可协议

牛客练习赛114 上一篇

Kruskal重构树下一篇