A 小橘编译器

知识点：字符串，模拟

按照题意模拟即可。先判断给定字符串是否含有 // ，如果没有，直接输出原字符串，如果有，则再判断字符串是不是以 // 开头，是则输出 null，否则输出删去被忽略的后缀得到的字符串。

参考代码：

void solve()
{
    string s;
    cin>>s;
    auto pos=s.find("//");
    if(pos==string::npos)
        cout<<s<<el;
    else if(pos==0)
        cout<<"null\n";
    else
        cout<<s.substr(0,pos)<<el;
}

B 小橙的好序列

知识点：组合数学，差分

思路一：

$a_0$ 的值固定为 $0$ ，从 $i=1$ 开始， $a_i$ 的可选值只与 $a_{i-1}$ 有关，为 $[a_{i-1}-k,a_{i-1}+k]$ 区间中的整数，共有 $2k+1$ 种，由分布乘法原理，可知总方案数为 $(2k+1)^n$ ，注意答案需要对 $998\,244\,353$ 取模。

思路二：

从差分的角度考虑，令 $c_i=a_i-a_{i-1}$ ， $i=1,2,\dots,n$ ，则有好序列的差分序列满足对任意 $i$ 都有 $|c_i|\leq k$ 。反过来说，任意满足上诉条件的差分序列对应唯一一个好序列，可以直接考虑有多少个这样的差分序列，每个 $c_i$ 独立，取值为 $[-k,k]$ 区间中的整数，不难得到总方案数为 $(2k+1)^n$ 。

参考代码：

using LL=long long;
const int p=998244353;
void solve()
{
    LL n,k,ans=1;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        ans=ans*(2*k+1)%p;
    cout<<ans<<'\n';
}

C 小橙的完美序列

知识点：位运算，哈希表

先考虑如果一个序列是「完美序列」具有什么性质。

不妨设 $b_1,b_2,\dots,b_m$ ，是一个「完美序列」，则存在一个 $x$ ，满足 $b_i=i\oplus x$ ，换一个形式，其实就是 $b_i\oplus i=x$ （原等式两边同时异或 $i$ 得到），也就是序列上每一个元素异或这个元素的下标得到同一个值；反过来说，如果序列上每一个元素异或下标都得到同一个值，那么这个序列是「完美序列」。

于是，计算 $a_1,a_2,\dots,a_n$ 改成「完美序列」所需的最少操作次数，只需要对每个 $a_i$ 异或它的下标，统计新序列哪一个元素出现次数最多，记这个最多次数为 $k$ ，那么答案就是 $n-k$ 。

void solve()
{
    int n,a,k=1;
    cin>>n;
    map<int,int>cnt;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        cnt[a^i]++;
    }
    for(auto [_,b]:cnt)
        k=max(k,b);
    cout<<n-k<<el;
}

DE 小橙的幸运数

知识点：模运算，记忆化搜索，基环树，贪心，倍增

思路一：

根据题意可以得到，每一次操作会使 $x$ 不变或增加，增量最多有 $m$ 种，每次增量仅由 $x~\text{mod}~m$ 决定，这启示我们可以从同余类的角度考虑，同余类用通俗的话来说就是：所有整数，按对 $m$ 取模后得到的结果进行分类，最终会得到 $m$ 个互相不交的集合。

现在回到问题，

每一次操作会使 $x$ 不变或增加，如果初始值就大于目标值 $c$ ，显然是 No；
我们称 $x=c$ 为目标，称 $x\equiv c~(\text{mod}~m)$ 为弱化目标。若 $x$ 能通过若干次操作达到目标，则在达到目标的过程中，一定会至少一次达到弱化目标。
在操作前，令 $x_0=x$ ，模拟操作过程，第 $1$ 次操作产生的新值为 $x_1$ ，其中 $x_1=x_0+a_{(x_0~\text{mod}~m)}$ ，以此类推，得到 $x_2,x_3,x_3\dots$ ，其中 $x_i=x_{i-1}+a_{(x_{i-1}~\text{mod}~m)}$ 。如果在达到弱化目标前，先有某两个值满足 $x_i\equiv x_j~(\text{mod}~m)$ ，不难可知，之后 $x$ 会在同余类上会陷入循环，永远无法达到弱化目标，是 No。
若达到弱化目标，此时 $x>c$ 是 No， $x=c$ 是 Yes， $x<c$ 则进入下一步；
我们已经有 $x\equiv c~(\text{mod}~m)$ 了，继续操作，如果能再次使 $x\equiv c~(\text{mod}~m)$ ，记录这个过程的总增量 $d$ ，只需要判断对于此时的 $x$ 是否满足 $c-x$ 是 $d$ 的倍数，即可得到结果；如果不能再次达到弱化目标，陷入其他循环，显然是 NO。

