Gym 101635 题解

A

暴力枚举差。

C

状压矩阵快速幂。

E

背包。

F

模拟。

G

增加 n-1 个餐馆点,跑 KM。

J

3 分组直接算答案。

K

旋转卡壳。


B

每一层从左往右枚举,维护上边界的单调栈,弹栈的时候考虑要去掉哪些矩形的答案,是左边被弹掉的一个矩形与这个格子右边的一排格子之间造成的贡献,也就是若干矩形减。一个维度上差分,另一个维度上差分两次,就只需要修改 8 个位置。

D

区间 dp 算删除这个区间的答案。算一个区间的答案就枚举第一个字符所在字符串,放在 Trie 上,每次要么往后考虑一个字符走一步,要么往后删去一段。状态很少拿个队列优化。

H

暴搜所有状态,即当前在每个限制上走到了第几个字符。由于每个限制没有多次出现一个字符所以转移是唯一的。状态数很少。

I

f(i,j,k) 表示 i 层以后,入口出口分别在 jk 的答案,暴力转移,注意关于 j=k 的特判。

发表评论

电子邮件地址不会被公开。 必填项已用*标注