URL

【MX-X23】梦熊 X 组 · 月亮赛（同步赛） - 洛谷 | 计算机科学教育新生态

【MX-J26】梦熊 J 组 · 月亮赛（同步赛） - 洛谷 | 计算机科学教育新生态

我的分数

X组：10分

J组：210分

MX-J26/X23 月亮赛 官方题解

A. 丢手绢

小朋友的编号为 $1 \sim n$，直接处理不够便捷，因此将所有编号减去 1，转换为 $0 \sim n-1$。这样调整后，便能通过取模运算轻松计算出每个被放手绢的小朋友编号。

具体规则如下：设编号为 $x$ 的小朋友被记录的数字为 $a_{x}$，则被放手绢的小朋友编号为 $(x + a_{x}) \mod n$。需特别注意，此处涉及负数取模的情况，计算时需遵循相应的取模规则。

后续操作流程为：统计每个小朋友被投放手绢的次数，找出其中的最大值，再依次输出所有出现最大值的小朋友的位置（此处位置需根据最初编号规则还原，若最终结果需对应 $1 \sim n$ 的编号，需将计算得到的 $0 \sim n-1$ 编号加 1）。

该算法的时间复杂度为 $O(n)$，其中 $n$ 为小朋友的总数，仅需遍历一次所有小朋友的记录即可完成统计与计算。

B. 括号序列

首先进行初步判断：若括号序列中左括号和右括号的数量不相等，则该括号序列一定无法构成合法序列，直接判定为无解。接下来仅针对左右括号数量相等的情况展开分析。

判断括号序列是否合法可通过前缀和的方法实现，具体定义前缀和数组 $a_i$ 如下：

$$ a_{i}= \begin{cases} 0, & i=0 \\ a_{i-1}+1, & s_{i}='(' \\ a_{i-1}-1, & s_{i}=')' \end{cases} $$

当遇到相邻的 “)(” 时，将其修改为 “()”，这一操作的本质是将初始时 “)” 对应位置的前缀和加 1，而其他位置的前缀和保持不变。括号序列合法的核心条件是：所有位置的前缀和 $a_i \geq 0$。

