### Day 1 进场，T1 考期望？T2 字符串，T3 神秘题。 T1 首先可以设 $f_{x,i}$ 表示考虑 $x$ 的子树，$x$ 所在重链长度为 $i$ 的期望，然后就可以直接 $O(n^2)$ 算答案了？非常兴奋以为自己秒了 T1，然后才发现自己根本不会转移 $f$。 前后缀卷合并？显然可以卡到 $O(n…

本文写于 2026.2.9。 ### Day -998244353 前面忘了。 ### Day -387 报道日，是三个人的四省联合寝室。 开幕式表演了我会喷火。 看神秘小说的第 391 章。 ### Day -386 讲课只有第一题能听懂，后面如听。 ### Day -384 1h 切 T1，这 T2 是啥？不管了开…

注意不要将负数赋值给unsigned int

在文章《题解：P14586 [LNCPC 2025] 前后缀石子博弈》发表评论：

orz orz orz

在文章《CSP-S 2025 游记》发表评论：

orz orz orz

### Day1 考前观察了 J 组题目，**polygon**？这文件名怎么这么有趣。(伏笔1) 进考场，由于我一般建文件夹的习惯是复制大样例，但**贴心**的主办方提前建好了主文件夹。于是灵光一现，决定手打文件夹名。(伏笔2) A 题这不是 [AT_agc018_c](https://www.luogu.com.c…

在文章《题解：P9168 [省选联考 2023] 人员调度》发表评论：

%%%

## CF1842 ### F 考虑钦定根节点为黑点重心，这样选每个点为黑点对答案造成的贡献是独立的。 如果计算答案时当前点不是黑点重心，那么会使答案更小，不会产生影响。 于是可以枚举黑点重心，$O(n^2 \log n)$ 解决本问题，瓶颈在于排序。 ### G 非常神秘，考虑乘法分配率的每条路径，每次从 $a_i$…

## CF1848 ### C 考虑对于每组 $(a_i,b_i)$ 分类讨论，不妨设 $a_i \ge b_i$。 * 若 $a_i \ge 2 \times b_i$，可以变为 $(a_i - 2k \times b_i,b_i)$。 * 若 $a_i < b_i$，变为 $(b_i,b_i-a_i)$。 每次至少…

### C 性质 不妨将概率计数转为方案计数，最后再乘上 $2^{-2m}$。 所有边权相等，条件可以转化为存在一棵外向生成树，考虑所有可以成为根的节点，可以发现其组成一个 SCC，更具体的，其恰好是缩点后唯一入度为 $0$ 的 SCC。 因此我们设 $dp_S$ 表示集合 $S$ 恰好是缩点后唯一入度为 $0$ 的…

# CF1918 ## D #### Solution 最大值最小，首先显然有二分答案。 观察阻断了一个点，能取到的上一个阻断的点显然是一个区间，进一步发现，其形如一个滑动窗口。 定义 $f_i$ 为阻断了第 $i$ 个点，前 $i$ 个点被阻断权值和最小值。 $$f_i = \min_{j #define int l…

# CF1935 ## E #### Solution 首先考虑每一对 $(x_i,y_i)$，将其二进制分解。 其中 $x_i$ 和 $y_i$ 的公共前缀一定会对答案产生贡献，这部分可以用 st 表维护区间 or，计为 $d$。 对于剩下的部分，考虑 $y_i$ 的第 $j$ 位为 $1$，由于 or 的性质，我们…

# CF1943 ## D #### Solution 考虑一个什么样的序列合法，通过观察得到结论： 定义第 $i$ 位合法为 $b_i \le b_{i-1}+b_{i+1}$，一个序列合法，当且仅当其所有位合法。 必要性是显然的，$b_i$ 最多会被减 $b_{i-1}+b_{i+1}$，然后 $b_{i-1}$，…

# CF1942 ## E #### Solution 首先假定第一头牛是先手的，最后再将答案乘 $2$ 就行。 将相邻的两头牛配对，我们有如下结论： 先手必胜当且仅当存在一对牛之间空格为奇数。 考虑证明，由于可以移动任意的牛，先手可以将所有空格为奇数的一对牛移动为偶数，后手由于所有牛空格为偶数，移动后必然在一对牛之间…

