TH911 Blog

树上最近公共祖先（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

保留区

用于记录想说的话。

Posted by TH911 on October 19, 2024

题解：Addition Chains

UVA529

洛谷同步链接题目传送门（洛谷）题目传送门（UVA）前置知识：迭代加深搜索定义迭代加深是一种每次限制搜索深度的深度优先搜索。——OI Wiki 简单而言，就是一种限制搜索深度的DFS。有什么变化？？过程设搜索深度上限为 $h$，搜索深度为 $p$ 。那么 $h$ 从 $1$ 开始自增，并在每次自增前进行DFS。（形如 dfs(p,h,.....

Posted by TH911 on October 19, 2024

题解：[SCOI2005] 互不侵犯

洛谷P1896

洛谷同步链接题目传送门什么是状压DP 状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。 ——OI Wiki 状态压缩例如，给定一个 bool 数组 $c$，那么 $c_i$ 为 $0$ 或 $1$。我们可以将其压缩为一个二进制整数 $(a)_2$，这样 a&(1<<i) 即 $c_i$。可以参照下表： ...

Posted by TH911 on October 18, 2024

题解：[NOIP2016 提高组] 蚯蚓

洛谷P2827

洛谷同步链接题目传送门前置结论结论对于整数 $x_1,x_2$ ，当 $x_1\geq x_2,0<p<1$ 时有： $\lfloor px_1 \rfloor \geq \lfloor px_2 \rfloor$ $x_1 -\lfloor px_1 \rfloor \geq x_2- \lfloor px_1 \rfloor$ 证明...

Posted by TH911 on October 17, 2024

题解：[蓝桥杯 2024 省 C] 商品库存管理

洛谷P10903

本文转载自我在洛谷上P10903的题解。前置知识：前缀和与差分前缀和简单而言，给定数组 $a_1,a_2,a_3,\cdots,a_n$，现在想要快速求出 $a_l,a_{l+1},a_{l+2},\cdots,a_r$ 的和。朴素算法遍历 $a_l$ 至 $a_r$，时间复杂度 $\mathcal O(r-l+1)$。使用前缀和算法，时间复杂度 $...

Posted by TH911 on October 13, 2024

Google Translate失效修复指南

网页与API

前言众所周知，Chrome内置的网页翻译API就是Google Translate，然而失效后却十分不便。声明：如果你害怕麻烦的话，可以直接使用Edge。为什么失效 Google Translate失效的主要原因是Google退出中国市场，关闭了国内翻译API及网站。现在访问translate.google.cn也是这样：解决方案某些过期的文章给定的解决方案时修...

Posted by TH911 on October 12, 2024

洛谷P2357

个人记录

这仅仅是过去写的一个记录，更详细请见树状数组详解，本题是作为例题讲解的。洛谷同步链接题目传送门与普通树状数组不同的是，这次既需要单点修改、区间查询，又需要区间修改、单点查询。对于数组 $a$ 的差分数组 $d$，我们可以使用 $d$ 求出 $a$ 的前缀和数组 $s$。由于 $d_k=a_k-a_{k-1}$，则： \[a_k=d_1+d_2+d_3...

Posted by TH911 on October 2, 2024