TH911 Blog

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

题解：XOR 操作

题目见正文

洛谷自建题目 数据包 题目 题目描述 有一圈数 $a_1,a_2,a_3,\cdots,a_n$，定义一次操作为每个数变成原数圈中的自己与相邻的两个数这三个数的异或和，给出原数组和操作次数，计算出最后的结果数组。 输入格式 输入第一行包含两个正整数 $n$ 和 $k$，分别表示数的数目与操作次数。接下来一行 $n$ 个数，表示 $a_1,a_2,a_3,\cdots,a_n...

Posted by TH911 on March 8, 2025

题解：盾盾的打字机

题目见正文

洛谷自建题目 数据包 题目 题目描述 盾盾有一个非常有意思的打字机，现在盾哥要用这台打字机来打出一段文章。 由于有了上次的经验，盾盾预先准备好了一段模板 $A$ 存在了内存中，并以此为基础来打出文章 $B$。盾盾每次操作可以将内存中的某一个字符改成另一个字符，或者在某一个位置插入一个字符，或者删除某一个位置上的字符。另外，为了避免自己预存的模板太腿反而浪费时间，盾哥在所有操作...

Posted by TH911 on March 8, 2025

题解：编辑距离

洛谷P2758

题目传送门 题意分析 给定字符串 $a,b$，有三种操作： 删除一个字符； 插入一个字符； 修改一个字符。 求至少需要多少次操作才能将 $a$ 转换为 $b$。 DP 状态设计 设 $dp_{i,j}$ 表示 $a$ 的前 $i$ 个字符转化为 $b$ 的前 $j$ 个字符的最少操作次数，即将 $a[1,i]$ 转化为 $b[1,j]$ 的最少操作次数。...

Posted by TH911 on March 8, 2025

广义串并联图

广义串并联图

如果你有一个序列上的问题，可以尝试将其放在树上。 如果你有一个树上的问题，可以尝试将其放在仙人掌[^1]上。 如果你有一个仙人掌上的问题，可以尝试将其放在广义串并联图上。 广义串并联图 定义 不存在同胚于 $K_4$ 的子图的无向图。即，对于任意 $4$ 个点，不能存在下图： 串联与并联 其实也可以借助电路来理解。广义串并联...

Posted by TH911 on February 23, 2025

题解：[PA 2013] Iloczyn

洛谷P5973

题目传送门 题意分析 对于正整数 $n,k$，求能否将 $n$ 划分为 $k$ 个不同的正整数的乘积，多测。 搜索 观察数据范围，可以发现 $1\leq k\leq 20$，拆出来数的个数不会太多，因此考虑 DFS。 很容易写出一个暴力 DFS 的判断函数： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 //last用于防止重复 bool check(...

Posted by TH911 on February 22, 2025

题解：Naughty Stone Piles

CF226B 和 CF227D

洛谷 RMJ 226B 题目传送门 CF 226B 传送门 CF 227D 传送门 为什么这么近就重题了。 题意分析 如果不考虑合并 $k$ 次的限制，就是一个普通的合并石子问题，思路即将小堆合并到大堆上，这样小堆的计算次数会更多，大堆的计算次数会更少，进而使得总代价最小。 考虑加入 $k$ 次限制之后总代价的形式： 存在 $1$ 个 $a_i$ 满足 $a...

Posted by TH911 on February 22, 2025

题解：Permutations

CF187A 和 CF189C

洛谷 RMJ 187A 题目传送门 CF 189C 传送门 CF 187A 传送门 为什么这么近就重题了。 题意分析 给出 $1\sim n$ 的两个排列 $a,b$，每次可以将 $a$ 末尾的数取出插入到 $a$ 的任意位置，求最少需要多少次能够将 $a$ 转化为 $b$。 我们可以考虑令 $\large map_{b_i}=i$，那么使 $a$ 按照 $\lar...

Posted by TH911 on February 22, 2025

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

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

要做一个优秀的 OIER

FRIENDS