TH911 Blog

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

题解：傻逼数学题

题目见正文

洛谷自建题目传送门 数据包 题目 题目描述 众所周知，数学组有一个神犇叫做 HSY。 一天他对 XYK 说：“听说你数学很好，那我出一道数学题考考你。” “给定一个包含 $n$ 个互不相同的数的序列 $a$，定义序列 $b$ 为 $b_i=\max\limits_{j<i,a_j<a_i}b_j+1$，且 $b_1=1$。” “定义‘$k$ 号序列’为：满足对...

Posted by TH911 on April 6, 2025

题解：Arena

CF1606E

题目传送门 题意分析 有 $n$ 个人，第 $i$ 个人的血量为 $a_i$，每一轮每一个存活的人都会让其他所有人的血量减 $1$，血量小于等于 $0$ 死亡。 给出人数 $n$ 和 $x$，满足 $a_i\leq x$（$a_i$ 最大值不一定为 $x$），求 $a_i$ 可能的方案数，对 $998244353$ 取模。 考虑 DP。 状态设计 令 $dp_{i,j}$...

Posted by TH911 on March 29, 2025

题解：[NOIP 2015 普及组] 求和

洛谷P2671

题目传送门 题意分析 对于三元组 $(x,y,z)$，显然其对于答案的贡献与 $y$ 无关，因此可以考虑消去 $y$。$y-x=z-y$ 即 $x+z=2y$，也就是说 $x,z$ 奇偶性相等。 $\text{50pts}$ $\mathcal O(n^2)$ 枚举 $x,z$，判断 $color$ 值是否相等后统计答案即可。 1 2 3 4 5 6 7 8 9 10 11...

Posted by TH911 on March 28, 2025

题解：MT 与 OI

题目见正文

洛谷自建题目 数据包 题目 题目描述 在 MT 刚接触到了冒泡排序的时候，觉得这个东西太慢了，但是加上 break 的效果怎么样呢？于是他开始考虑这样一个问题：任意一个 $N$ 的排列中，有多少种需要恰好扫 $K$ 次才能使得数列从小到大排列。所谓扫就是第一重循环，当数列有序后程序会自动退出循环。 冒泡排序的代码： 1 2 3 4 5 6 7 for(int i=1;i&l...

Posted by TH911 on March 22, 2025

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

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

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

要做一个优秀的 OIER

FRIENDS