9.28

标签：赛时最大值 9.28 补图贪心 dp equiv

突然发现自己之前一场 ARC ，评分分别为 1110 和 1049 的 A 和 B ，赛时一点思路没有。
然后打开了几道 AGC 评分 2000 左右的 A 和 B，结果发现自己连 1701 的 A 题都觉得很困难。
然后为今晚打 ABC 光荣 rk1468 埋下伏笔。

我承认 \(99\%\) 都是看的题解。

agc066_a

给网格进行黑白染色，让其中一种点 \(\mod2d\equiv d\) 另一种 \(\mod2d\equiv0\) ，或者反过来，因为这两种方案代价总和为 \(dn^2\) ，所以一定有一种方式代价 \(\le\frac{1}{2}dn^2\)

agc067_a

我觉得这个挺难的啊，在补图上团就是独立集了，然后问题就变成补图任意导出子图都存在点数不少于一半的独立集，发现不合法的情况当且仅当补图存在奇环，也就是说如果补图是二分图，那么就一定合法，然后用并查集判断一下是不是二分图就好，补图边数 \(\frac{n(n-1)}{2}-m\) 如果 \(>\frac{n^2}{4}\) 那么就不合法了，然后这么先判一下，这样复杂度就保证了。

原式可变为 \(a_n-a_1+pk\)，其中 \(p\) 是满足 \(a_i > a_{i+1}(1 \le i \le n-1)\) 的下标 \(i\) 数量。显然若 \(c\) 是 \(p\) 能取到的最大值，只有 \(p \ge c-1\) 时才能产生最优解，像我只能想到倒序排序，然后发现如果有相同的数不一定行，于是找出出现次数最多的数，设出现次数为 \(m\)，分别考虑分成 \(m\) 组和 \(m-1\) 组。
\(m\) 组的贡献是确定的，即出现了 \(m\) 次里的数字的最小值 \(x_1\)，减去出现了 \(m\) 次里的数字的最大值 \(x_2\)，此时答案即是 \(ck + x_1 - x_2\)
\(m+1\) 组贪心的把出现次数小于 \(m\) 的都放在中间，剩下的考虑扔到最左边还是最右边，我们贪心的想右边最小值减左边最大值最大，所以我们可以定一个阈值 \(x\)，大于 \(x\) 的不放在第一组，小于等于 \(x\) 的不放在最后一组。那么，此时的答案是出现 \(m\) 次且大于 \(x\) 的最小值减去出现 \(m\) 次且小于等于 \(x\) 的最大值。排序出现 \(m\) 次里的数字，枚举相邻项的差即可。设差是 \(d\)，答案是 \(d + (c-1)k\)

agc065_b

正着想很难想，同时我们发现操作是可逆的，于是我们可以对 \(P\) 操作，每次从 \(P\) 中删去 \(i\) 再插入 \(i\) ，\(i\) 依次从 \(n\) 到 \(1\) ，考虑操作 \(i\) 时，\(i+1\) 为 \([i+1,n]\) 中位置最小的，而 \([1,i]\) 还没动过，所以可以根据 \(i+1\) 的位置浅判一下 \(i\) 当前在 \(i+1\) 的左侧还是右侧。
设 \(dp_{i,j}\) 为 \(i\) 插入到位置 \(j\) 的方案数，这次转移若 \(i\) 在 \(i+1\) 左侧，则可转移到 \([1,j-1]\) ，否则可转移到 \([1,j]\) ,维护差分数组最后前缀和就好。