TH911 Blog

题解：[USACO12DEC] First! G

洛谷P3065

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

Posted by TH911 on November 14, 2024

Trie 树详解

洛谷P8306 | Trie树

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

Posted by TH911 on November 14, 2024

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

洛谷P1041

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

Posted by TH911 on November 10, 2024

XPlayer使用指南

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

Posted by TH911 on November 9, 2024

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

洛谷P1967

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

Posted by TH911 on November 8, 2024

题解：[省选联考 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...

Posted by TH911 on October 25, 2024

Manacher算法详解

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

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

Posted by TH911 on October 25, 2024

离线扫描线二维数点

例题：洛谷P10814

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

Posted by TH911 on October 23, 2024

关于ChatGPT 4o mini

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

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

Posted by TH911 on October 22, 2024

ST表

例题：洛谷P3865

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

Posted by TH911 on October 20, 2024