ABC460

本次赛时只有3题，D题没有写方向数组，八个方向全手搓，导致写了非常久，调试也极其困难，实际上就是个简单的BFS题。而E题作为数论题也是比较简单，是可以尝试解决的。

A

问题陈述

您将获得正整数 $N$ 和 $M$ 。

如果重复执行以下操作，而 $M$ 的值不是 $0$ ，请找出执行的操作次数。

• 设 $x$ 为 $N$ 除以 $M$ 的余数。将 $M$ 的值替换为 $x$ 。

可以证明，经过有限次数的运算后， $M$ 变成了 $0$ 。

思路:

按照题意模拟并计数即可。

Code

void sol()
{
    int M,N;
    cin>>N>>M;
    int cnt=0;
    while(M)
    {
        M=N%M;
        cnt++;
    }
    cout<<cnt;
}

B

问题陈述

$xy$ \平面上有两个圆 $C_1$ 和 $C_2$ 。在这个问题中，圆指的是圆周而非圆面。
圆 $C_1$ 的圆心为 $(X_1, Y_1)$ ，半径为 $R_1$ 。
圆 $C_2$ 的圆心为 $(X_2, Y_2)$ ，半径为 $R_2$ 。
确定圆 $C_1$ 和 $C_2$ 是否有公共点。换句话说，判断是否存在至少一个到 $(X_1, Y_1)$ 的距离为 $R_1$ 且到 $(X_2, Y_2)$ 的距离为 $R_2$ 的点。

您获得了 $T$ 个测试用例；逐一解决。

思路:

题意为判断两圆是否相交，即不相离、不内含。

Code

void sol()
{
    int X1,Y1,R1,X2,Y2,R2;
    cin>>X1>>Y1>>R1>>X2>>Y2>>R2;
    if((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)<=(R1+R2)*(R1+R2)&&(X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)>=(R1-R2)*(R1-R2))
    {
        cout<<"Yes\n";
    }
    else cout<<"No\n";
}

C

问题陈述

寿司的原料有 $N$ 块醋饭和 $M$ 块内塔（配料）。

第 $i$ 个shari的权重是 $A_i$ ，第 $j$ 个neta的权重是 $B_j$ 。

您将结合 Shari 和 Neta 制作寿司。

要制作一件寿司，您需要将一份 Shari 和一份 Neta 结合在一起。这里， Neta 的重量最多是 Shari 重量的两倍。此外，相同的 Shari 或 Neta 不能用于多份寿司。

求最多可以制作多少个寿司。

思路:

对于第$i$个Shari和第$j$个Neta，满足$A_i\times 2\ge B_j$时，才能结合在一起。
因此我们将$A$和$B$排序后，利用指针$i$和$j$，分别对$A$和$B$进行扫描：

• 如果当前的$i$和$j$不满足条件，那么就将$i$向后移动。
• 如果当前的$i$和$j$满足条件，那么就将他们组合成寿司，$ans$累加，并将$i$和$j$均向后移动，防止重复使用。（注意越界判定）

Code

void sol()
{
    int N,M;
    cin>>N>>M;
    for(int i=1;i<=N;i++)cin>>A[i];
    for(int i=1;i<=M;i++)cin>>B[i];
    sort(A+1,A+N+1);
    sort(B+1,B+M+1);
    int j=1,ans=0;
    for(int i=1;i<=N;i++)
    {
        if(B[j]>2*A[i]&&j<=M)continue;
        if(j>M)break;
        ans++;
        j++;
    }
    cout<<ans;
}

补题

D

问题陈述

有一个包含 $H$ 行和 $W$ 列的网格。从上数第 $i$ 行、从左数第 $j$ 列的单元格称为单元格 $(i, j)$ 。

每个细胞都是白色或黑色的。网格由 $H$ 字符串 $S_1, S_2, \ldots, S_H$ 描述，每个字符串的长度为 $W$ 。如果 $S_i$ 的第 $j$ 个字符是 .，则单元格 $(i, j)$ 为白色；如果 $S_i$ 的第 $j$ 个字符是 #，则单元格 $(i, j)$ 为黑色。

您执行以下操作 $10^{100}$ 次。

• 同时将以下规则应用于所有单元格。
  • 当且仅当存在至少一个与其相邻的黑色单元格时，操作前为白色的单元格才会变为黑色。这里，单元格 $(x, y)$ 和 $(x', y')$ 是相邻的，当且仅当其中一个单元格位于另一个单元格的 $8$ -邻域内，即 $\max(|x-x'|, |y-y'|) = 1$ 。
  • 操作前为黑色的单元格变为白色。

求操作后每个单元格的颜色。

分析:

每次操作会使黑格子变白格子，并且将周围有黑格子的白格子变黑。执行$10^{100}$次操作，显然我们无法模拟这么多次，我们只能找变化规律。

• 显然，当白格子周围有黑格子时，经过偶数次变化，两者颜色不变；经过奇数次变化，两者颜色交换。（以下简称其为互锁格子）

