做题记录
2026-08-28 11:50:02
发布于:上海
美国时间8/12
P2851
思考一下不难发现John的最小交付硬币数相当于多重背包,店主的找零相当于完全背包,那么先把这几个求出来,但是John多付一些钱去找零的方案可以更优,最后统计结果是取付钱的最少硬币数+找零的最小硬币数的最小值。背包上界值用余数的鸽巢原理证一下的求出 。(但是由于数据太水10100的上界甚至也过去了)
Code
美国时间8/16
P1117
贴主是看题解才会100分的,所以讲的不明不白。
先考虑 做法,由于题面允许 所以相当于两个 串拼接在一起,所以先求出以每个点为结尾和开头的 串数量,可获得95pts。
考虑遍历 的长度,每 个字符放一个标记点,不难发现每个 串中必然有且仅有2个相邻标记点,因此遍历相邻标记点。
每个 串中的 由2个部分组成:从相邻标记点往后的 和 相邻标记点往前的 ,只有当 时才能构成 串。然后用差分记录答案。
这里求 和 可以直接用后缀数组,但是由于我太弱了不会,所以选择用多一只 的二分哈希,代码细节不少。
Code
美国时间8/17
P13323
本质上是一个最长公共子序列,将每一个段作为整体求最长公共子序列,但是需要把前面的段内别的可以匹配的放进来。
Code
P14347
在最优状态下有几个重要结论:区间覆盖操作不相交,区间翻转操作不相交,先区间覆盖再区间翻转一定不劣,具体证明看题解,这里就不写了。
然后定义 表示为当前第 位,这一位不覆盖,不翻转; 表示为当前第 位,这一位不覆盖,翻转; 表示为当前第 位,这一位覆盖为0,不翻转; 表示为当前第 位,这一位覆盖为0,翻转; 表示为当前第 位,这一位覆盖为1,不翻转; 表示为当前第 位,这一位覆盖为1,翻转。
转移时如果第二维或第三维不为 且与 的这一维状态不同则需要在前一位基础上加一,具体实现见代码。
Code
美国时间8/18
P3488
这道题首先用hall定理转化一下问题,转化后为:在任意区间(设为 )内脚的总数鞋必须全部小于等于 才能全部匹配,那么将式子转化一下成为求脚的数量减去鞋子的数量的最大子段和再减去 ,判断其正负性,线段树维护即可。
Code。
美国时间8/21
美国时间8/22
P2114
从高位往低位贪心,如果这一位设为0不劣或上界不足设1则设为0,否则设为1。
Code
P8572
根号分治题。
如果 预处理所有 的答案。
否则用前缀和按照题意模拟即可。
Code
美国时间8/24
P9000
设 表示第 个人的位置, 为 的相对最终位置,因为题目相当于求最小的最大值,所以左移可以相对地变为右移,则最终答案等于 ,由于 恒为0,所以相当于求 。
则 ,代入答案式得 ,线段树维护即可。
Code
中国时间8/25
中国时间8/26
P1377
注意到最终的树按插入顺序来看是小根堆,按权值来看是二叉搜索树,而笛卡尔树的性质是按权值来看是小根堆,按插入顺序来看是二叉搜索树。因此把插入顺序和权值交换一下就好了(其实数据范围也提示了这一点)。
Code
P3793
太好了是随机数据,说明建出来的二叉搜索树是平衡的。因此建出笛卡尔树,找到查询区间内节点的LCA的权值即可,具体实现的话,如果当前节点在区间左端点外则走右儿子,在区间右端点外则走左儿子,直到其落到区间内输出即可。
时间复杂度,虽不是神秘类四毛子算法的线性复杂度但是常数极小,因此能过。
Code
中国时间8/27
P3586
查询先把每个数大于 的部分砍掉,若 即输出 TAK。实现用值域树状数组即可。
Code
中国时间8/28
喜报:一天没看我做的19道紫降了3道,做的速度赶不上降的速度那咋办/yi。
P2597
看到DAG和食物链一眼拓扑。先建立一个超级源点作为每一个单独的DAG中生产者的共同食物,这样图中只剩一个生产者。先反向连边(食物猎物),不难发现任何一个点 总能找到另外恰好一个离它最近的点 ,使得一旦 灭绝, 也一定灭绝。然后将 当作 的父亲建树(称其为灭绝树),最终个点 的答案就是 的子树大小。
具体实现时在拓扑排序的过程中通过灭绝树上 的猎物的LCA更新节点在灭绝树上的父亲,因为根据拓扑序,更新转移时 的猎物一定已经出现在了灭绝树上(拓扑序的性质),别忘了将节点入队时更新ST表。
Code
全部评论 7
- 置顶
本贴评论区禁止发表批话,最终解释权归我所有
22小时前 来自 上海
05小时前 来自 上海
0
为啥,这么多青,这么多蓝,这么多紫,我看不懂
21小时前 来自 广东
0因为您,自动,忽略了,完全不足,您的,水平,的知识
21小时前 来自 上海
0给个建议,用白色字写题解,不然做法全透露了/咦/咦/咦
21小时前 来自 广东
0你会,鸽巢原理,青背包,串串题,定长分块,SA,二分哈希,青 dp,青 dp 性质证明,Hall 定理,蓝 ds,简单树论,数位贪心,根号分治,背板板,拆式子,笛卡尔树,批,批,批,批,批,批,批,批,批,批,批,批,批,批,批,批,批,批
21小时前 来自 上海
0
P3793 不是,暴力 LCA,也能,过
21小时前 来自 广东
0我咋不知道我咋这么弱/yi
21小时前 来自 上海
0还在,批
21小时前 来自 上海
0
你咋这么牛
21小时前 来自 广东
0你咋这么批
21小时前 来自 上海
0/对对
21小时前 来自 上海
0
强烈谴责 /fn /fn /fn
22小时前 来自 浙江
0怎么你了
22小时前 来自 上海
0本贴评论区禁止发表批话,最终解释权归我所有
本贴评论区禁止发表批话,最终解释权归我所有
本贴评论区禁止发表批话,最终解释权归我所有
本贴评论区禁止发表批话,最终解释权归我所有
本贴评论区禁止发表批话,最终解释权归我所有
本贴评论区禁止发表批话,最终解释权归我所有
本贴评论区禁止发表批话,最终解释权归我所有
本贴评论区禁止发表批话,最终解释权归我所有
本贴评论区禁止发表批话,最终解释权归我所有
本贴评论区禁止发表批话,最终解释权归我所有
22小时前 来自 浙江
0对啊咋了
22小时前 来自 上海
0
w
23小时前 来自 浙江
0dsa
23小时前 来自 浙江
0

























有帮助,赞一个