「Diary & Solution Set」February 2026 愿我们在真理前相会

2026.2.1

议论文没素材了不应该成为不做题的借口/lh

征途之所以伟大，史诗之所以壮阔，皆因万物终有逝去之时。

它是我们会在临别时含泪的理由，也是最初点燃凡人热情的薪火。

但无论我们如何被他人、被世界塑造，自诞生起，我们的存在就已注定，任何事物都无法将其抹消。

2.2

怎么寒假集训才开始就一堆 3000+ 的 Problems 😡。机房这个氛围感觉我整个寒假要在 whk 中度过了（雾）。

ABC214G Three Permutations

小清新 AT 风味 CN 套路排列计数。

首先考虑容斥，通过 dp 钦定一部分值必须选 \(p_i\) 或 \(q_i\)，剩下的随便选。不过因为是排列，这个互不相同的限制并不好刻画——但是只给了两个排列做限制，这意味着一个数最多可能会被两个位置选到。很自然的思路是将这两个位置连边，形成若干个环，转化为环上边独立集方案数。每个环内部是独立的，可以通过 dp 算出来方案数，最后做一个背包统计答案，复杂度是 \(O(n^2)\) 。

AGC017F Zigzag

这题 edu 的地方在于状态设计上应当打破惯性思维，关注对转移真正有用的信息。

2.3

题目正常了，但是我的精神状态疑似不正常了。

[JOIST 2025] 勇者比太郎 3

感觉第一步就超级困难，还好基本功并没有一如既往地崩塌，使得后面的步骤做起来还比较顺。

这个拆贡献感觉如果被 informed 之后还是容易理解的，但是我感觉还没有很本质地理解到这个东西。

[JSOI2009] 面试的考验

虽然说感觉我的 CNOI 套路 ds 基础还不错，但是支配对一直不是很会。这个题今天才写。

考虑对于一个 \(i\) 来说，\(j>i\land a_j>a_i\) 中真正有效的 \(j\)。首先最小的 \(j\) 一定有效，不会被其它这样的点对支配。考虑再右边的一个 \(k\)，由于 \((i,k)\) 是 \((i,j)\) 与 \((j,k)\) 的超集，所以在区间上已经被这两个点对支配，值域上不能被支配，所以有限制 \(a_k-a_i<\frac{a_i+a_j}{2}\)。发现每次找下去可行值域减半，\(a_j<a_i\) 同理，所以一共有 \(O(n\log V)\) 对有效点对，拉出来跑二维偏序即可做到 \(O(n\log n\log V)\)。

2.4

模拟赛，但是大机房+瞌睡+两个一眼题 debuff 叠满/shui，懒得写代码。最后写了个暴力，发现居然是并列倒一而非倒一。

T1 是根号分治反射容斥，T2 是遥远的国度那种换根题，但是信息很复杂，场上胡了 3 个做法（拆贡献树剖线段树，SATT，时间轴分块），都懒得写，嘟嘟嘟。T3 是神秘计数 dp，不是很会，赛后点了一下贡献延迟计算会了，不过头还是很晕。

下午体锻时间被同学拉去打球，但是上一次打乒乓还是在小学，突然想起来初中三年都没打过球，这也太失败了。

感觉中学生活也太失败了。初中的时候想不到那么多，现在焦虑未来眼光已经放到很久之后了。

告诉我，我们的 golden days 为何一去不复返了？

2.5

模拟赛。T1 简单题，但是花了 1min 思考一个东西如何优化，突然想起来这东西不是整除分块吗。T2 一眼凸优化（模拟赛怎么这么喜欢凸优化），但是感觉 T3 可做写了个暴力贪心就走了。T3 按 \(\frac{L}{2}\) 分开之后扩展 Hall 定理（模拟赛怎么这么喜欢 Hall 定理），胡了个根号分治，不过根号下有个 log，但是最后 \(n=10^5\) 多测 \(T=10\) 大样例 0.5s，很诡异。赛后发现有个细节没处理到位所以挂分了。

明天要去 NOIWC2026 了，希望不要重蹈去年的覆辙。