0103abc 的网站

先考虑灌水操作会发生什么。在 $x$ 位置加水直到 $ax\ge h$，特判掉原来已经有 $ax\ge h$ 的情况。然后考虑水位上涨到 $h$ 的时候只能越过高度 $<h$ 的挡板。因此从 $x$ 位置出发二分找出左右第一块高度 $\ge h$ 的挡板。假设她们围出的格子区间是...

真的是人类能想出来的题吗？？？？ 套路的先挖掘题目的性质。容易发现先染色再折叠一定不会更差。证明可以考虑厚度为 $k$ 的绳子染色需要花费 $k$ 等价于再折叠前把组成她的 $k$ 根单位绳分别染色或者调整法。 然后考虑在大脑中想象绳子折叠的过程。此时可以发现一个只含有两个颜色的序列能够折成长度为...

非常困难的题目。考虑对当前的每一个第 $i$ 类物品，记录一个信息 $w$ 表示组成她的哪些物品，在只考虑前 $i$ 类物品的情况下，最多可以贡献的价值是多少。 首先如果直接保留当前物品，则可得到 $vi$ 的贡献，因此可以直接更新每张纸币代价为 $\max(w,vi)$，新加入的 $ci$...

管理员备注：本题可能是错题。 2025.1.27 update：现在本题存在多项式解，但仍然无法在原数据范围下通过（UOJ941）。 $O(n^3)$ 做法，但是过了所有数据而且还过拍了，不知道对不对（疑似是对的），先写一下，欢迎来 hack。...

看到单调栈容易想到笛卡尔树分治。设区间 $[l,r]$ 中的最小值位于 $k$ 位置，则： 处理到 $k$ 位置时，前面 $[l,k-1]$ 部分在栈中的元素都会被弹出，因此 $b_k$ 就等于扫描左半段后单调栈内元素数量。 最小值入栈后，右半段 $[k+1,r]$...

特判掉序列中左括号和右括号出现次数不同的情况。 套路的把左括号 看作 $1$，右括号 看作 $-1$。因为处理的信息是字符串的所有循环移位，因此考虑把字符串旋转成从前缀和最小值处开始的循环移位。 如果不交换字符的话答案就是前缀和数组中最...

有点 boring 的题。很显然有答案上界 $|sl-el|+|sc-ec|$。 如果在某一行最左侧不能按左键，在某一行最右侧不能按右键，那么问题是十分简单的，容易发现此时直接从 $(sl,sc)$ 位置开始，先一直按上键 / 下键直到和 $(el,ec)$ 处于同一行，然后再按左键 /...

不是很难。容易想到给所有串建一个 Trie 然后在 Trie 上 dp（为了方便，后面记 Trie 上的 $i$ 点是第 $i$ 个串的结尾位置，$0$ 号结点为 Trie 的根结点）。设 $fi$ 表示到达 Trie 上 $i$ 号点所需要的最小操作次数。则初始条件是...

容易发现序列必须是单谷序列，否则必然不满足性质。 考虑枚举谷的位置为 $p$，则有这样一个经典的刻画单谷序列的方式： 执行若干次下面的操作： 把序列 $a$ 中所有元素的值都增加 $1$。 选择一个位置 $i\neq p$： 若 $i<p$，则将...