TH911 Blog

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

题解:[USACO12DEC] First! G

洛谷P3065

题目传送门 如果你还不会 Trie树:看这里 题意分析 策略 看到字典序,很容易想到考虑使用 Trie 树解决。 假设 $s$ 为更改字典序后可能的最小值,那么相当于钦定了 $s_i$ 小于其兄弟节点。(如图) 假设 $s=\texttt{acd}$,那么就钦定了 $c<a,c<b$,否则最小值不可能为 $\texttt{acd}$。 至此,思路就比...

Trie 树详解

洛谷P8306 | Trie树

题目传送门 字典树(Trie树) 字典树其实就是一种空间换时间的策略。 比如我们使用 $\texttt{aa,ab,ac,abc,acd,aac}$ 来构造一棵字典树,则如下图: 简单而言,就是将每一位字符都视作连接节点的两条边,那么便形成了如上的树。 这么做有什么好处呢? 节约时间。 这样查询前缀,仅仅需要在字典树上找到 $t$ 的最后一个字符,然后统计字数权值和...

题解:[NOIP2003 提高组] 传染病控制

洛谷P1041

题目传送门 强化版数据包 本题是错题,后来被证明没有靠谱的多项式复杂度的做法。测试数据非常的水,各种玄学做法都可以通过,不代表算法正确。因此本题题目和数据仅供参考。 题意分析 首先,$p=n-1$。输入时直接 scanf("%d %*d",&n); 即可。 将可能的传播途径视作一棵以节点 $1$ 为根节点的树,那么我们优先救子树最大的节点及其...

XPlayer使用指南

项目地址 演示地址 此文档已弃用,请参考 README.md。 简介 一个静态音乐播放器。 作为一个从来没学过html/css/js的人,我想能写成这样已经很好了。 使用方法 访问项目地址即可,在 /XPlayer 后可以加上 /#1,表示播放第一首歌曲,同样有 /#2、/#3、/#4 等,但注意如果超出了歌曲总数,或是小于 $1$,那么会随机跳歌。 如:/#0。 随机跳歌 ...

题解:[NOIP2013 提高组] 货车运输

洛谷P1967

题目传送门 题意分析 为了使两座城市间的道路限重的最小值尽可能大,那么我们建立一棵最大生成树即可。 然后对于每次询问 $x,y$,输出 $x\sim \operatorname{lca}(x,y),\operatorname{lca}(x,y)\sim y$ 的限重最小值即可。 问题就在于如何存储最小值。 事实上,这个问题很简单:只需要在倍增LCA时存储 $x$ 至 $x$...

题解:[省选联考 2024] 季风

洛谷P10217

题目传送门 题目分析 首先,明显 $0\sim n-1,0\sim m-1$ 不好,因此我们统一使用以 $1$ 开始的下标。 其次,对于“$\large x_{i\bmod n}$”,那么我们为了便于分析(但事实上在后文就会发现只会用到 $x_1\sim x_n$),直接让其无限循环,即:令 $\large \forall x_i=x_{i\bmod n}$。对 $\large...

Manacher算法详解

马拉车算法 | 例题:洛谷P3805

Manacher算法,又名“马拉车”算法。 引入 给出一个只由小写英文字符 $\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$ 组成的字符串 $s$ ,求 $s$ 中最长回文串的长度 。 对于这种问题,一眼便有两种朴素算法。 枚举最长回文串的左右边界 $l,r$,然后 $\mathcal O(r-...

离线扫描线二维数点

例题:洛谷P10814

什么是二维数点 顾名思义,在一个二维平面内求一个矩形内有多少个点(“点”并非指普通几何点,否则有无数个),如图。 我们可以一眼看出: $\color{red}\colorbox{red}{1}$ 矩形内有 $1$ 个点; $\color{#FF8000}\colorbox{#FF8000}{1}$ 矩形内有 $1$ 个点; $\color{#3F48CC}\color...

关于ChatGPT 4o mini

原来,2023年10月22日至2024年10月22日仅有1024天

也就不说什么了,看图吧: 咱就说原来 $2023$ ~ $2024$ 有 $1024$ 天……

ST表

例题:洛谷P3865

定义 ST 表(Sparse Table,稀疏表)是用于解决 可重复贡献问题 的数据结构。——OI Wiki 可重复贡献问题是什么我也不知道 作用 求静态区间最大(小)值,即一个区间不会修改。 能够实现 $\mathcal O(n\log_2 n)$ 预处理,$O(1)$ 查询。 实现 倍增思想 设 $\large f_{x,i}$ 表示区间 $[x,x+2^i-1]...