xixike

# Description Luogu 传送门 # Solution 一直以为这是道数学题，结果是 dp\text{dp}dp…… 观察题目给的式子，不难发现，这就是个长为 ai+aja_i + a_jai​+aj​，宽为 bi+bjb_i + b_jbi​+bj​ 的矩阵，让你求从左下角走到右上角的方案数。 转移方程也非常简单： dpi,j=dpi−1,j+dpi,j−1dp_{i, j} = dp_{i - 1, j} + dp_{i, j - 1} dpi,j​=dpi−1,j​+dpi,j−1​ 但是转移完之后我们还是要 O(n2)O(n^2)O(n2)...

说是游记其实就是在在机房里考的啦。 全程摸鱼警告 10:55 的时候就开始新建文件夹了，58 分的时候发现没登录，赶紧登录了一波。 11:00 准时开题，发现这题面怎么都巨大长啊，看到了叫做 “THUPC” （后来改成 “画图” 了）的题目，感觉可能是签到题，点进去看了一眼，发现是个毒瘤模拟，让你判断输入的线段是否构成 THUPC 字样，果断放弃。 这时机房里几个 dalao 已经开始切 K 了，是模拟题，输入一个字符矩阵让你求正方体个数头顶标数法应用，感觉也是非常的毒瘤。 开考 6 分钟的时候首 A 诞生了，切的是 A 题，于是滚去看 A。听到旁边 qq 已经搜到 A...

# Description Luogu 传送门 # Solution （感谢 @Acestar 提供的思路） 初始情况下，每头奶牛匹配一个礼物，所以我们把奶牛和礼物当作一个点。 如果奶牛 iii 非常不要脸的去抢奶牛 jjj 的礼物（iii 向 jjj 连单向边），而且不幸的是奶牛 jjj 还打不过奶牛 iii，那么 jjj 就被迫去抢别人的礼物 qwq，所以 jjj 就必须向它能抢到的别的奶牛连边。 因此我们这个图就建出来了，找一组解只需要跑一遍传递闭包即可，顺便拿个 bitset\text{bitset}bitset 优化一下，时间复杂度 O(n3ω)O(\frac...

# Description Luogu 传送门 # Solution 斜率优化 dp 非常好的一道斜率优化，完全理解题目都用了好长时间 QwQ 其实如果你已经完全理解了这道题也不是特别难了。 我们可以选两个下标，然后把经过这两个下标的线全部删掉。 不难发现，交叉的线是没有用的，所以对于上方的一个点，我们只保留它与下方连边中最右边的点即可。 然后这张图就变成了好多不相交的线，这样就可以列出朴素 dp\text{dp}dp 了。 设 fif_ifi​ 表示把前 iii 条弦全部切掉的最小花费，那么有转移方程： fi=min⁡(fj+minlu[j+1]−1×minrv[i]+1)f_i =...