对于 easy 版，步骤3和5都可以直接迭代模拟，迭代不超过 $m$ 次会陷入循环或达到弱化目标，复杂度 $O(mq)$ 。

对于 hard 版，直接迭代的复杂度是不可接受的。考虑步骤3，令 $f(i)$ 表示满足 $x\equiv i~(\text{mod}~m)$ 的初始值 $x$ ，达到 $x\equiv c~(\text{mod}~m)$ 时，需要的最少总增量，可以使用记忆化搜索计算；也可以从图的角度考虑，对 $m$ 个同余类建立节点，根据序列 $a$ 连接 $m$ 条边，会得到若干个基环树，之后计算节点间的距离。考虑步骤5，对于 $x$ 满足 $x\equiv c~(\text{mod}~m)$ ，如果继续操作能再次使 $x\equiv c~(\text{mod}~m)$ ，则这个过程的总增量 $d$ 值不会变化，只需计算一次即可。总复杂度 $O(m+q)$ 。

参考代码（记忆化搜索做法）：

#define int long long
void solve()
{
    int m,c,q;
    cin>>m>>c>>q;
    int cc=c%m;
    vector<int>a(m),f(m,-1),vis(m);
    for(int i=0;i<m;i++)
        cin>>a[i];
    f[cc]=0,vis[cc]=1;
    auto cal=[&](auto &self,int x)->int
    {
        if(vis[x])
            return f[x];
        vis[x]=1;
        int res=self(self,(x+a[x])%m);
        if(res!=-1)
            f[x]=res+a[x];
        return f[x];
    };
    int d=-1;
    if(cal(cal,(cc+a[cc])%m)!=-1)
        d=cal(cal,(cc+a[cc])%m)+a[cc];
    while(q--)
    {
        int x;
        cin>>x;
        int dx=cal(cal,x%m);
        if(dx==-1)
        {
            cout<<"No\n";
            continue;
        }
        x+=dx;
        if(x==c)
            cout<<"Yes\n";
        else if(x>c || d==-1 || (c-x)%d!=0)
            cout<<"No\n";
        else
            cout<<"Yes\n";
    }
}

思路二：

序列 $a$ 的值是非负整数，每次操作后 $x$ 的值单调不减，可以考虑使用倍增。令 $f[i][j]$ 表示对于满足 $x\equiv i~(\text{mod}~m)$ 的初始值 $x$ ，进行 $2^j$ 次操作的总增量，预处理 $f[i][j]$ 数组，每次询问，不断贪心地增加 $x$ ，判断能否到达 $c$ ，总复杂度 $O((m+q)\text{log}A)$ 。关于此思路更详细的说明，可以观看 $\text{wzgg}$ 的视频题解。

（题外话：如果将序列 $a$ 的值扩展到负整数，思路二的倍增将无法处理，但思路一的记忆化搜索仍然可以计算）

F 小橙的异或和

知识点：均摊分析，并查集

思路一：

每一个 $a_i$ 在进行不超过 $30$ 次除以大于 $1$ 的正整数，会变为 $0$ ，而 $0$ 除以任何数都为 $0$ ，换一句话说，每一个 $a_i$ 在变成 $0$ 之前最多变化不超过 $30$ 次，如果变成 $0$ 则之后将不再变化。

于是，可以考虑维护一个下标集合 $S$ ，若 $i\in S$ ，代表当前 $a_i$ 非零，每次操作一，直接修改区间内的所有非零元素，同时维护异或和，集合 $S$ 在C++中可以简单地使用 set 维护，总复杂度为 $O(n\text{log}n\text{log}A)$ 。

思路二：

用并查集维护，创建 $n$ 个节点的并查集，初始时，每个节点指向自身，如果 $a_i$ 变成 $0$ ，则将第 $i$ 个节点指向 $i+1$ 节点，于是，每次查找节点 $i$ 的根节点就可以找到下标从 $i$ 开始的第一个非零元素的下标。总复杂度 $O(n\alpha(n)\text{log}A)$ 。

（此外，也有线段树上二分，势能线段树等做法，在此不多赘述）

参考代码（并查集做法）：

void solve()
{
    int n,q,ans=0;
    cin>>n>>q;
    vector<int>a(n+1),fa(n+2);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ans^=a[i];
        fa[i]=i;
    }
    fa[n+1]=n+1;
    auto find=[&](auto &self,int u)->int
    {
        return fa[u]==u?u:fa[u]=self(self,fa[u]);
    };
    while(q--)
    {
        int op,l,r;
        cin>>op;
        if(op==2)
        {
            cout<<ans<<"\n";
            continue;
        }
        cin>>l>>r;
        for(int i=find(find,l);i<=r;i=find(find,i+1))
        {
            ans^=a[i];
            a[i]/=i-l+1;
            if(!a[i])
                fa[i]=i+1;
            ans^=a[i];
        }
    }
}