我们找到所有互锁格子后，剩下的非互锁格子必定全为黑色或白色，且这些互锁格子的边缘一定是相应的黑色或白色。

• 若全为黑色，则经过一次变换后，就会转变成了全为白色的情况。（后续以全白说明）

由于互锁格子会根据操作次数不断变化，当外侧变为黑色时，下一次变化就会将黑色向外传递到非互锁格子，而再下一次，会再往外传递（因为外面为白色），如此就会像波一样不断向外扩散，而互锁格子就如同脉冲信号一样，不断间歇地产生波，周期为2，那么对于波经过偶数次的格子，其颜色仍为白色，经过奇数次的格子，其颜色变黑。
而在网格上，实际上就是判断非互锁格子距离其最近的黑色格子的切比雪夫距离的奇偶性。
切比雪夫距离：$d_{\text{Chebyshev}}((x_1, y_1), (x_2, y_2)) = \max(|x_1 - x_2|, |y_1 - y_2|)$

思路：

考虑到非互锁格子可能为黑色，而黑色又比较特殊，所以我们需要先模拟进行一次操作。
我们找到所有周围有黑色格子的白色格子并记录下来后，将所有黑色格子变为白色，再将记录下来的白色格子变黑，就实现了一次操作。
求切比雪夫距离就用多源BFS计算即可。

复杂度$O(H\times W)$

Code

void sol()
{
    int H,W;
    cin>>H>>W;
    for(int i=1;i<=H;i++)
    {
        cin>>S[i];
        S[i]=" "+S[i];
    }
    vector<vector<int>>dis(H+5,vector<int>(W+5,-1));
    queue<pair<int,int> >q;
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
        {
            if(S[i][j]=='#')continue;
            bool fg=0;
            for(int k=0;k<8;k++)
            {
                int sx=i+x[k],sy=j+y[k];
                if(sx<1||sy<1||sx>H||sy>W)continue;
                if(S[sx][sy]=='#')
                {
                    fg=1;
                    break;
                }
            }
            if(fg)q.push({i,j});
        }
    }
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
        {
            if(S[i][j]=='#')S[i][j]='.';
        }
    }
    while(q.size())
    {
        auto [tx,ty]=q.front();
        q.pop();
        S[tx][ty]='#';
    }
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
        {
            if(S[i][j]=='#')
            {
                dis[i][j]=0;
                q.push({i,j});
            }
        }
    }
    if(q.empty())
    {
        for(int i=1;i<=H;i++)
        {
            for(int j=1;j<=W;j++)
            {
                cout<<'.';
            }
            cout<<'\n';
        }
        return;
    }
    while(q.size())
    {
        auto [tx,ty]=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            int sx=tx+x[i],sy=ty+y[i];
            if(sx<1||sy<1||sx>H||sy>W||dis[sx][sy]!=-1)continue;
            dis[sx][sy]=dis[tx][ty]+1;
            q.push({sx,sy});
        }
    }
    for(int i=1;i<=H;i++)
    {
        for(int j=1;j<=W;j++)
        {
            cout<<(dis[i][j]%2==0?'.':'#');
        }
        cout<<'\n';
    }
}

E

问题陈述

对于正整数 $a$ 和 $b$ ，将 $\mathrm{concat}(a, b)$ 定义为依次写入 $a$ 和 $b$ 形成的整数。更正式地说， $\mathrm{concat}(a, b)$ 定义如下。

• 令 $A$ 和 $B$ 分别为通过十进制写入 $a$ 和 $b$ 形成的字符串。令 $C$ 为按顺序连接 $A$ 和 $B$ 形成的字符串。将 $C$ 解释为十进制整数的值为 $\mathrm{concat}(a, b)$ 。

例如，如果 $a = 123$ 和 $b = 45$ ，则为 $\mathrm{concat}(a, b) = 12345$ 。

您将获得正整数 $N$ 和 $M$ 。
求不大于 $N$ 的正整数对 $(x, y)$ 的模 $998244353$ 的数量，使得 $\mathrm{concat}(x, y) \equiv x + y \pmod{M}$ 。

您获得了 $T$ 个测试用例；逐一解决。

思路:

数论题，推导过程如图：

$L(x)$表示x的长度，如$L(325799)=6$。

在本题中，由于数据很大，需要用到unsigned long long，并且$\frac{N}{\frac{M}{G}}$不能写成$\frac{N\times G}{M}$，否则数据会溢出

Code

int _10[20];

int L(int x)
{
    int res=0;
    while(x){x/=10;res++;}
    return res;
}
void sol()
{
    int ans=0;
    int N,M;
    cin>>N>>M;
    for(int i=1;i<=L(N);i++)
    {
        int G=__gcd(M,_10[i]-1);
        int sumx=N/(M/G);
        int sumy=9*_10[i-1];
        if(i==L(N))sumy=N-_10[i-1]+1;
        ans=(ans+sumx%mod*(sumy%mod)%mod)%mod;
    }
    cout<<ans<<'\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    _10[0]=1;
    for(int i=1;i<=19;i++)_10[i]=_10[i-1]*10;
    cin>>T;
    while(T--)sol();
}

