Gym-102465k Dishonest Driver 给出一个字符串，两个相邻且相同子串可以进行压缩，问压缩后字符串最少有多少字符，n≤700n \le 700n≤700。 将两个相邻区间合并，且 nnn 很小，就很像是区间 DP。 定义 dpi,jdp_{i, j}dpi,j​ 表示 [i,j][i, j][i,j] 的压缩后最少字符数。 显然有两种合并，直接拼起来相加，或者将右区...

邮局 加强版 加强加强版 普通版 dpi,k=min⁡j=0i−1dpj,k−1+w(j+1,i)dp_{i, k} = \min_{j=0}^{i-1}dp_{j, k - 1} + w(j + 1, i)dpi,k​=minj=0i−1​dpj,k−1​+w(j+1,i) 其中 dpi,kdp_{i, k}dpi,k​ 表示前 iii 个放 kkk 个邮局的最小代价，w(l,r)w(l...

luogu 阅读链接。 题目链接。 题目的边用的是倍数关系（偏序）。 当 x→y,y→zx \rarr y, y \rarr zx→y,y→z，就必然有 x→zx \rarr zx→z。 为了避免这种情况，意味着每个点要么只有因数，要么只有倍数。 我们将每个点拆成两个点，x0x_0x0​ 表示图中 xxx 只能保留其的因数，x1x_1x1​ 表示其倍数。 再用一条边 (x,y)(x, y)(...

题目链接：HDU5828 rikka with sequece 简要题面：实现 333 中操作：区间开根，区间加，区间求和。 如果直接暴力递归，区间加操作会破坏复杂度，例如交替的 2,32, 32,3 序列，我们反复做全局 +6+6+6，再开根，单次复杂度就变成 O(n)O(n)O(n) 了。 所以我们不能完全暴力，要单独维护一下懒标记。 注意到，有很多数开根后答案相同，比如 161616 ...

luogu 阅读链接。 前言 麻将模拟器 调了一早上结果发现 DP 中的 jjj 写成 iii 了。 题目中的和牌距离基本和向听数差不多。 文中的面子指刻子和顺子的统称。 基础操作 定义 #define endl '\n' #define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a+...

luogu 阅读链接。 灭鼠行动。 前言 其实有很多地方出题人没讲清楚，所以只保证代码可以通过本题数据。 细节 神秘射线是停止一切生理活动（包括成长），会暂停，但不会打断繁殖。 繁殖后要动一下（包括旋转），才能继续繁殖。 顺序：武器 -> 繁殖 -> 移动。 注意老鼠刚出生时的年龄。 注意时间单位和时刻的区别。 繁殖是某点恰好有两只异性老鼠。 岔路的拐弯与当前这只老鼠面对岔...

luogu 阅读链接。 题目链接 我们先看一道弱化版：P1972。 在 P1972 中，我们将询问离线，每个颜色当前的最后一位才有贡献。 在这道题，我们每个颜色有了不同的贡献，从保留一位变成保留 kkk 个。 我们先对当前位置单点加。 如果超出 kkk 个，就把最前面的数减去。 答案就是当前的区间和。 用树状数组做单点修改、区间查询，用 vector 访问前面的数。 123456789101...

luogu 阅读链接。 题目链接 我们先把环断成链。 转换题意：fi,j=fi−1,j−1⨁fi−1,j+1f_{i, j} = f_{i - 1, j - 1} \bigoplus f_{i - 1, j + 1}fi,j​=fi−1,j−1​⨁fi−1,j+1​。 其中第一维是操作次数，⨁\bigoplus⨁ 是异或。 由于 TTT 很大，而且大概率是不会有循环的。 那么我们先画图： ...

luogu 阅读链接。 题意 题目链接 有两行，一行 nnn 个点，和 mmm 条线（从第一行的节点连向第二行的节点）。 现在问你最多留下多少线，能使任意两条线均不相交。 思路 为了方便描述，第 aaa 条线的第一行节点是 axa_xax​，第二行节点是 aya_yay​。 显然，两条相交的线 a,ba, ba,b 必然满足，ax<bx∧ay>bya_x < b_x \...