基于此条件，判断流程如下：找到第一个满足 $a_i < 0$ 的位置，若该位置附近存在可修改的 “)(” 结构（即能通过修改使该位置及后续位置的前缀和均非负），则进行修改操作，随后再次检查修改后的括号序列是否满足所有前缀和 $a_i \geq 0$，以此确定序列是否合法。

该算法的时间复杂度为 $O(n)$，$n$ 为括号序列的长度，仅需遍历一次序列即可完成前缀和计算与合法性判断。

C. 猜拳游戏

首先定义 $g = \gcd(n, m)$（即 $n$ 和 $m$ 的最大公约数），并令 $n' = \frac{n}{g}$，$m' = \frac{m}{g}$。

在猜拳游戏中，$10100$ 是一个足够大的数字（其值超过 $\text{lcm}(n, m)$，即 $n$ 和 $m$ 的最小公倍数），因此只需考虑游戏不断进行过程中可能出现的所有状态。

将字符串 $a$（长度为 $n$）和字符串 $b$（长度为 $m$）分别按照下标对 $g$ 取模的余数进行分组，共可分为 $g$ 组。以第 $k$ 组（$0 \leq k < g$）为例，字符串 $a$ 中属于该组的有 $n'$ 个招式，字符串 $b$ 中属于该组的有 $m'$ 个招式，这两组招式两两组合形成的 $n' \times m'$ 种情况，一定会在同一局游戏中全部出现。

若要避免平局，必须保证字符串 $a$ 中该组的 $n'$ 个招式组成的集合与字符串 $b$ 中该组的 $m'$ 个招式组成的集合没有交集（即两组招式完全不同）。

接下来需讨论 “石头（R）、剪刀（P）、布（S）” 这三种招式在字符串 $a$ 和 $b$ 中的可选情况，在所有合法的情况中选择操作次数最少的方案，最后将 $g$ 组的最少操作次数相加，得到最终的答案。

该算法的时间复杂度为 $O(n + m)$，其中 $n$ 和 $m$ 分别为字符串 $a$ 和 $b$ 的长度，需分别遍历两个字符串完成分组与招式集合的判断。

D. 卡常数

首先分析单个数列的情况：对于某一数列，选择其中一个位置 $j$，会使该数列的代价乘以系数 $\frac{a_{i,j} - b_{i,j}}{a_{i,j}}$（其中 $a_{i,j}$ 和 $b_{i,j}$ 为该数列第 $j$ 个元素的相关参数）。由于该系数为真分数，将数列中所有这样的真分数按照从小到大的顺序排列后，从左到右选择这些真分数（即优先选择较小的真分数），能使数列代价的减少量最大，是最优的选择策略。

进一步计算每个数列中，按照上述顺序选择每个元素时，该元素能让数列代价比选择上一个元素后再减少的量，将这个减少量定义为该元素的“价值”。通过分析可发现，在同一个数列中，元素的价值是单调递减的（即越靠后选择的元素，其减少代价的能力越弱）。

基于单个数列的价值特性，将所有数列中所有元素的价值整合到一个集合中，对该集合按照从大到小的顺序排序，然后依次选择价值最大的元素，即可实现整体代价的最小化。

贪心策略正确性证明：由于单个数列内部元素的价值单调递减，后续元素的价值必然小于前面元素的价值，因此在选择时，后续元素不可能先于前面元素被选中，这就保证了将所有元素价值排序后从大到小选择的贪心策略是正确的。

设 $m = \sum l_i$（其中 $l_i$ 为第 $i$ 个数列的长度），则该算法的时间复杂度为 $O(m \log m)$，主要耗时在于对所有元素价值的排序操作。

E. 向死存魏

首先采用离线处理的方式，将所有的“二操作”（具体操作含义需结合题目背景，此处默认是对序列的修改或查询操作）加入到操作序列中。在执行操作的过程中，实时记录当前序列的长度，若某一查询操作要求的答案超过当前序列的长度，则判定该查询无解。设所有操作全部结束后，序列的最终长度为 $k$。

对于删除操作，由于每个元素至多被删除一次，且序列的最终长度为 $k$，因此可使用 $set$ 数据结构对序列进行暴力修改（如标记删除或直接移除元素），操作效率可满足需求。

对于查询操作，首先利用双指针法预处理出初始状态下从序列每个位置开始查询的答案。在后续的删除操作中，针对被删除的元素 $x$，先确定其删除区间：设删除区间左边第一个未被删除的位置为 $p$（若不存在这样的位置，则令 $p = 0$），删除区间右边第一个未被删除的位置为 $q$（若不存在这样的位置，则令 $q = k + 1$）。删除该区间内所有的 $x$ 后，会对起始位置在 $[p + 1, q - 1]$ 范围内的查询产生影响——从这些起始位置开始查询时，需要到位置 $q$ 才能找到元素 $x$。

为高效处理上述区间影响，需对 $[p + 1, q - 1]$ 范围内的当前查询答案进行更新（将答案设为 $q$），此处可使用线段树维护“区间取最值、单点查询”的操作，确保查询与更新的效率。

该算法的时间复杂度为 $O((k + m) \log k)$，其中 $k$ 为序列最终长度，$m$ 为操作总数，线段树的查询与更新操作均为 $O(\log k)$ 复杂度，且需处理 $m$ 次操作。

F. 网格 III

在网格操作中，每一次操作至多会影响 $O(n)$ 个格子（$n$ 为网格的边长或相关维度参数），因此只需关注当前操作实际改变的格子数量即可。

由于行列混合操作较为复杂，可将其拆分为两个独立的部分讨论：一是计算有多少行对当前列的修改产生贡献，二是计算有多少列对当前行的修改产生贡献。下文以“计算行对当前列修改的贡献”为例展开分析。

首先为每行和每列分别记录两个关键信息：最后一次修改的时间、最后一次修改的颜色（如红色或白色）。对于网格中 $k \times k$ 的正方形区域，其对应的所有行列信息仅存在两种不同的有效情况：

1. 该正方形区域内所有列的修改颜色均为红色，且最晚的白色行修改时间在最早的红色列修改时间之前；
2. 该正方形区域内存在列的修改颜色为白色，且所有行的修改颜色均为红色，同时最早的红色行修改时间在最晚的白色列修改时间之后。

由于 $k$ 的取值较小，可直接枚举包含当前列且长度为 $k$ 的区间，暴力查询该区间内的行列信息，进而统计满足上述两种情况的行的数量。为提高效率，对于每行，预先记录所有长度为 $k$ 的区间的信息，每次修改操作仅会改变 $O(k)$ 个区间的信息，后续可通过一维偏序的方法查询满足条件的行数量。

为简化时间与颜色的判断逻辑，对修改时间进行如下处理：若修改颜色为红色，时间值保持不变；若修改颜色为白色，时间值取其相反数。初始状态下，所有行列的修改颜色默认为红色，时间值可设为初始常量（如 0）。经过这样的处理，上述两种情况的判断可转化为对区间内时间值取最小值的操作。

可使用树状数组或线段树维护区间最小值，若直接暴力求区间最小值，算法的时间复杂度为 $O(n k^2 + n k \log n)$；若采用单调队列对区间最小值查询进行优化，时间复杂度可降至 $O(n k \log n)$，其中 $n$ 为网格的相关维度参数，$k$ 为正方形区域的边长。

G. 我爱数数

设 $t_i$ 表示使 $b_i \geq a_i$ 所需的操作次数（$a_i$ 和 $b_i$ 为题目给定的数组元素），则本题的答案等价于求 $E[\max_{i=1}^{n} t_i]$（即 $t_i$ 最大值的期望）。

可通过容斥原理计算该期望，具体公式为：答案等于对所有非空子集 $S \subseteq [n]$，求和 $(-1)^{|S| - 1} \times E[\min_{i \in S} t_i]$（其中 $|S|$ 表示子集 $S$ 的元素个数，$E[\min_{i \in S} t_i]$ 表示子集 $S$ 中 $t_i$ 最小值的期望）。

期望计算分析

假设有 $x$ 个区间满足：对任意 $i \in [l_p, r_p] \cap S$，均有 $c_p < a_i$（$[l_p, r_p]$ 为区间的左右端点，$c_p$ 为区间的相关参数）。此时，剩余的 $m - x$ 个区间（$m$ 为总区间数）一旦被选中，就会覆盖子集 $S$ 中的某个元素，导致 $t_i$ 的值固定。

在上述假设下，$E[\min_{i \in S} t_i]$ 的计算过程如下：

$$ E[\min_{i \in S} t_i] = \sum_{i=0}^{+\infty} \frac{x^i (m - x) (i + 1)}{m^{i + 1}} = \frac{m}{m - x} $$

基于此，定义 $w_x$ 为：对所有满足“恰好有 $x$ 个区间符合上述条件”的子集 $S$，求和 $(-1)^{|S| - 1}$。则最终答案可表示为：

$$ \text{答案} = \sum_{x=0}^{m - 1} w_x \times \frac{m}{m - x} $$

动态规划与优化

为计算 $w_x$，引入辅助函数 $h_i$，定义如下：

$$ h_i = \begin{cases} a_i - 1 & i \in S \\ +\infty & \text{Otherwise} \end{cases} $$

此时，“对任意 $i \in [l_p, r_p] \cap S$，$c_p < a_i$”这一限制条件可转化为“对任意 $i \in [l_p, r_p]$，$c_p \leq h_i$”。

进一步构建小根笛卡尔树（基于 $h_i$ 的值），并在树上进行动态规划。定义状态 $f_{L, R, u, x, 0/1}'$，其含义为：

• 考虑区间 $[L, R]$，仅关注 $h_i \geq u$ 的位置，且 $[L, R]$ 是一个连续段（即 $h_{L - 1} < u$ 且 $h_{R + 1} < u$）；
• 满足 $L \leq l_p \leq r_p \leq R$ 且 $c_p \leq x \leq \min_{i \in [l_p, r_p]} h_i$ 的区间 $p$ 共有 $x$ 个；
• 子集 $T = S \cap [L, R]$ 的元素个数为偶数（对应“0”）或奇数（对应“1”）；
• 该状态的值表示满足上述条件的子集 $T$ 的数量。

令 $f_{L, R, u, x} = f_{L, R, u, x, 0}' - f_{L, R, u, x, 1}'$，并引入辅助数组 $g$，则动态规划的转移公式如下：

$$ g_{L, R, u, x} = f_{L, R, u + 1, x} - \sum_{i=L}^{R} [h_i = u] \sum_{y=0}^{x} f_{L, i - 1, u + 1, y} \times g_{i + 1, R, u, x - y} $$

$$ f_{L, R, u, x} = g_{L, R, u, x - s_{L, R, u}} $$

其中 $s_{L, R, u}$ 表示满足 $L \leq l_p \leq r_p \leq R$ 且 $c_p = u$ 的区间 $p$ 的数量。

时间复杂度优化

若直接按照上述转移公式计算，时间复杂度为 $O(n^4 m^2)$（$n$ 为数组长度，$m$ 为总区间数）。但通过观察可知，$h_i = u$ 的位置对于所有 $u$ 而言，总数仅为 $n$ 个，因此可将时间复杂度优化至 $O(n^3 m^2)$。

进一步利用经典的拉格朗日插值（拉插）技巧，可将转移过程中的卷积运算转化为点乘运算，此时时间复杂度可降至 $O(n^3 m + m^2)$。关于拉格朗日插值技巧的具体应用，可参考题目 CF1874E Jellyfish and Hack。

我的评价

首先，让我吐槽一下这次比赛XJ的题目分配

题目分配

开始吐槽

在我的印象里，CSP-X是小学组的难度，但是，这里为什么X组的难度有NOI，我就感觉很猎奇，而且，为什么J组的第一二题在X组没，Who can tell me?

关于各题

【MX-X23-T1】丢手绢

这道题我大概提交了有好几次，主要是老是TLE，原因是因为写了太多没用的循环，这是AC的代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n,x,i,f[N],ma,s;
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>x;s=i+x;
        while(s<1) s+=n;
        while(s>n) s-=n;
        f[s]++;
        ma=max(ma,f[s]);
    }
    for(i=1;i<=n;i++) if(f[i]==ma) cout<<i<<" ";
}

