TH911 Blog

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

数论学习笔记

同余 CRT exgcd BSGS Lucas

参考资料 参考资料 本文中出现的代数式、数，如无特殊说明，均为整数。 对于 OI 中的数论题，答案不对请先尝试： 1 2 3 #define int __int128 typedef long long ll; #define ll __int128 数论函数指的是定义域为正整数的函数，也可以视为一个序列。 基础部分 $\perp$ 在数论中表示“互质”，例如 $2\p...

Posted by TH911 on February 5, 2025

组合数学学习笔记

排列组合 母函数与递推关系 容斥原理与鸽巢原理

参考资料 参考资料 参考资料 待办事项 斜体 的是不会的，加粗的是正在写的，下划线的是暂 可重复圆排列（莫比乌斯变换） 伯努利数 不定方程非负整数解计数 容斥原理与第二类 Stirling 数 多重组合数 与 多重集的组合数 同一列的第二类 Stirling 数计算 同一行的第一类 Stirling 数计算 同一列的第一类 Stirl...

Posted by TH911 on February 4, 2025

Blog 的配置模板

YAML Front Matter

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 --- layout: post title: "题解：[BalticOI 2018] 基因工程" subtitle: "洛谷P4795 | 基于随机化 + bitset 的做法" date: 2025-1-26 author: "TH911" header-img: "img/2024/10/006....

Posted by TH911 on February 4, 2025

Vercel 部署后通过Cloudflare代理导致重定向次数过多的解决方案

部署 XPlayer 时遇到的问题

前情提要：因为将 XPlayer 部署在 Blog 的目录下，Blog 本体的 Service Worker 缓存仍然生效，于是会导致在 iOS 上异常……因此想要转换到独立域名上。 然后 GitHub Pages 有点慢，于是转 Vercel 部署。（GitHub Pages 部署仍然生效） 第一步：将SSL模式更改为“完全（严格）”。 第二步：关闭代理。 第三...

Posted by TH911 on January 28, 2025

二分图

「理论上到现在应该已经学习完了所有 NOIP 考纲内的知识点，如果还有不会的赶紧学习。」 突然发现自己从来没有学过二分图。想起来去年本来想学，但是看了一下好像没怎么考，学别的去了。 二分图基础 定义 对于一张图，如果其点集可以划分为两个部分，且图上的每一条边的两个端点都不在同一个部分中，则称这个图为「二分图」。 形式化地，设图 $G=(V,E)$，若 $V=X\cup ...

Posted by TH911 on January 26, 2025

题解：[BalticOI 2018] 基因工程

洛谷P4795 | 基于随机化 + bitset 的做法

题目传送门 $\mathcal O\left(n^3\right)$ 暴力做法 $\mathcal O\left(n^2\right)$ 枚举两个字符串，$\mathcal O(n)$ 计算差异个数。 $\mathcal O\left(\frac{n^3}{w}\right)$ 做法 $w$ 为计算机字长，一般为 $64$ 或 $32$。 （如果不会 bitset 或 sh...

Posted by TH911 on January 26, 2025

题解：[POI2008] BLO-Blockade

洛谷P3469

题目传送门 前置知识：Tarjan 求割点 不会可以看看。 题意分析 给定 $n$ 个点，$m$ 条边的无向图，点从 $1$ 至 $n$ 标号。 求对于每一个点 $i$，删除该点后不连通的有序点对 $(x,y)$ 的个数。 保证给定图连通。 割点 因为原图连通，所以最开始时对于任意两个点都是连通的。 而删去某个点 $i$ 后如果存在点对 $(x,y)$ 满足点 $x...

Posted by TH911 on January 25, 2025

题解：[POI2000] 病毒

洛谷P2444 | 有向图 DFS 找环

题目传送门 加强版数据包 加强版数据包满足病毒代码段总长度不超过 $1000000$，且绑包。 暴力 $\text{84pts}$ 做法 第一眼发现不会做，我们考虑暴力。 枚举长度 我们可以枚举每一位，直到枚举到第 $2\times len$ 时结束代表存在无限长的安全代码，其中 $len$ 表示病毒代码段的最长长度。 为什么 ...

Posted by TH911 on January 24, 2025

题解：间谍网络

洛谷P1262

题目传送门 一道水的 提高+/省选−，但是可能会降 普及+/提高。 因为这个请求升 提高+/省选− 的理由是另一道差不多的题目是 提高+/省选−，但是该题已经降 普及+/提高。 $\text{Updated at 2025/7/21}$ 真的降 普及+/提高 了…… 前置知识 Tarjan 缩点和拓扑排序。 题意...

Posted by TH911 on January 24, 2025

无向图 Tarjan 点双连通分量详解

例题：洛谷P8435

例题链接 有向图没有点双连通分量 有向图请见强连通分量。 点双连通分量 点双连通 若一个无向连通图删去任意一个点之后仍然连通，则该图点双连通。 点双连通分量 在满足边双连通的前提下尽可能大的子图。 Tarjan 求点双连通分量 前置知识 Tarjan 求割点。 三条性质 两个点双连通分量存在至多一个...

Posted by TH911 on January 23, 2025

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

要做一个优秀的 OIER

FRIENDS