"听说黑题做不出来就别想冲省队"... 这样的场景，是否正在您的家庭上演？ 2025 年 NOIP 第四题竟是黑题，而第三题也是黑题，就像游戏里突然把终极 BOSS 放在第二关。有孩子花了 $3$ 小时死磕黑题，结果发现前面藏着能拿 $0$ 分的黑题，这种战略失误比不会做题更令人扼腕。 温水煮蛙型：部分 CSP-S 选…

在讨论《试题和数据已经修复》回复：

qqpp

在文章《小学习.》发表评论：

有点没绷住

Accepted。 ## 题解 他提到重儿子，所以不要树链剖分。令 $son_{x}$ 为 $x$ 的重儿子，$fa_{x}$ 为 $x$ 的父节点。 对于操作 1，dfs 一遍预处理一个数组 $s$ 存以 $x$ 为根的子树重要度和。 对于操作 2，发现其只会影响 $x$，$son_{x}$，$fa_{x}$，所以只…

在讨论《11月21-23日比赛 作弊名单》回复：

qp

## 题意 有一个长度为 $n$ 的序列 $a$，$q$ 次询问，问 $[l,r]$ 中是不是互不相同。 ## 题解 题解区里一车子莫队，但我不会莫队，用一个非常神秘的算法交一发过了，故写题解。 令 $lst_{i}$ 为 $a$ 中与其相同的上一个数的位置，如果一个区间不合法，他肯定同时包含 $lst_{i}$ 和…

Update：对语言进行了润色，增加了自己忘写了的情况。 ## 题面 有一串长度为 $n$ 的颜色序列 $s$，选一段最短区间，对其重排，使得整个序列没有相邻颜色相同的情况，求出这个区间并给出重排后的序列。 特判原序列就满足条件和无解。 ## 题解 原序列就满足条件：枚举一遍序列，判断题目中的条件。 无解：注意到一个颜…

## 题解 一道贪心题。注意到长度为 $2$ 的块对答案的限制作用最大，所以根据不同情况去放。从连续两个位置去看，发现有 $\{0,1\}$，$\{1,0\}$，$\{0,0\}$，$\{1,1\}$ 四种情况。其中，只有 $\{1,1\}$ 的块放长度为 $2$ 的会让答案比放长度为 $1$ 的减小 $1$，所以去看…

你说得对。但是无论什么代价都在所不惜。（题目名字） ## 题面 有一个长度为 $n$ 的序列 $a$，对于每个位置 $i$，对其进行 $+1$ 操作的代价是 $b_{i}$。求最小的代价，使得序列 $a$ 中存在不互质的两个数。 对于这一题的简单版：$b_{i}=1$。 对于这一题的困难版：$1 \le b_{i} \…

在文章《终》发表评论：

越少人看见越好。

我好菜。 今年最后一年高二了。 我还没有七钩。 我完蛋了。 从不知道我的学 OI 这几年在干什么。 几年来感觉啥都没学到。 同组的神都飞升了。 我高一还拿不到六钩，我甚至不敢奖项认证，同组的巨佬看到我高一还五钩，我肯定会被爆爆爆的。 最搞笑的是，我高一才第一次参加 NOIP，第一次坐车去省会考。 充满了遗憾，我的 OI…

在讨论《我有NOIP打吗》回复：

有。

你说得对。但是无论什么代价都在所不惜。（题目名字） ## 题面 有一个长度为 $n$ 的序列 $a$，对于每个位置 $i$，对其进行 $+1$ 操作的代价是 $b_{i}$。求最小的代价，使得序列 $a$ 中存在不互质的两个数。 对于这一题的简单版：$b_{i}=1$。 对于这一题的困难版：$1 \le b_{i} \…

## 题面 有一个树，$q$ 次询问，每次求以 $x$ 为根的子树中的最长路径长度！（话说这题为什么没人写啊 ## 题解 树形 dp。 定义 $f_{x}$ 是以 $x$ 为根的子树中的最长路径长度（就是题目中要求的）。 对 $f_{x}$ 进行分讨： - 这条路径不经过 $x$，那就是在其子节点的子树上取最长路径。…

## 题面 有一个长度为 $k$ 的序列，不管他怎么排列变换，对于任意的自然数 $x$，满足 $s=(((x \bmod a_1) \bmod a_2) \bmod \cdots \bmod a_{k})$ 为定值。 求序列所有元素不大于 $n$ 且序列元素互不相同的方案数，一个序列通过排列变换得到的序列不算一个新的序…

## 题解 注意到最好的方案是将 $a$ 通过操作转化为 $\gcd(a,b)$ 再将其转化为 $b$。 证：若转化到低于 $\gcd(a,b)$ 的数，下一步最优肯定要转化到 $b$ 的因数。由于有 $k$ 的限制，所以在合法方案下，在 $\gcd(a,b)$ 上可以一步转化到的一个数 $x$，在低于 $\gcd(a…

## 题面 给两个 $n \times m$ 的矩阵，可以交换两行，可以交换两列，求第一个矩阵可不可以用若干次操作变成第二个。 ## 题解 不管怎么换，位于同行的总位于同行，位于同列的总位于同列，不可能拆开。 而且，这里因为元素各不相同，所以第一个矩阵中一个元素只能对应到第二个矩阵至多一个元素。 所以要判断是不是对于第…