G 小橙交换水果

知识点：最近公共祖先，树上前缀和，多源BFS

令 $\text{dist}(u,v)$ 为节点 $u$ 和节点 $v$ 的距离， $\text{near}[i]$ 为度数大于 $2$ 的节点到节点 $i$ 的距离，对于询问 $u$ 和 $v$ ，我们有以下结论：

若树上不存在度数大于 $2$ 的节点，则无解。
若在 $u$ 和 $v$ 的简单路径上，不包括端点 $u$ 和 $v$ ，存在度数大于 $2$ 的节点，则最少操作次数为 $2\times \text{dist}(u,v)+2$ ；
若在 $u$ 和 $v$ 的简单路径上，不包括端点 $u$ 和 $v$ ，不存在度数大于 $2$ 的节点，则最少操作次数为 $2\times \text{dist}(u,v)+4\times \min(\text{near}[u],\text{near}[v])+4$ 。

判断简单路径上，不包括端点，是否存在度数大于 $2$ 的节点，可以通过树上前缀和得到：对于度数大于 $2$ 的节点，赋一个权值 $1$ ，计算树上前缀和数组 $\text{pre}[i]$ ，其中 $\text{pre}[i]$ 表示从节点 $i$ 到根节点的权值和，则 $u$ 到 $v$ 简单路径的权值和为 $\text{pre}[u]+\text{pre}[v]-\text{pre}[\text{lca(u,v)}]-\text{pre}[\text{fa}(\text{lca(u,v)})]$ ，再减去两个端点 $u$ 和 $v$ 的权值，就可以得到简单路径不包括端点的权值和，通过这个权值和是否大于 $0$ ，判断是否有度数大于 $2$ 的节点。

$\text{near}[]$ 数组可以通过一次多源BFS 得到：BFS的起点为所有度数大于 $2$ 的节点，计算最短路。

总复杂度 $O(n\log n+q\log n)$ 或 $O(n\log n+q)$ ，取决于LCA的实现方式。

参考代码：

void solve()
{
    int n,q;
    cin>>n>>q;
    vector<vector<int>>g(n+1);
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>dep(n+1);
    vector<array<int,21>>fa(n+1);
    auto dfs=[&](auto &self,int u,int fau)->void
    {
        dep[u]=dep[fau]+1;
        fa[u][0]=fau;
        for(int i=1;i<21;i++)
            fa[u][i]=fa[fa[u][i-1]][i-1];
        for(auto v:g[u])
            if(v!=fau)
                self(self,v,u);
    };
    dfs(dfs,1,0);
    auto lca=[&](int u,int v)->int
    {
        if(dep[u]<dep[v])
            swap(u,v);
        for(int i=20;i>-1;i--)
            if(dep[fa[u][i]]>=dep[v])
                u=fa[u][i];
        if(u==v)
            return u;
        for(int i=20;i>-1;i--)
            if(fa[u][i]!=fa[v][i])
            {
                u=fa[u][i];
                v=fa[v][i];
            }
        return fa[u][0];
    };
    vector<int>pre(n+1),near(n+1),vis(n+1);
    queue<int>que;
    int ok=0;
    for(int u=1;u<=n;u++)
        if(g[u].size()>=3)
        {
            ok=1;
            pre[u]=1;
            que.push(u);
            vis[u]=1;
        }
    auto dfs2=[&](auto &self,int u,int fau)->void
    {
        pre[u]+=pre[fau];
        for(auto v:g[u])
            if(v!=fau)
                self(self,v,u);
    };
    dfs2(dfs2,1,0);
    while(que.size())
    {
        int u=que.front();
        que.pop();
        for(auto v:g[u])
            if(!vis[v])
            {
                near[v]=near[u]+1;
                vis[v]=1;
                que.push(v);
            }
    }
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        if(!ok)
        {
            cout<<-1<<el;
            continue;
        }
        int ll=lca(u,v),dist=dep[u]+dep[v]-dep[ll]*2;;
        if(pre[u]+pre[v]-pre[fa[ll][0]]-pre[ll]-(g[u].size()>=3)-(g[v].size()>=3)>0)
            cout<<dist*2+2<<el;
        else
            cout<<dist*2+min(near[u],near[v])*4+4<<el;
    }
}

题解 | 小白月赛 Round 129

A 小橘编译器

B 小橙的好序列

C 小橙的完美序列

DE 小橙的幸运数

F 小橙的异或和

G 小橙交换水果