TH911 Blog

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

Vercel 部署 Jekyll 踩坑

1 [22:46:49.890] /vercel/path0/vendor/bundle/ruby/3.3.0/gems/jekyll-4.4.1/lib/jekyll/url.rb:161:in `encode': "\xE4" from ASCII-8BIT to UTF-8 (Encoding::UndefinedConversionError) 不要在文件或文件夹的名称中使用非英...

Posted by TH911 on February 16, 2025

题解：[NOI2001] 陨石的秘密

洛谷P5694

题目传送门 题意分析 先说一个坑：当 $l_1=l_2=l_3=d=0$ 时不是绝对无解。 我们考虑 $\large f_{l_1,l_2,l_3,d}$ 表示所有含有 $l_1$ 对 {}，$l_2$ 对 []，$l_3$ 对 () 的深度小于等于 $d$ 的 SS 串的个数。 关于为什么是“小于等于”，我们考虑这样一件事。 对于 SS 串 $S=AB$，若 $A$ ...

Posted by TH911 on February 15, 2025

题解：跑路

洛谷P1613

题目传送门 题意分析 给出 $n$ 个点，$m$ 条有向边，每一步能够走 $2^k$ 条边，求从节点 $1$ 走到节点 $n$ 至少需要走几步。 因为一次能够 $2^k$ 条边，一个很自然的思路就是对于每一个节点 $x$，都找出所有其能够通过 $2^k$ 步走到的节点 $y_i$，然后建新图并连边 $(x,y_i)$。 然后，新图边权为 $1$，在新图上跑最短路即可。 考虑...

Posted by TH911 on February 8, 2025

数论学习笔记

同余 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

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

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

要做一个优秀的 OIER

FRIENDS