TH911 Blog

「光阴不可测,岁月亦无歌。」

思维题练习

思维题题解合集

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

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

一些有趣的事情

记录。 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....

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

特征方程

以下内容摘自《组合数学》(第五版)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\...

LCT详解

Link Cut Tree | 动态树问题

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

Splay 之区间操作

Splay 维护区间操作

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

题解:Perishable Roads

CF773D

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

题解:[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...

题解:Towering Arrays

CF2071F

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

题解:Trapmigiano Reggiano

CF2071C

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