[DP]Codeforces1453F【Even Harder】题解
题目概述CF1453F解题报告考虑路径计数 $cnt_i=\sum_{j=1}^{i-1}[j+a_j\ge i]cnt_j$ ，如果想要 $cnt_n=1$ ，那么一定不存在一个 $cnt_i...
[背包+构造]Codeforces1444D【Rectangular Polyline】题解
题目概述CF1444D解题报告这题演我啊，我看三个 $1000$ 以为有什么高级的分半算法，结果写背包能过QAQ。首先显然 $h\not=v$ 时无解，然后我们需要把水平线段和竖直线段都拆成两半...
[思维+DP]Codeforces1446C【Xor Tree】题解
题目概述CF1446C解题报告画下Trie树，不难发现如果一个节点 $0$ 子树中只有一个元素，$1$ 子树中只有一个元素，那么这两个元素就会形成重边。由于题目要求形成一棵树，因此重边必须有且只...
[计数+DP]2020 CCPC 秦皇岛站 H【Holy Sequence】题解
题目概述一个合法的整数数列 $\{a_n\}$ 需要满足：$1\le a_i\le n$ 。令 $p_i=\max\{a_k|1\le k\le i\}$ ，则 $p_i\le p_{i-1}+...
[DP]Codeforces1427C【The Hard Work of Paparazzi】题解
题目概述CF1427C解题报告我又被傻子题干翻了😭，首先 $O(n^2)$ DP非常好想，需要优化。由于保证了 $t_i<t_{i+1}$ ，所以当 $j+2(r-1)\le i$ 时，$...
[计数+背包]AtCoder Regular Contest 104D【Multiset Mean】题解
题目概述AtCoder Regular Contest 104D解题报告对于每个 $x$ ，我们认为第 $i$ 个物品大小为 $x-i$ ，共有 $K$ 个，现在的问题就转化为有多少种方案，使得...
[DP]AtCoder Regular Contest 104C【Fair Elevator】题解
题目概述AtCoder Regular Contest 104C解题报告我英语太渣题目读错了😭，以为只要存在某两个人满足 $C_i=C_j$ 就行了，实际上应该是只要出现两个人在电梯上，就必须有...
[DP+单调栈+线段树动态开点]Codeforces1407D【Discrete Centrifugal Jumps】题解
题目概述有 $n$ 个建筑物，高度 $h_i$ 。要从 $1$ 跳到 $n$ ，求最少跳跃步数。$i\to j$ 的跳跃要求：$i+1=j$$\max(h_{i + 1}, \ldots, h_...
[KDT+DP]BZOJ1171【大sz的游戏】题解
题目概述有 $n$ 个基地，每个基地可以发射和接收 $[x_i,y_i]$ 频率内的信号，坐标为 $l_i$ ，且 $i$ 号基地只能往前发射到距离不超过 $L$ 的基地。求 $[2,n]$ 的...
[DP]BZOJ4321【queue2】题解
题目概述求不存在 $|a_i-a_{i+1}|=1,i<n$ 的 $n$ 的排列 $\{a_n\}$ 的个数。解题报告定义 $f_{i,j,0/1}$ 表示前 $i$ 个数，有 $j$ 个...
