关于 MX-S11
感受
我也不是打 noip 的货，也很菜
题解
梦熊 NOIP 2025 模拟赛 3 题解
T1 战争游戏
题目描述
游戏在一行 $n$ 个城市上进行，城市 $i$ 初始有士兵 $a_i$ 人。前 $m$ 个城市属于小L，其余属于小K，两人交替操作，小L先手。操作包含三种：
- 转移：选择己方地盘上相邻（$|x-y|=1$）的两个城市 $x$、$y$，将 $x$ 的所有士兵转移到 $y$，$a_x$ 变为 0。
- 攻占：选择己方城市 $x$ 和对方相邻城市 $y$，小L操作需满足 $a_x > a_y$，小K操作需满足 $a_x \geq a_y$，攻占后 $y$ 归己方，士兵转移方式同转移操作。
- 不进行任何操作。
当一方占据所有城市时获胜，需对 $m=1,2,...,n-1$ 分别输出获胜方。
关键思路
- 特殊性质B：若先手第一步无法攻占，双方会优先集中兵力，最终比较分界线两侧总兵力。
- 特殊性质C：若先手第一步可攻占对方城市且后手无法反制，比较攻占后两侧总兵力。
- 正解：先手攻占后需判断对手是否能反制，若能则选择转移兵力，否则执行攻占，核心是比较关键状态下的兵力总和。
T2 加减乘除
题目描述
给定一棵以 1 为根的树，每个节点 $u$ 有运算符号 $op_u$（加或减）和数值 $a_u$。$q$ 次询问，每次给定 $x$，从根节点出发，需满足边的范围条件 $[l_v, r_v]$（即经过节点 $u$ 运算后的 $x'$ 需在子节点 $v$ 的边范围内）才能走向子节点，求能到达的节点个数。
正解
- 区间预处理：每个节点 $u$ 对应可到达的 $x$ 区间 $[L_u, R_u]$，初始根节点区间为 $[-\infty, +\infty]$。
- 区间更新：向下遍历树时，运算操作会平移区间，边的范围条件会取区间交集，以此递推得到所有节点的 $[L_u, R_u]$。
- 高效查询：对所有区间端点离散化，用差分法给每个区间 $[L_u, R_u]$ 加 1，查询时二分找到 $x$ 对应的区间，即可得到答案。
- 时间复杂度：$O((n+q) \log n)$。
T3 空之碎物
题目描述
定义二进制不退位减法 $\ominus$，给定序列 $a$，对于区间 $[l, r]$，$f(l, r)$ 表示将该区间元素作为多重集，经若干次合并操作（选两个数合并为其不退位减法结果）后剩余的最大值。求 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} f(i, j)$ 对 998244353 取模的值。
核心性质
- 性质1：最终操作结果可表示为 $x \ominus(y \ominus a_1 \ominus a_2 \ominus ... \ominus a_{n-2})$（$a_1~a_{n-2}$ 为除 $x,y$ 外的元素）。某二进制位无1时无影响，恰好一个1时贡献由 $y$ 选择决定，至少两个1时贡献为0。
- 性质2：若区间长度超过 $\log_2 V + 2$（$V$ 为元素最大值，此处 $V < 2^{25}$），则 $f(l, r)$ 等于区间最大值。
正解
- 处理长区间：直接累加所有长度超过 $\log_2 V + 2$ 的区间的最大值。
- 处理短区间：枚举每个二进制位，对该位有两个1的元素建立连边，通过枚举连边计算贡献，时间复杂度 $O(n \log_2^2 V)$。
T4 Ice Drop
题目描述
一个正整数序列是“好的”，当且仅当对任意正整数 $k$，序列中所有 $k$ 的倍数位置连续。给定序列 $a$，$f(b)$ 表示满足以下条件的“好的”序列 $b'$ 的数量：
- $|b'| = |b|$；
- 若 $b_i > 1$，则 $b_i' = b_i$；
- $LCM(b_1,...,b_m) = LCM(b_1',...,b_m')$（$m$ 为 $b$ 的长度）。
$q$ 次询问，每次给定 $l, r$，求 $\sum_{x=l}^{r} \sum_{y=x}^{r} f(a[x,y])$ 对 $10^9+7$ 取模的值。
关键思路
- 核心等价：序列是“好的”等价于每个质因子的指数序列是单峰的。
- 特殊性质A（$q=1$）：不能新增质因子，也不能超过原质因子最大指数，通过组合数计算合法填充方式，答案为各质因子贡献乘积。
- 特殊性质B：若只有一个质因子，合法区间是若干不交区间的子集，答案非0即1。
- 正解：用扫描线结合线段树，维护全局乘、单点修、查历史和，对每个不交区间单独处理，时间复杂度 $O(n \log n)$。
个人代码
T1
主要思路：骗分
#include <bits/stdc++.h>
using namespace std;
int T,n,i,m,ma,t,a[100010];
string ans;
int main(){
cin>>T;
while(T--){
cin>>n;t=ma=0;ans="";
for(i=1;i<=n;i++)
cin>>a[i],ma+=a[i];
for(m=1;m<n;m++){
t+=a[m];
if(2*t>ma) ans+='1';
else ans+='0';
}
cout<<ans<<"\n";
}
}太好力，又水了一篇 blog
MX-S11
