TH911 Blog

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

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

其实可以推广到普通凸多边形。反证法假设一条直线 $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

树状数组详解

例题：树状数组 1（P3374）、树状数组 2（P3368）、守墓人（P2357）

题目传送门：树状数组 1、树状数组 2 、守墓人防止日后忘记。引入例题 $1$：已知一个数列，你需要进行下面两种操作：将某一个数加上 $x$。求出某区间每一个数的和。对于操作 $1$，我们可以直接通过普通数组 $\mathcal O(1)$ 实现修改。对于操作 $2$，我们可以通过前缀和 $\mathcal O...

Posted by TH911 on December 14, 2024

《三体》电子书

三体I：地球往事三体II：黑暗森林三体III：死神永生