F

问题陈述

有一棵树，其顶点为 $N$ 。顶点编号为 $1, 2, \ldots, N$ ，第 $i$ 条边连接顶点 $U_i$ 和 $V_i$ 。

最初，所有顶点都涂成黑色。

按顺序处理以下形式的 $Q$ 查询，并找到每个查询的答案。

• 给出一个整数 $x$ $(1 \leq x \leq N)$ 。如果顶点 $x$ 为白色，则将其重新绘制为黑色；如果顶点 $x$ 为黑色，则将其重新绘制为白色。然后，找到两个黑色顶点之间的最大距离。这里，树上两个顶点之间的距离是它们之间的简单路径中的边数。

在给定的输入中，按顺序处理查询时始终至少有两个黑色顶点。

分析：

我们需要求树的直径，首先就需要求树上两点距离，有公式：

$$Distance(u,v)=Deep(u)+Deep(v)-2\times Deep(LCA(u,v))$$

而$LCA$则用倍增法$O(\log N)$、树链剖分$O(\log N)$乃至DFS序+ST表$O(1)$均可。（倍增法是最简单的）
随后我们考虑求直径并且支持动态修改，这里使用线段树来维护。

思路：

线段树节点信息：
对于表示$[l,r]$区间的节点，我们记录$u,v\in [l,r]$，且

$$dist(u,v)=\max\limits_{l\le i,j\le r}dist(i,j)$$

那么树的直径就是线段树根节点对应的$dist$。

$merge$函数：
设线段树中，$x$节点的左孩子是$lc$，右孩子是$rc$。
左孩子$lc$对应的$u=a$，$v=b$，右孩子$rc$对应的$u=c$，$v=d$，则合并区间后的最大距离为$(a,b,c,d)$四点之间的某两点的距离。

$update$函数：
修改$p$位置的颜色后：

• 如果该位置变白，则该点不能被计入直径计算，我们将该节点的$dist$改为$-\infty$，同时$u$和$v$改成0。
• 如果该位置变黑，我们则恢复该点状态，将节点数据$(p,p,0)$。

随后向上更新到线段树根为止。

复杂度$O((Q+N)\log N)$

Code

int dist(int x,int y);

struct Node
{
    int x,y,d;
    Node(int x=0,int y=0):x(x),y(y),d(dist(x,y)){}
    bool operator<(const Node& t)const
    {
        return d<t.d;
    }
};

vector<int>dep,col;
vector<vector<int> >tree,f;
vector<Node>segtre;

void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    for(int i=1;i<=20;i++)
    {
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(auto c:tree[x])
    {
        if(c==fa)continue;
        dfs(c,x);
    }
}

int lca(int x,int y)
{
    if(dep[x]!=dep[y])
    {
        if(dep[x]<dep[y])swap(x,y);
        int tem=dep[x]-dep[y],i=0;
        while(tem)
        {
            if(tem&1)x=f[x][i];
            tem>>=1;
            i++;
        }
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--)
    {
        if(f[x][i]==f[y][i])continue;
        x=f[x][i];
        y=f[y][i];
    }
    return f[x][0];
}

int dist(int x,int y)
{
    if(x==0||y==0)return -1;
    if(x==y)return 0;
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}

Node merge(int x,int y)
{
    Node res=max(segtre[x],segtre[y]);
    res=max(res,Node(segtre[x].x,segtre[y].x));
    res=max(res,Node(segtre[x].x,segtre[y].y));
    res=max(res,Node(segtre[x].y,segtre[y].x));
    res=max(res,Node(segtre[x].y,segtre[y].y));
    return res;
}

void build(int x,int l,int r)
{
    if(l==r)
    {
        segtre[x]=Node(l,l);
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    segtre[x]=merge(x<<1,x<<1|1);
}

void update(int x,int l,int r,int pos)
{
    if(l==r)
    {
        col[l]^=1;
        if(col[l])segtre[x]=Node(l,l);
        else segtre[x]=Node(0,0);
        return;
    }
    int mid=(l+r)>>1;
    if(pos>=mid+1)update(x<<1|1,mid+1,r,pos);
    else update(x<<1,l,mid,pos);
    segtre[x]=merge(x<<1,x<<1|1);
}

void sol()
{
    int N;
    cin>>N;
    dep.assign(N+1,0);
    col.assign(N+1,1);
    tree.assign(N+1,vector<int>(0));
    f.assign(N+1,vector<int>(22));
    segtre.assign(N<<2,Node());
    for(int i=1;i<=N-1;i++)
    {
        int u,v;
        cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1,0);
    build(1,1,N);
    int Q;
    cin>>Q;
    while(Q--)
    {
        int x;
        cin>>x;
        update(1,1,N,x);
        cout<<segtre[1].d<<'\n';
    }
}