chx2026-08-06
NOIP2025T3树的价值
是在参加南京大学办的计算理论之美活动期间和舍友随机跳题跳到的, 结果这一段时间一直在想到现在才想清楚. 简述题意 题意 给定一个有 $n(\le 8000)$ 个节点, 树高不超过 $m(\le 800)$ 的有根树 $T$ , 树根是 …
标签浏览
题解
这里包含当前标签及其所有子标签下的文章。
2026-07-31
一种处理异或运算下不等式的技巧-逐位比较
真的恶心，妈的放道D1恶心人，D1跟D2正解毛关系都没有，傻逼比赛 题号 CF1720D2 Xor-Subsequence (hard version) 简单转化一下题意就是求这样的一个 dp 数组： …
2026-07-31
CF605E. Intergalaxy Trips 与对期望的一些理解
简化题面 给一张无向图，在每一时刻，每一条边权值都为 $1$ ,出现的概率都是给定的（但不完全相同），问最优决策下 $1$ 到 $n$ 的期望。 Attention： 是每条边都会有概率出现，而不是走每条边都会有概率成功，这就意味着，我 …
2026-07-31
CF2234G. Stripe, Token and Two Players
记录一个很有意思的观察。朴素的博弈 DP 状态是 $$DP[i,j]:=位置在\ i\ 并且能力为\ j\ 的前提下先手是否必胜\def\la#1{\langle #1\rangle}$$ 然后转移就是 $$\begin{align*} …
2026-07-31
CF2232E. Snaking Arrangement
记录一种新颖的排列构造方法。 我们先看一个相对而言更弱的问题，如果初始的时候整个网格是空的，那么有多少摆放方法呢？这个题我们首先需要从蛇的长度限制上获得一个非平凡的观察：摆放的方法远比我们预期的要少 我们作如下的实验：摆蛇先摆长的，之后 …
2026-07-31
CF2055E. Haystacks
神奇的贪心题目——对于贪心的总结 记录一下自己的狗屎思路： 考虑固定了遍历顺序的前提下，怎么操作是最优的？ 对于每个栈，把栈的元素尽量放入到已经清空过的栈内，放不完的全部丢到最后一个栈里 考虑怎么模拟这个过程： 维护已经清空的栈的空间 …
2026-07-31
CF1684F. Diverse Segments
一个和官方题解不大一样的做法，常数略微大一点点，故作文记之。 首先第一点，每一个区间都有可能产生若干个冲突对，然后显然我选择的区间一定要覆盖这些冲突。但是不一定要全部覆盖，其实留出每组冲突对的最左边或者最右边都可以。以及可以感性理解一 …
2026-07-31
CF1172C2. Nauuo and Pictures (hard version) 与对条件期望的一些理解
前言 再次看到这一题是在某带砖的思政课上。回忆中，第一次看到这题的时，我尚懵懂，并不会做。如今，将这题推给我的人已功成名就，而我却一无所有，不禁黯然神伤，感慨时移世异以至沧海桑田。兴许能把以前自己不会的题做出来，已然是莫大的安慰，故作文 …
2026-07-31
2024年ICPC区域赛南京站I题题解
看！一道计数题！我们有救了！ 设 $f[x=i]$ 表示值恰好为 $i$ 的方案数，那么答案就是求 $$ans=\sum_{i\ge 0} f[x=i]\cdot i$$ 考虑进行阿贝尔变换，得到： $$\begin{aligned} …
2026-07-31
2024年ICPC区域赛昆明站B题题解
前言 成功摄金！世界上没有什么更加美妙的事了 这题在赛时没有做出来，但是感觉实际上是很好处理的，索性就赛后做一下，发现确实不太难 写题解的另外一个原因是代码估计很难写，所以先贷款 另外，很喜欢这种一层一层把思路剥开的题目， 思路 考虑一 …
2026-07-31
2024年ICPC区域赛杭州站J题题解
前言 赛时没有做出来，然后赛后被队友嘲讽说是简单题，还搞了一堆奇奇怪怪的容斥加减…… 我认为都是假的，毕竟计数的难点并不在于设计怎样的状态，而在于怎么不算重，我在赛时已经想过很多容斥了，要么会算重，要么就是无 …
2026-07-31
【luogu题解】P3269 [JLOI2016]字符串覆盖 单调队列做法
简单概况一下题意 给定一个母串S与其子串T ，要将T放入母串中 ，在允许相互覆盖或者相交的情况下 ，问这些子串在母串中覆盖的字符 最多/少 是多少 分析 看见最值很容易就往dp上想，但是这题直接dp会有后效性，就是每个串放的位置没有顺序 …
2026-07-31
【luogu题解】CF1387A 图上解方程
一个蒟蒻来水本题第一篇题解 分析 首先不难发现一条边$(u,v,w)$表示的是一个方程 $x_u+x_v=w$ ，那么问题就转换为了方程组是否有解，求出绝对值最小解的问题 实现 首先图是不一定联通的，但因为每个连通块是独立的，所以可以分 …
2026-07-31
【luogu题解】[HNOI2009]双递增序列 想不到序列对调的题解
这题的做法其实和以前大佬的很像，但是第二个那个交换序列的转移我太弱了真的想不到，所以在此提出新的转移方式 状态定义：$f[len][i]$ 表示处理到第 $i$ 个数 $a[i]$ ，将其放入 $U$ 集合中，则此时 $V$ 集合内最后 …