TH911 Blog

思维题练习

思维题题解合集

本文选取题目源于此处。 CF2071C Trapmigiano Reggiano 以终点 $t$ 为树的根节点。那么求排列等价于求一种移动顺序，使得老鼠最后停留在根节点。移动可以分两种：向上和向下。显然向上是更优的。设老鼠当前位于节点 $p$，如果在 $x$ 处生成一个奶酪：若 $x$ 是 $p$ 的祖先节点，则这是优的。若 $x$ 是 $p$ 的子...

Posted by TH911 on September 27, 2025

忆

原文扫描件忆我常常追忆过去1。过往在我眼前定格，我行走于记忆的回廊。或清晰，或模糊，或光鲜，或灰暗；往事纷纷而至，可是，我似乎是孤独的。我时常回忆起零碎的往事。坐在车上，想起儿时和爷爷坐火车回老家，本是到「天门南」站，但估计是印刷问题，车票上的「南」不是很清晰，爷爷被吓坏了，还以为是车票买错了站。还是我发现了这一情况，告诉了爷爷，事情才告一段落。然而，我的爷爷现在...

Posted by TH911 on September 26, 2025

一些有趣的事情

记录。 OI 生活只过 hack 数据参见此处。 qzmoot（QGY）：说明有可能你的强制在线写出了问题，因为hack数据一般只有一个询问，并且在最后。然而我的李超线段树写的强制在线是： 1 2 3 4 a.x=(a.x+lastans-1)%X+1; a.y=(a.y+lastans-1)%X+1; b.x=(b.x+lastans-1)%Y+1; b....

Posted by TH911 on September 26, 2025

一类特征方程在数列递推中的应用

特征方程

以下内容摘自《组合数学》（第五版）P86【例 2-41】。求 $S_n=1^3+2^3+\cdots+n^3$。 $\Delta S_n=S_{n+1}-S_n=(n+1)^3$ 是 $n$ 的 $3$ 次多项式，因此 $S_n$ 满足递推关系： \[S_n-5S_{n-1}+10S_{n-2}-10S_{n-3}+5S_{n-4}-S_{n-6}=0\...

Posted by TH911 on September 21, 2025

LCT详解

Link Cut Tree | 动态树问题

例题链接。给定 $n$ 个点以及每个点的权值，要你处理接下来的 $m$ 个操作。询问 $x\sim y$ 路径上的点权的 $\operatorname{xor}$ 和。保证 $x$ 到 $y$ 是联通的。连边 $(x,y)$，若 $x$ 到 $y$ 已经联通则无需连接。删边 $(x,y)$，不保证边 $(x,y)$ 存在。将点 $...

Posted by TH911 on August 25, 2025

Splay 之区间操作

Splay 维护区间操作

例题链接。您需要写一种数据结构（可参考题目标题），来维护一个有序数列。其中需要提供以下操作：翻转一个区间，例如原有有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。前置知识：Splay 参见Splay 树详解。平衡树维护区间信息无论是 Splay 还是 FHQ Treap，亦或是其他...

Posted by TH911 on August 25, 2025

题解：Perishable Roads

CF773D

题目传送门题意分析考虑最终的生成树，一定包含了权值最小边。设该边为 $(u,v)$，若生成树中不包含 $u,v$，则一定有两条边分别到达 $u,v$。显然这两条边有一条换为 $(u,v)$ 更优。那么生成树一定形如从 $t$ 到达最小边，之后便是从最小边出来的一些子树（实际上也可以是链，都是等价的）。为了到达最小边，成为一条链是最优的，否则会有不必要的花费。确定最...

Posted by TH911 on August 22, 2025

题解：[PA 2020] Malowanie płotu

洛谷P9108 | 前缀和优化 DP

题目传送门绝世前缀和优化 DP 好题。题意分析即找出长度为 $n$ 的序列 $\langle[l_1,r_1],[l_2,r_2],\cdots,[l_n,r_n]\rangle$ 的个数，且满足： $l_i,r_i$ 为整数，且 $1\leq l_i\leq r_i\leq m$。对于 $1\leq i<n$，有 $[l_i,r_i],[l_{i...

Posted by TH911 on August 22, 2025

题解：Towering Arrays

CF2071F

题目传送门 VP 场切。题意分析二分答案显然，条件 $b_j\geq p-\vert i-j\vert$ 成立的 $p$ 具有单调性。即若 $p=p_0$ 时该条件成立，则 $p<p_0$ 时也成立。因此可以二分答案 $p$，取最大值即可。线段树维护 $p$ 已经确定，那么便是判断条件。显然绝对值并不好处理，考虑拆开。即需要满足条件： \[\b...

Posted by TH911 on August 20, 2025

题解：Trapmigiano Reggiano

CF2071C

题目传送门题意分析记起点为 $s$，终点为 $t$。原树没有根，考虑人为设定一个根。不妨以 $t$ 为根节点。那么求排列等价于求一种移动顺序，使得老鼠最后停留在根节点。移动可以分两种：向上和向下。显然向上是更优的。设老鼠当前位于节点 $p$，如果在 $x$ 处生成一个奶酪：若 $x$ 是 $p$ 的祖先节点，则这是优的。若 $x$ 是 $p$ ...