TH911 Blog

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

题解：[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

树上最近公共祖先（LCA）问题

例题：洛谷P3379

参考链接：OI Wiki 倍增LCA 倍增思想 可以参考ST表。 设 $\large f_{x,i}$ 表示 $x$ 的 $2^i$ 级祖先，用 $father_i$ 表示节点 $i$ 的父节点 ，则显然： \[\large f_{x,0}=father_x\] 例如对于这棵树： $\large f_{9,0}=\normalsize father_...

Posted by TH911 on October 20, 2024

关于MathJax

比较MathJax与KaTeX

首先说一下使用感受吧： MathJax：一堆奇奇怪怪的错误，渲染慢的同时一堆错。 $\KaTeX$：渲染比较快，也比较轻量，但是仍然渲染会有问题。比如这里。 怎么说呢，单从配置难度来讲，$\KaTeX$ 完虐 MathJax。 从实用来讲，$\KaTeX$ 足以支持 $\LaTeX$ 语法，也不需要MathJax。 总而言之，MathJax直接替换为 $\KaTeX$ 就...

Posted by TH911 on October 20, 2024

FEATURED TAGS
树状数组 题解 省选/NOI− 提高+/省选− DP 基础算法 普及+/提高 数学 线段树 贪心 普及/提高− 组合数学 字符串 未完 二分 图论 平衡树 数论 树形 DP Tarjan 位运算 搜索 Trie 二分答案 状态压缩 无聊时候的一点思考 最短路 FHQ Treap NOI/NOI+/CTSC 前端 前缀和 树链剖分
ABOUT ME

要做一个优秀的 OIER

FRIENDS