不给样例解释是这题最大的恶意。 ## 题面 一个矩阵包含 "\*" 和 "."。每次修改一个位置的状态，将其取反（"\*" 变成 "."，"." 变成 "\*"），问将所有 "\*" 排到左侧的最小代价（类似你在桌面上自动排列图标）。 有 $q$ 次修改，对于每个修改都要求最小代价。 ## 题解 统计 "\*" 的数目…

## 题解 诡异的贪心。 有四种策略： 1. 将头尾并成一样的，直接全赋值为 $-10^{9}$； 2. 处理开头一段和结尾一段，使得这两段直接并在一起。 3. 处理开头一段和结尾一段，将端点后的元素加成相同的，赋值中间一段。 4. 处理开头一段和结尾一段，此时开头结尾这两段全为 $-10^{9}$，取这两段的最靠近端…

## 题意 给一个数组，可以将其进行两种操作：翻转，循环右移一位。求最小操作数使得它单调不减。 ## 题面 好的样例创造好的题目，样例使我在打这题时思路特别的顺畅。 首先，发现两种操作都不会影响两个元素的相对位置（相邻的位置仍然相邻，相距 $2$ 的位置仍然相距 $2$）。可以得出翻转不会超过 $2$ 次。 发现右移后…

## 题解 首先，如果 Alice 操作后，Bob 操作了，那么 Alice 可以把他的操作反走一遍，这时 $f(a)$ 的值便会比第一次 Alice 操作后还大，所以对 Bob 来说，他最好在第一次就结束游戏。 所以决定权在 Alice 手中。 Alice 第一次操作肯定要找对答案贡献最大的 $l,r$ 操作。这时候…

## 题解 先求出 $p_{n}$ 的值。 具体地，先从 $1$ 到 $n-1$ 枚举一个数 $x$，询问 $a=[1,1,1,\cdots,1,x+1]$，此时若返回 $0$，则 $p_{n}$ 已经确定，即 $p_{n}=n+1-x$；若返回其他的 $k$，则标记 $p_{k}=p_{n}+x$，求出 $p_{n}…

## 题面 给定一个序列，可抽取其中两个相同的数 $x$ 并将其合并为 $x+1$，问若干次操作后能得到的序列最大值。 ## 题解 你好。 我打这题真是糖丸了。 首先可以发现操作与序列顺序无关，只与各个元素的个数有关，于是可以用桶存每个元素的个数。 然后发现这个合并可以视作一棵二叉树（森林也可以）。 由数值最低的节点一…

## 题面 有一个长为 $n$ 串由 `a` 和 `*` 组成，里面所有的 `*` 都可以替换为 $i$ 个 `b`（$0 \le i \le k$）。求将所有 `*` 替换后，按字典序排序第 $x$ 小的串。 ## 题解 由于不管填法只管可以得到的所有串，所以可以将连续多个 `*` 合并为一个空格，这个空格就可以填…

## 题解 简单 DP。 可以发现栅栏摆放的地方是一段区间，所以可以设 $f_{i,0}$ 为第 $i$ 个栅栏底端的最低高度，$f_{i,1}$ 为最高高度。 那么 $f_{1,0}=f_{1,1}=h_{1}$。 容易想到 $f_{i}$ 会被 $f_{i-1}$ 和 $h_{i}$ 约束。 求 $i$ 最高高度，…

## 题面 一个长为 $n$ 数组 $a$，初始满足 $a_{i}=i$。 可以做不超过 $n+5$ 次操作：每次选定满足 $x \neq y$ 的两个下标 $x,y$，令 $a_{x}=\lceil \frac{a_{x}}{a_{y}} \rceil$。 问是否可以将 $a$ 数组变为含 $n-1$ 个 $1$ 和…

## 题面 一个数组，求数组中大数模小数的最大值。 ## 题解 你好。重复的元素没有用，而且由于只需要满足 $a_{i} \ge a_{j}$，所以可以直接排序并去重。 第一个暴力就是直接从小到大排序并去重，然后枚举 $i \in [1,n],j \in [1,i)$，时间复杂度 $O(n^{2})$。 然后发现这里的…

你好。 ## 题面 分 $m$ 个物品给排成一排的 $n$ 人，求第 $k$ 个人可以拿到的最大物品数，要求相邻的人物品数相差不超过 $1$，且每个人都有物品。 ## 题解 二分第 $k$ 个人可以拿到的物品数 $x$。 若第 $k$ 个人拿到 $x$ 个物品，则可以构造出一种方案，使得这一排人拿到的物品数最小。 如果…

## 题面 有 $m$ 个人分布在 $6 \times n$ 的座位中，这 $m$ 人**按顺序**从它的座位走到位于中央的走廊，然后往前或往后走进第一排前或最后一排后的一个房间。设对于一个人，它经过的人数为 $x$，房间里人数为 $y$，那么它的不满度为 $Ax+By$。最小化所有人不满度的和。 ## 题解 你好。…

## 题解 你好。 莫比乌斯函数为积性函数，因此有 $\mu(ij) = \mu(i)\mu(j)$ 当且仅当 $\gcd(i,j)=1$ 时成立。 所以这个式子可以化为 $$\sum_{i=1}^{n}\sum_{j=1}^{n} \mu(i)\mu(j)ij[\gcd(i,j)=1]$$ 然后因为 $\vareps…