感受

我也不是打 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

主要思路：骗分

#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