TH911 Blog

Binary GCD

二进制 GCD

https://www.cnblogs.com/cmy-blog/p/binary-gcd.html) Binary GCD Luogu P5435 基于值域预处理的快速 GCD 给定 $a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_n$，对于 $i\in[1,n]$，求 $\displaystyle A_i=\sum_{j=1}^{n}...

Posted by TH911 on March 21, 2026

题解：【MYCOI R1】好想大声说爱你

洛谷P1553

题目传送门在场上被骗了，最后才写出来，遂有此题解。题意分析记原题面中 $L,M$ 分别为 $l,m$。如果无解则输出 Che_is_Loser。然而你发现似乎怎样都有解，实际上也是如此……也许只有我在这里停了。但是在 IOI 赛制下，其实你可以直接交一发就可以知道没有无解了。我们的目标是让 $a_1,a_2,\cdots,a_n$ 都增长到 $...

Posted by TH911 on February 28, 2026

提问的智慧

Posted by TH911 on February 28, 2026

高维偏序

树套树三维偏序/高维偏序

不知道从哪里下的 PDF，感觉写的很好。处理偏序问题时，如果偏序条件都带等号，则需要考虑两个元素完全相同的情况，这时需要该元素 $a$ 的统计个数 $\textit{cnt}$，然后统计满足偏序条件元素个数 $x$，则 $a$ 的答案为 $x-1$，同时直接做 $\textit{cnt}$ 的贡献。一维偏序排序即可。二维偏序排序之后树状数组统计即可。比如逆序对...

Posted by TH911 on February 18, 2026

Link Cut Tree

LCT 动态树问题

Luogu P3690 动态树（LCT）给定 $n$ 个点、每个点的权值和 $m$ 次操作： 0 x y 代表询问从 $x$ 到 $y$ 的路径上的点的权值的 $\operatorname{xor}$ 和。保证 $x$ 到 $y$ 是联通的。 1 x y 代表连接 $x$ 到 $y$，若 $x$ 到 $y$ 已经联通则无需连接。 2 x y 代表...

Posted by TH911 on February 17, 2026

题解：[POI 2001] 和平委员会

洛谷 P5782

题目传送门题意分析显然可以跑 2-SAT。记 $f(x)$ 为 $x$ 的同一党派的代表。那么，若 $i,j$ 彼此厌恶，建边 $i\rightarrow f(j),j\rightarrow f(i)$ 即可。因为 $i$ 存在，则 $j$ 不存在，$f(j)$ 存在。$j\rightarrow f(i)$ 同理。答案即在 $2i-1,2i$ 里选择拓扑序较大...

Posted by TH911 on February 15, 2026

2-SAT

例题：洛谷 P4782

SAT 给定 $n$ 个布尔变量 $x_1,x_2,\cdots,x_n$，和 $m$ 组关系，每组关系给定 $i_1,i_2,\cdots,i_k,a_1,a_2,\cdots,a_k$，表明： \[[x_{i_1}=a_1]\lor[x_{i_2}=a_2]\lor[x_{i_3}=a_3]\lor\cdots\lor[x_{i_k}]=1\] 求任意一组解。 SAT...

Posted by TH911 on February 14, 2026

题解：[JXOI2017] 加法

洛谷 P4064

题目传送门题意分析注意到「最小值尽可能的大」。一般对于这种最值的最值的问题，都可以套一层二分答案。——xxy 考虑二分答案。二分答案的原因一直没想明白，直到我在模拟赛上打了 $\text{1.5h}$ 建了 $3$ 棵线段树维护的贪心假了后，终于想起来二分答案。最值具有单调性，最值的...

Posted by TH911 on February 10, 2026

题解：[JOISC 2015] 有趣的家庭菜园 2 / Growing Vegetables is Fun 2

洛谷 P14407

题目传送门题意分析记原题面中 $n,H_i,P_i,C_i$ 分别为 $n,h_i,p_i,c_i$。考虑 DP 求解最大收益，不难发现最终有效的 $h_i$ 一定是先上升在下降的。对于这种「单峰」的东西，DP 可以考虑做两次：上升和下降，即从前往后 $h_i$ 不降和从前往后 $h_i$ 不增。以 $h_i$ 不降为例，设 $\textit{dp}_{i,j}$...

Posted by TH911 on February 10, 2026

题解：To the moon

HDU4348

题目传送门题意分析显然是维护一棵可持久化线段树。 $1\leq n,m\leq 10^5$，很容易写完。但是发现空间限制 $\text{64MB}$，需要卡空间。先丢掉线段树中存储的节点边界，放入递归中传参。然后考虑继续卡，将可持久化线段树的懒标记改为标记永久化，这样可以避免每次 down 都要新建两个节点。（当然你写回收也可以，不过不好写。） AC 代码 1 ...

Posted by TH911 on February 10, 2026

TH911 Blog

Binary GCD

二进制 GCD

题解：【MYCOI R1】好想大声说爱你

洛谷P1553

提问的智慧

提问的智慧

高维偏序

树套树三维偏序/高维偏序

Link Cut Tree

LCT 动态树问题

题解：[POI 2001] 和平委员会

洛谷 P5782

2-SAT

例题：洛谷 P4782

题解：[JXOI2017] 加法

洛谷 P4064

题解：[JOISC 2015] 有趣的家庭菜园 2 / Growing Vegetables is Fun 2

洛谷 P14407

题解：To the moon

HDU4348

FEATURED TAGS

ABOUT ME

FRIENDS