# CF1957 ## D #### Description 给定序列 $a_n$，求满足以下条件的三元组 $(x,y,z)$ 的数量： * $1\le x\le y\le z\le n$. * $f(x,y)\oplus f(y,z)>f(x,z)$. 其中 $f(l,r)$ 表示 $a_l\oplus a_{l+1…

### Description 定义一个子段是独特子段，当且仅当存在一个整数在这个子段中出现恰好一次。 给定序列 $a$，求至少替换多少个元素，才能使得 $a$ 的所有子段为独特子段。 ### Solution 考虑扫描线，定义一个二维平面，横轴代表左端点，纵轴代表右端点，点 $(l,r)$ 代表子段 $[l,r]$。…

### Description 有 $n$ 个商品，Alice 以 $a_i$ 的价格选择若干个物品进货，然后卖给 Bob。Bob 可以选择其中的 $k$ 个免费拿走，剩下的付款 $b_i$ 元。 Alice 希望自己的利润最大化，而 Bob 希望 Alice 的利润最小化，求 Alice 能获得的最大利润。 ###…

# CF1969 ## D #### Description 有 $n$ 个商品，Alice 以 $a_i$ 的价格选择若干个物品进货，然后卖给 Bob。Bob 可以选择其中的 $k$ 个免费拿走，剩下的付款 $b_i$ 元。 Alice 希望自己的利润最大化，而 Bob 希望 Alice 的利润最小化，求 Alice…

考虑使用 0-1trie 解决，可以将其视作一棵动态开点权值线段树，每个线段树结点向左子树连权值为 $0$ 的边，向右子树连权值为 $1$ 的边。 对 and，or，xor 操作进行分析，单独考虑一个叶子节点在操作后会放在什么位置，发现其相当于将一些父亲的左儿子改为右儿子，右儿子改为左儿子。这会改变树的形态，难以在区间…

## 例题 ### P4145 区间开根。 观察到一个数可以开根的次数为 $O( \log \log n)$，我们定义势能为所有数可以开根的次数，每次线段树递归开根都将减少 $1$ 的势能，因此每次只需要将需要开根的数开根，时间复杂度 $O(n \log n)$。 ### UOJ228 区间开根，区间加。 原本的势能分…

## Solution 看了其他人的做法，感觉维护相邻差分的 $\gcd$ 还是有点难想到的，于是就有了这篇暴力随机化做法。 对于一个长度为 $n$ 的序列 $a$，设其最小值为 $a_1$，最大值为 $a_n$，如果它排序后能构成公差为 $d$ 的等差数列，要满足以下几点： 1. $a_n-a_1 = d \cdot…

### 6.25~7.11 模拟赛被各种吊打，只切掉了严格小于一道题。 选手丢失房卡，会扣多少钱？**- 50** ### 7.12 报道，坐大巴车前往奶龙山书院，和若干个人交换了徽章。 奶龙山的住宿和食堂一如既往的优秀。 ### 7.13 上午开幕式。 省流：我说不一定 我认识鲁迅比较早了 【数据删除】制度好 这小品…

如果你只 WA 1个点，请注意斜率优化时不同点的横坐标可能相同。

# 群论 ## 群 #### 群的定义 若集合 $S\ne\varnothing$ 和集合 $S$ 上的运算 $\cdot$ 构成的代数结构 $(S,\cdot)$ 满足以下性质: 1.封闭性：$\forall a,b \in S,a \cdot b \in S$ 。 2.结合律：$\forall a,b,c \in…

在讨论《来给 NOIP 四个题评难度吧》回复：

绿蓝紫紫

在讨论《20 分 求调》回复：

qp

在讨论《75PTS 求助awa（码风也许优良，可艾萌新悬关)》回复：

@[willow_Catkin](/user/457623) 32行上界为m+up[i]

在讨论《关于 CSP-S T3》回复：

模拟赛骗了100分，考古