关于 MX-S11

博主： admin
发布时间：2025 年 11 月 19 日
14 次浏览
暂无评论
2426字数
分类： OI 编程 Online Judge 梦熊OJ

# 感受

我也不是打 noip 的货，也很菜

# 题解

## 梦熊 NOIP 2025 模拟赛 3 题解

### T1 战争游戏

#### 题目描述

游戏在一行 $n$ 个城市上进行，城市 $i$ 初始有士兵 $a_i$ 人。前 $m$ 个城市属于小L，其余属于小K，两人交替操作，小L先手。操作包含三种：

1. 转移：选择己方地盘上相邻（$|x-y|=1$）的两个城市 $x$、$y$，将 $x$ 的所有士兵转移到 $y$，$a_x$ 变为 0。
2. 攻占：选择己方城市 $x$ 和对方相邻城市 $y$，小L操作需满足 $a_x > a_y$，小K操作需满足 $a_x \geq a_y$，攻占后 $y$ 归己方，士兵转移方式同转移操作。
3. 不进行任何操作。
   当一方占据所有城市时获胜，需对 $m=1,2,...,n-1$ 分别输出获胜方。

#### 关键思路

1. 特殊性质B：若先手第一步无法攻占，双方会优先集中兵力，最终比较分界线两侧总兵力。
2. 特殊性质C：若先手第一步可攻占对方城市且后手无法反制，比较攻占后两侧总兵力。
3. 正解：先手攻占后需判断对手是否能反制，若能则选择转移兵力，否则执行攻占，核心是比较关键状态下的兵力总和。

### T2 加减乘除

#### 题目描述

给定一棵以 1 为根的树，每个节点 $u$ 有运算符号 $op_u$（加或减）和数值 $a_u$。$q$ 次询问，每次给定 $x$，从根节点出发，需满足边的范围条件 $[l_v, r_v]$（即经过节点 $u$ 运算后的 $x'$ 需在子节点 $v$ 的边范围内）才能走向子节点，求能到达的节点个数。

#### 正解

1. 区间预处理：每个节点 $u$ 对应可到达的 $x$ 区间 $[L_u, R_u]$，初始根节点区间为 $[-\infty, +\infty]$。
2. 区间更新：向下遍历树时，运算操作会平移区间，边的范围条件会取区间交集，以此递推得到所有节点的 $[L_u, R_u]$。
3. 高效查询：对所有区间端点离散化，用差分法给每个区间 $[L_u, R_u]$ 加 1，查询时二分找到 $x$ 对应的区间，即可得到答案。
4. 时间复杂度：$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. 性质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. 性质2：若区间长度超过 $\log_2 V + 2$（$V$ 为元素最大值，此处 $V < 2^{25}$），则 $f(l, r)$ 等于区间最大值。

#### 正解

1. 处理长区间：直接累加所有长度超过 $\log_2 V + 2$ 的区间的最大值。
2. 处理短区间：枚举每个二进制位，对该位有两个1的元素建立连边，通过枚举连边计算贡献，时间复杂度 $O(n \log_2^2 V)$。

### T4 Ice Drop

#### 题目描述

一个正整数序列是“好的”，当且仅当对任意正整数 $k$，序列中所有 $k$ 的倍数位置连续。给定序列 $a$，$f(b)$ 表示满足以下条件的“好的”序列 $b'$ 的数量：

1. $|b'| = |b|$；
2. 若 $b_i > 1$，则 $b_i' = b_i$；
3. $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$ 取模的值。

#### 关键思路

1. 核心等价：序列是“好的”等价于每个质因子的指数序列是单峰的。
2. 特殊性质A（$q=1$）：不能新增质因子，也不能超过原质因子最大指数，通过组合数计算合法填充方式，答案为各质因子贡献乘积。
3. 特殊性质B：若只有一个质因子，合法区间是若干不交区间的子集，答案非0即1。
4. 正解：用扫描线结合线段树，维护全局乘、单点修、查历史和，对每个不交区间单独处理，时间复杂度 $O(n \log n)$。

# 个人代码

## T1

主要思路：骗分

```cpp
#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

最后修改：2025 年 11 月 19 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱

地址

关于 MX-S11

admin • 2025 年 11 月 19 日

# 感受

我也不是打 noip 的货，也很菜

# 题解

## 梦熊 NOIP 2025 模拟赛 3 题解

### T1 战争游戏

#### 题目描述

游戏在一行 $n$ 个城市上进行，城市 $i$ 初始有士兵 $a_i$ 人。前 $m$ 个城市属于小L，其余属于小K，两人交替操作，小L先手。操作包含三种：

#### 关键思路

### T2 加减乘除

#### 题目描述

#### 正解

### T3 空之碎物

#### 题目描述

#### 核心性质

#### 正解

### T4 Ice Drop

#### 题目描述

#### 关键思路

# 个人代码

## T1

主要思路：骗分

太好力，又水了一篇 blog
MX-S11

关于 MX-S11

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

IP地址修改器 [bilibili配套]

关于 2025 CSP

个人对于身高歧视的评价

FMCRAFT Res领地插件使用教程【官方 and 非官方】

关于 2025 年浙江省初中名校发展共同体七年级第一学期考试反思

2025年10月12日学校编程集训感言

学校训练栈+队列+堆+优先队列【历史存档】

教你快速搭建一个文件快递柜[filecodebox使用教程]

HUSTOJ常见问答（Plus版）

教你“正确”运用malloc函数（附原理）

关于 MX-S11

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

关于 MX-S11

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款