TH911 Blog

差分约束

例题链接差分约束给定包含 $n$ 个未知数 $x_1,x_2,\cdots,x_n$ 的不等式组： \[\begin{cases} x_{a_1}-x_{b_1}\leq y_1\\ x_{a_2}-x_{b_2}\leq y_2\\ \cdots\\ x_{a_m}-x_{b_m}\leq y_m \end{cases}\] 求其任意整数解，或报告无解。最短路考...

Posted by TH911 on November 25, 2025

Bellman-Ford、SPFA 判断负环

Bellman-Ford 负环 Bellman-Ford 会对边进行松弛操作，若不存在负环，则至多松弛 $n-1$ 轮即可求出最短路，进而确定无负环。注意需要特判 inf，因为负权。注意需要 dis[s]=0。 vector 实现代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...

Posted by TH911 on November 25, 2025

浅谈随机化算法

爬山算法与模拟退火

随机函数应该很简单，介绍三个最常用的。 rand()，会返回一个在 $[0,r]$ 内的随机整数。$r$ 为 RAND_MAX，标准库中的宏，在 Windows 下取 $2^{15}-1$，在 Linux 下取 $2^{31}-1$。rand() 效率较低。可使用 srand(seed) 做种。配合 time(0)。 mt19937，可用...

Posted by TH911 on November 20, 2025

CSP 2025 游记

CSP-J 2025 没什么好说的。早上出门的时候车还被别人拦住了，出不去。于是换了一辆车走了。 T1 找出数字后排序，sort 秒了。赛时代码 ```cpp //#include<bits/stdc++.h> #include #include #include #include #include #include #include #include #in...

Posted by TH911 on November 8, 2025

莫队算法学习笔记

其实莫涛据说是 xqz 的学生，可以算是我的学长。以下记 $n$ 为序列 $a_1,a_2,\cdots,a_n$ 的长度，$q$ 为询问次数（与修改次数之和）。对序列以 $B$ 为块长分块，记 $\operatorname{pos}(i),\operatorname{edgeL}(i),\operatorname{edgeR}(i)$ 分别为 $a_i$ 的块编号（即 $\...

Posted by TH911 on November 8, 2025

思维题练习

思维题题解合集

本文选取题目源于此处。 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