TH911 Blog

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

题解：绝世好题

洛谷P4310

题目传送门 回顾：最长子序列问题 先让我们回想一下最长上升子序列是如何解决的。 定义 $dp[i]$ 表示以 $a[i]$ 结尾的最长子序列的长度。 那么 $dp[i]$ 就是在 $[1,i-1]$ 中找到一个满足 $a[j]<a[i]$ 且 $dp[j]$ 最大的 $j$，则 $dp[i]=dp[j]+1$。 这是 $\mathcal O(n^2)$ 的做法。 ...

Posted by TH911 on January 18, 2025

Pick 定理的证明

毕克定理 | 皮克定理 无聊时候的一点思考

之前想的，现在记录一下。 定理阐述 将定点都在正方形网格格点上的多边形称为“简单多边形”，则任意简单多边形面积都为其边上格点数的一半加上其内部的格点数减去 $1$，简述为： \[S=\frac12A+B-1\] 其中 $S$ 为面积，$A$ 为边上格点数，$B$ 为内部格点数。 例如：如图所示图形，显然 $A=10,B=18$，则 $S=\dfrac12A+B-1=22$。...

Posted by TH911 on January 3, 2025

如何证明一条直线与圆至多有两个交点？

反证法 | 无聊时候的一点思考

其实可以推广到普通凸多边形。 反证法 假设一条直线 $l$ 与一圆可以存在多于 $2$ 个交点。 从交点集中选出三个点 $A,B,C$，连接 $AB,BC$。 令圆心为点 $O$，连接 $OA,OB,OC$。 $\therefore OA=OB=OC$。 取点 $P$ 为 $AB$ 中点，点 $Q$ 为 $BC$ 中点。 $\because OA=OB,PA=PB$...

Posted by TH911 on January 3, 2025

题解：[ABC232G] Modulo Shortest Path

AtCoder ABC232G

题目传送门 题意分析 $n$ 个点的完全图，求 $1\sim n$ 的最短路径。 如果我们直接使用朴素 Dijkstra $\mathcal O(n^2)$ 求解，会 $\text{TLE}$。 因此我们考虑优化建图。 优化建图 考虑到 $a_i,b_i<m$，因此边 $u\to v$ 的边权 $(a_u+b_v)\bmod m$ 只有可能是 $a_u+b_v$ 或...

Posted by TH911 on January 3, 2025

2025 元旦快乐

元旦快乐！ 元旦快乐！

Posted by TH911 on January 1, 2025

OI 优化技巧

快读快写,卡常,清空,mt19937

快读快写 scanf 与 printf 没什么好说的。 关闭同步流与解除绑定 众所周知，cin 与 cout 的 IO 效率十分低下，主要原因就是因为需要兼容 C 的 scanf 和 printf 以保证线程安全而不混乱。 我们以下代码来关闭同步流并解除绑定： 1 2 ios::sync_with_stdio(false); std::cin.tie(nullptr); ...

Posted by TH911 on December 31, 2024

关于OI Wiki的<details>样式的复刻

前言 之所以想要搞这个，纯粹是因为某些文章过长想要折叠（比如说 LCA 和 FHQ Treap），但是又嫌弃原版折叠太丑，于是盯上了 OI Wiki 的折叠效果。 发现 OI Wiki 的 css 文件没有单独列出折叠虽然是个正常人写的代码都不会单独搞一个文件，于是全部复制进 Blog 的 css 文件 hux-blog.css，然后删掉与折叠无关的，行数从 $8872$ 降到 $2...

Posted by TH911 on December 28, 2024

题解：[NOIP2024] 编辑字符串

洛谷P11361

题目传送门 T1 蓝切了，T2 绿只得了 20 分…… 题意分析 给定字符串 $s_1,s_2$ 和标记数组 $t_1,t_2$，$t_i[j]$ 表示 $s_i$ 的第 $j$ 位是否可以参与交换。 同一字符串内任意两个可以参与交换的相邻的字符可以交换，让你求出最多有多少位是相同的。 我们其实可以使用一个很简单的贪心来求解。 首先，对于第 $i$ 位，如果能够通过交换使...

Posted by TH911 on December 27, 2024

题解：[SCOI2010] 序列操作

洛谷P2572

题目传送门 题意分析 我们需要维护一种数据结构来维护 $0,1$ 区间的信息，使其能够高效的获取区间内 $1$ 的数量和最多的连续的 $1$ 的数量，并能够高效的将指定区间赋为指定值和实现区间翻转（注意是值取反，而不是类似于字符串的翻转）。 维护区间信息 线段树节点维护信息 维护区间信息，自然而然地想到线段树。 那么需要维护哪些信息呢？ 一般地，区间边界 $l,r$。 ...

Posted by TH911 on December 21, 2024

题解：三元上升子序列

洛谷P1637

题目传送门 题意分析 通过树状数组可以在 $\mathcal O(n\log n)$ 的时间内求出所有 $i<j$ 且 $a_i<a_j$ 的 $(i,j)$ 的个数。 仅仅需要在从左向右遍历的过程中在权值树状数组中查询小于等于 $a_i-1$ 的个数并加入 $a_i$ 即可。 那么我们需要求出所有 $i<j<k$ 且 $a_i<a_j<a...

Posted by TH911 on December 21, 2024

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

要做一个优秀的 OIER

FRIENDS