注意超n和小1的数据处理

【MX-X23-T2】括号串

这道题，我当时是在洛谷搜一道题，叫做括号串匹配，然后，找到了，但是没用，然后我在CSXX上找答案，找到了，但是没用

所以只好独立思考

namespace pts70{
bool check(string s){
    int tmp,i;
    for(i=tmp=0;i<s.length();i++){
        if(s[i]=='(') tmp++;
        else if(s[i]==')'){
            tmp--;
            if(tmp<0) return 0;
        }
    }
    return tmp==0;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>s;fl1=0;
        if(check(s)) fl1=1;
        if(n>1000){cout<<(fl?"Yes":"No")<<"\n";continue;}
        ss=s;
        for(i=0;i<ss.length()-1;i++){
            ss=s;
            if(ss[i]==')'&&ss[i+1]=='('){
                ss[i]='(';ss[i+1]=')';
                if(check(ss)) fl=1;
                else ss=s;
            }
        }
        cout<<(fl?"Yes":"No")<<"\n";
    }
    return 0;
}
}

思路其实也很明显了，就是死暴力，check函数就是判断这个字符串的括号是否合法，然后，20-29行就是两个字符串一个一个往后做，替换，然后判断，可以就输出，不可以就下一个

然后我看了一眼前面那个人的代码，发现是我想多了，代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int T,n,t,w,wz,i,fl1,fl2,sts;
char s[N];
void count(){
    if(s[i]=='(') t++;
    if(s[i]==')') w++;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;t=w=0;fl1=1;
        for(i=1;i<=n;i++){
            cin>>s[i];
            count();
            if(t<w){fl1=0;wz=i;}
        }
        if(t==w){
            sts=1;
            if(fl1==1){cout<<"Yes\n";sts=0;continue;}
            swap(s[wz],s[wz+1]);
            t=w=0;fl2=1;
            for(i=1;i<=n;i++){
                count();
                if(t<w) fl2=0;
            }
            if(wz==n) fl2=0;
            if(sts==1) cout<<(fl2?"Yes":"No")<<"\n";
        }else{cout<<"No\n";continue;}
    }
}

【MX-X23-T3】猜拳游戏

不会做，这个代码 10pts

#include <bits/stdc++.h>
using namespace std;

int main(){
    cout<<1;
}