在讨论《关于ngoi》回复：

如何参加 NGOI

OOI 超级无敌强强题。 不难发现，如果初始序列中的元素种类本身就只有 $x\le t$ 种，那么答案就是 $1$。 如果原序列中有大于 $t$ 中元素，显然一个人能拿走的长度一定小于 $n$。 我们可以把两个序列 $a$ 拼接起来，就可以计算一个人从某一种元素出发最多能拿多少长度。 注意到 $a_i \in [1,1…

超级牛牛题。 首先考虑如果没有限制节点的重量，即对于 $\forall i$，都有 $w_i=-1$。 有一个贪心的策略显然是优的，考虑从叶子节点开始，父亲相同的节点中随机挑选一个使其值为 $K$，其余的等于 $0$，这样可以保证对于每一层，都能保证其吃满限制，肯定最优。 那么有重量限制怎么办呢？ 我们可以让每个节点的…

在文章《题解：P10907 [蓝桥杯 2024 国 B] 蚂蚁开会》发表评论：

大神 /bx/bx/bx

NOIP 考前复习一下 SPFA 判断负环，刚好今天模拟赛出了一道最短路。 SPFA 的本质就是基于 BFS，通过维护一个队列来遍历所有点并松弛每条边，从而求出最短路。 这道题中就是将松弛操作中的加法改为了乘法，但是随之出现了一个问题，如果存在一个环的每条边都小于 $1$，那么就会出现类似于普通最短路中的“负环”，这也…

## [ARC104D] Multiset Mean 求可重集合 $S$ 的个数，满足 $[1,n]$ 中每个数出现 $[0,k]$ 次且 $S$ 中各个元素的平均数为 $x\in [1,n]$。 对于每个 $S$，和显然是 $cnt\times x$，$cnt$ 为集合内元素个数。 将每个数都减去 $x$，那么就是要…

现有题解的写法好像都和我不太一样，所以写一篇题解。 首先找一个非叶子节点作为这棵树的根节点，然后考虑后序遍历贪心。 设 $s$ 为节点 $u$ 的来自子树的所有配对请求数，该节点可以组成的配对数 $m=\min(\lfloor \frac{s}{2} \rfloor,K)$。 如果还有剩余且 $m using name…

根据曼哈顿距离的定义，$ans=\sum |Dx-x_i|+\sum |Dy-y_i| $，其中 $(Dx,Dy)$ 是曼哈顿距离最小的点。 根据小学奥数可以知道，对于一个一维的序列，若要让 $\sum |x-a_i|$ 最小，那么 $x$ 就一定是序列 $a$ 的中位数。 这一点也可以扩展到二维上，然后就做完了。 但…

很好的 dp 题。 因为 $0 \le R_i,C_i \le 2$，所以矩阵中的所有元素也一定是在 $[0,2]$ 的范围内。 考虑一个三维的 dp，设 $f_{i,j,k}$ 表示前 $i$ 行有 $j$ 列和为 $1$，有 $k$ 列和为 $2$ 的方案数。 第一维应该可以滚动数组掉，但是时间复杂度就是 $O(n…

活动以时刻升序排序，同时同一时刻按城镇排序。设 `dp` 表示以某活动结束时能参加的最大活动数。处理当前活动 `(city, time)` 时有两种来源：同城延续使用 $bestsame_{city}$，得到转移 $bestsame_{city}+1$；跨城转移需要满足 $lst + travel ≤ time - 0…

> CSP 只是 NOIP 前的一次练兵。 记高中生涯的第一次 CSP，也可能是最后一次了。 ### 距离 CSP2025 还有 1 天 校运会。 思来想去，我的 OI 生涯可能马上就要结束了，停课显然不必要，放弃学校的活动训练，是我一直不情愿的。 作为学校摄影社的高一成员，我放弃了在机房安逸的复习备考，在楼下的操场不…

## P4786 [BalkanOI 2018] Election ### 题目大意 有一个长度为 $N$ 的字符串，由 `C` 和 `T` 组成，有 $Q$ 次询问，每次询问给出 $[l,r]$，问该区间内需删除至少多少个 `T` 使得 `T` 和 `C` 的个数相等。 ### 解题思路 首先我们需要转化题意，对于“…

## P2087 GTY的人类基因组计划2 ### 题目大意 给定 $n$ 个人和 $m$ 个房间，初始时所有人都在 $1$ 号房间。有两种操作，第一种是将 $i$ 号人从 $a$ 号房间移动到 $b$ 号房间，第二种是对一段区间里的人数求和，特殊地，每种人的组合只能被加一次和。 其中，$n,m,q\leq 10^5$…

很久没有写做题笔记了，将这两个月做的一些个人认为比较有意义的题都复盘一下。 这里面的题目都不是模拟赛的题，模拟赛的题会再开一篇。 ## [P12195 [NOISG 2025 Prelim] Itinerary](https://www.luogu.com.cn/problem/P12195) ### 题目大意 有一个…

## [AT_arc197_b 大于均值](https://www.luogu.com.cn/problem/AT_arc197_b) ### 解题思路 - 首先对序列 $A$ 排序，并计算其前缀和。 目标是选出一个子序列，其得分为大于子序列均值的元素数量最大。 定义得分为 $\sum_{i=1}^{|x|} \mat…

## [AT_arc197_a 网格路径并](https://www.luogu.com.cn/problem/AT_arc197_a) ### 题目大意 给定一个 $H \times W$ 的白色网格以及一个长度为 $H+W-2$ 的字符串 $S$（字符为 `D`、`R` 和 `?`），其中 - 若 $S_i = \…

## [P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava](https://www.luogu.com.cn/problem/P11860) ### 题目大意 你被困在一个有 $n$ 个房间和 $m$ 条双向隧道构成的地牢中。隧道地板上覆盖着温度为 $c$ 的熔岩，只有当你的耐热…

## [P11861 [CCC 2025 Senior] 写作业 / To-Do List](https://www.luogu.com.cn/problem/P11861) ### 题目大意 维护一个待办任务列表，支持两种加密更新操作： - `A s t`：添加一个任务（发布时间 $s$，所需时间 $t$） - `D…

## [P11906 [NHSPC 2023] E. 迷宫钥匙圈](https://www.luogu.com.cn/problem/P11906) ### 题目大意 给定一个由字母表示的迷宫面板,每一次将迷宫向左或向右旋转 $90$ 度，所有还在迷宫内的小钢珠会按照特定规则“下落”——直到掉出迷宫、碰到挡板或碰到其它…

## [P11903 [NHSPC 2023] B. 人工智能模拟](https://www.luogu.com.cn/problem/P11903) ### 题目大意 给定 $n$ 个长度为 $k$ 的 `01` 字符串，要求构造一个长度为 $k$ 的字符串，满足： - 与任一给出字符串不完全相同； - 对任意选择的…

## [P12195 [NOISG 2025 Prelim] Itinerary](https://www.luogu.com.cn/problem/P12195) ### 题目大意 有一个树和一个序列，要求按照给出的顺序访问序列中的所有点，问每个点能否作为起点。 ### 解题思路 如果一个方案不合法，当且仅当沿着这个…

在讨论《洛谷讨论区恢复公告》回复：

AT 和 CF 的 RMJ 什么时候回来 /ll /ll

## F - ABCBA ### 题目大意 KMP 板子。 给定一个只包含大写英文字母的字符串 $S$，要求构造一个以 $S$ 为前缀的最短回文字符串。 ### 解题思路 - 将字符串 $S$ 反转得到 $R$。 - 构造字符串 `C = R + # + S`。 - 在 $C$ 上计算 $KMP$ 失配函数，得到末尾位…

## E - Tree Game ### 题目大意 给定一棵有 $N$ 个节点的树，编号为 $1$ 到 $N$。游戏玩家（你）和高桥君轮流向图中添加新的边 $(i,j)$，但只能添加不在图中已有边中出现、且不会形成奇环的边。当一位玩家无法进行有效操作时，该玩家失败。你的任务是决定先手或后手，并与高桥君交互，给出你的操作…

## C - Uniqueness ### 题目大意 给定 $N$ 个人，每人有一个整数 $A_i$，若某人的数在所有人中不重复，则该人满足条件。找出满足条件的人的最大数，并输出此人的编号；若无满足条件者，则输出 $-1$。 ### 解题思路 统计每个整数出现的次数，然后在所有只出现一次的整数中寻找最大值，并输出对应的…

## D - Bonfire ### 题目大意 给定在无限二维平面上的一个焰火位置 $(0, 0)$，每个时刻烟雾会按照方向移动，若时刻 $t$ 烟雾不在 $(0,0)$，则在 $(0,0)$ 处重新生成烟雾。我们要判断在每个半时刻 $(t+0.5)$ 时，给定坐标 $(R, C)$ 是否存在烟雾。 ### 解题思路…

在文章《题解：P11754 [COCI 2024/2025 #5] 绘图 / Crtež》发表评论：

太强了%%%

## [CF749E Inversions After Shuffle](https://www.luogu.com.cn/problem/CF749E) ### 题目大意 给定一个排列，随机打乱其中一部分，求期望的逆序对个数。 ### 解题思路 考虑对于一个数对 $(a_i,a_j),i a_j$，则**减少的逆序对…

## [P11753 [COCI 2024/2025 #5] 绘图 / Crtež 题解](https://www.luogu.com.cn/problem/P11753) ### 题目大意 给定一个长度为 $n$ 的序列，初始全为 $0$。每次给定区间 $[l,r]$，将区间内的 $0$ 和 $-1$ 互相翻转。每次…

## [\[ABC391G\] Many LCS](https://www.luogu.com.cn/problem/AT_abc391_g) ### 题目大意 有一个长度为 $N$ 的小写英文字符串 $S$。需要统计对于所有可能的长度为 $M$ 的小写英文字符串 $T$，它们与 $S$ 的最长公共子序列长度为 $0,…