TH911 Blog

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

题解：[NOIP2022] 种花

洛谷P8865

题目传送门 题意分析 首先，观察样例解释，显然可以发现所谓的 F 就是 C 下面带了一段。 样例解释 四个 C- 形种花方案为： 1 2 3 4 **1 **1 **1 **1 *10 *10 *10 *10 **0 *** *00 *00 000 000 **0 *** 其中 * 表示在这个位置种花。注意 C 的两横可以不一样长。 类似的，...

Posted by TH911 on April 18, 2025

题解：[NOIP2020] 排水系统

洛谷P7113

题目传送门 题意分析 “不会发生污水形成环流的情况”，即无环，则整张图为一张有向无环图。 那么很容易想到拓扑排序，拓扑排序后统计贡献即可。 这道题目的难度可能就在于分数运算，但是也不难，写个结构体用 __int128 实现即可。 AC 代码 时间复杂度：$\mathcal O(n\log V)$。其中 $\mathcal O(\log V)$ 是求解最大公因数带来的。 ...

Posted by TH911 on April 18, 2025

题解：[NOIP 2017 提高组] 时间复杂度

洛谷P3952

题目传送门 大模拟 对于这种模拟题，其实题解也几乎没什么好说的——依据题意模拟即可。 注意事项 某些循环体不会被执行，其内部的循环体也不会被执行，不应当计入时间复杂度。 注意变量的上下界 $x,y$ 当 $x>y$ 时不会执行，$x=y$ 时为常数复杂度（包括 $x=y=n$）。 AC 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 1...

Posted by TH911 on April 12, 2025

题解：[NOIP 2017 普及组] 棋盘

洛谷P3956

题目传送门 DFS 暴力搜索 这是可以写的，从 $(1,1)$ 开始搜索，当搜索到 $(m,m)$ 的时候结束，记录答案。 设 $dfs(i,j,step,0/1)$ 表示搜索到 $(i,j)$，已经花费了 $step$ 金币，能否使用魔法。 从节点 $(i,j)$ 到达的节点 $(i’,j’)$ 的分支有三种： $(i,j),(i’,j’)$ 颜色相同，下...

Posted by TH911 on April 12, 2025

题解：The Number Games

CF980E

题意分析 给定一棵 $n$ 个节点的树，第 $i$ 个节点的权值为 $2^i$。从中删除 $k$ 个节点，使得剩下 $n-k$ 个节点联通且权值和最大。 求删除哪 $k$ 个节点。 贪心性质 权值为 $2^i$ 毫无疑问是极其特殊的，因此我们可以考虑有没有一些性质。 显然，$2^x>2^{x-1}+2^{x-2}+2^{x-3}+\cdots+2^{0}$，因此我们可以考虑贪...

Posted by TH911 on April 12, 2025

题解：[NOIP 2015 提高组] 子串

洛谷P2679

题目传送门 DP 状态设计 因为需要满足无后效性原则，因此 DP 考虑的肯定是两段前缀。 设 $f_{i,j,p,0/1}$ 表示从 $A$ 中取前 $i$ 个字符（第 $i$ 个字符选或不选）取 $p$ 段，匹配 $B$ 中前 $j$ 个字符的方案数。 DP 状态转移 $A_i=B_j$ 时。 显然，有 $f_{i,j,p,0}=f_{i-1,j...

Posted by TH911 on April 11, 2025

题解：傻逼数学题

题目见正文

洛谷自建题目传送门 数据包 题目 题目描述 众所周知，数学组有一个神犇叫做 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

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

要做一个优秀的 OIER

FRIENDS