输了。

A

如果 r>min⁡(x,y)−1r>\min(x,y)-1，总能通过再添加一个 min⁡(x,y)\min(x,y) 使 rr 变得更小。直接输出 n=min⁡(x,y)−1n=\min(x,y)-1 即可。

B

令 x≤yx\leq y。若 z=y+1z=y+1，可以构造 x=10x−1,y=10y−1x=10^x-1,y=10^y-1，若 z=yz=y，可以构造 x=10x−1,y=10y−1x=10^{x-1},y=10^{y-1}。其余情况无解。

C

前缀和，模拟即可。也可以做到线性。

D

横着移动其实就是在求 min⁡j=1n{∣axi−bj∣}\min\limits_{j=1}^n\{|a_{x_i}-b_j|\}，用 set 查一下每个 aa 在 bb 里的前驱后继即可。因为还要处理竖着移的情况，一种简单的实现方式是交换所有 x,yx,y 和 a,ba,b 然后再做一遍前面的事情。

E

令 fi,0/1f_{i,0/1} 代表走到点 ii，还未经过 / 已经经过商店的最短路。bfs 后枚举终点的 fi,1f_{i,1}，然后再判一下有没有边可以形成环即可。需要特判一下起点是不是商店。

F

从这里开始应该就不算签到题了。

考虑产生最大贡献的条件：第一步肯定是将 aa 划分成一些内部相邻差为 11 的连续段，不同的段之间不会产生贡献，是独立的。观察到一个段内，奇数分在同一组，偶数分在同一组贡献最大，如果段长 ll 为奇数，每个偶数都可以产生 22 的贡献；否则除了最后一个偶数产生 11 的贡献，其余都产生 22 的贡献。于是可以求出第一问的答案。

第二问依旧分别考虑每段的奇偶性：

  • 如果段长为偶数，将偶数分配到红组，奇数分配到蓝组和反过来分配对答案是没有影响的，直接将答案乘 22 即可。

  • 如果段长为奇数，将奇数分配到某一组，那一组会多出 11，对后面的决策有后效性。考虑两组人数相等的充要条件：红组人数与蓝组人数的差为 00。如果将奇数分配到红组会对这个差 +1+1，否则 −1-1。令段长为奇数的段数为 kk，可以转化成有 kk 个值为 −1-1 或者 11 的变量，统计赋值后和为 00 的方案数。于是这部分的贡献就是 (kk2)\binom{k}{\frac{k}{2}}。

G

我觉得这个题明明超级难啊，怎么过的比 H 和 I 还多这么多？？？

考虑什么样的逆序对会产生贡献：因为只能删 kk 个元素，考虑对每个 ii 记下包含 ii 的逆序对中前 k+1k+1 大的，这样其中至少有一个会对最后的答案产生贡献。

现在我们有了 O(nk)\mathcal{O}(nk) 个可能成为答案的逆序对。将它们按差值从大到小排序。对于每个时刻还存在的差值最大的那个逆序对 (i,j)(i,j)，ii 和 jj 其中肯定有一个要被删掉，但我们不知道是哪一个。因为 kk 很小，可以直接爆搜每次是删掉 ii 还是删掉 jj，然后往后遍历找出第一个无法删除的。容易证明这种策略一定能枚举到一个最优的答案。这样做的复杂度是 O(2kkn)\mathcal{O}(2^kkn)，可以通过。

H

赛时读错题了，还以为可以向上走。。。

官方题解是，直接把不可达的格子跟 (1,1)(1,1) 距离为偶数的可达格子填上 −1-1，剩下填 +1+1，然后 dp 一遍 check 合不合法即可。其实这个构造确实比较自然，但如果我想不到该咋办？

考虑对于可达的格子，限制实际上是比不可达的格子要松的，尝试让可达的格子的最大的路径和尽量小。手玩发现最优方案里上下两个可达格子的最大路径和之差只会是 11，>1>1 时不优且不可能 =0=0，所以可以 dp 上下两个格子最大路径和的最小值。

I

排序方式其实无关紧要，(s,k,x)(s,k,x) 不合法的充要条件是 k≤s∧(ak−1>s∨ak+1<s)k\leq s\land (a_{k-1}>s\lor a_{k+1}<s)。枚举 ss，每一个 k≤sk\leq s 产生的贡献只与它在前 ss 个元素中的前驱和后继有关，扫描线，用 set 维护前驱和后继即可。

J

题意是问至少加几条边能使这个无向图存在一种定向方式，使得定向后强连通，且每次加边只能对两个距离 ≤2\leq 2 的点加边。其实合法的条件就是没有割边，操作的目标是把割边都删掉。

首先忽略掉所有非割边，最后剩下的是割边组成的森林。显然一次不可能删掉不在一个连通块里的两条割边或者同一个连通块里的三条割边，这种情况两个端点的距离一定 >2>2。对于每棵树分别处理。一次操作删掉一条割边是容易的，直接再加一条一模一样的边即可，我们想让尽量多的操作一次能删掉两条割边。考虑操作次数的下界：⌈s2⌉\lceil\frac{s}{2}\rceil，其中 ss 是一棵树中边的个数。采用如下策略便能取到下界：对于一棵边数 ≥2\geq 2 的树，

  • 如果它深度最大的叶子深度 ≥2\geq 2，且这个叶子没有兄弟，删掉它上方的两条边；
  • 否则删掉两个相邻的叶子及其连向根的边即可。

这样删边可以保证每次删完，剩下的边仍然是连通的。因此这是一个合法的操作策略。

K

L