TH911 Blog

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

题解：[国家集训队] 最长双回文串

洛谷P4555

题目传送门 如果你还不会Manacher：看这里 题意分析 首先，我们发现题目要求最长回文串，自然而然地想到 Manacher。 但是当我们求出最长回文半径 $p_i$ 后，却发现不知道如何进一步做题了。 如果枚举两个回文串分别的回文中心，那么就是一个 $\mathcal O\left(n^2\right)$ 的算法，考虑到 $2\leq \vert S \vert \...

Posted by TH911 on November 14, 2024

题解：[USACO12DEC] First! G

洛谷P3065

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

Posted by TH911 on November 14, 2024

题解：字典树

洛谷P8306

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

Posted by TH911 on November 14, 2024

题解：用于试题标题的中文名称

题目见正文

时间限制 空间限制 输入文件名 输出文件名 $1000ms$ $512MB$ title.in title.out 题目 题目描述 给定长度为 $n...

Posted by TH911 on November 13, 2024

题解：好题

题目见正文

题目 时间限制 空间限制 输入文件名 输出文件名 $3000ms$ $512MB$ good.in good.out 题目描述 给定两个长度为 $n...

Posted by TH911 on November 13, 2024

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

洛谷P1041

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

Posted by TH911 on November 10, 2024

题解：卡戎

题目见正文|原题:正睿 noip 十连测 Day4T1

数据包 题目 输入文件名 输出文件名 时间限制 空间限制 charon.in charon.out $1s$ $512MB$ 题目描述 您...

Posted by TH911 on November 10, 2024

XPlayer使用指南

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

Posted by TH911 on November 9, 2024

题解：[CSP-S 2019]划分

洛谷P5665

题目传送门 题意分析 AC代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 ...

Posted by TH911 on November 9, 2024

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

洛谷P1967

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

Posted by TH911 on November 8, 2024

FEATURED TAGS
普及+/提高 题解 提高+/省选− 搜索 数学 普及/提高− 未完 贪心 二维数点 倍增算法 前缀和 字典树 扫描线 状态压缩 队列 LCA Manacher RMQ ST表 XPlayer
ABOUT ME

要做一个优秀的 OIER

FRIENDS