E

由于 nanjing 并没有非平凡 Border，所以它们不会重叠出现。

那么只需要枚举分界点，并且预处理出前后缀中 nanjing 的出现次数，并且暴力统计分界处的 nanjing 出现次数即可。

设 m=7m=7 为 nanjing 字符串的长度，直接朴素 O(nm2)O(nm^2) 实现即可。

J

我们需要枚举两个人，但是不能 O(n2)O(n^2) 的枚举两个人。

先枚举一个 xx，那么 yy 分两种情况：

  1. 若 yy 回复过 xx，我们从 xx 的回复列表中枚举 xx。
  2. 若 yy 没有回复过 xx，xx 也没有回复过 yy，那么这两个人是相互独立的，我们只需要取一个最大次大值即可。
  3. 若 yy 没有回复过 xx，但是 xx 回复过 yy，那么当我们枚举到 x′=yx'=y 的时候会枚举到 y′=xy'=x，所以并不会漏掉这种情况。

除此之外，如果我们将 x,yx,y 视为相互独立的，但是 x,yx,y 实际上不是，当枚举到 x,yx,y 的回复关系时，算出来的值一定比视作相互独立的值更大，所以会把这种非法答案覆盖掉，不会导致最终的答案有问题。

将 n,m,kn,m,k 视作同阶，并且使用 map 维护相互贡献，这样枚举的复杂度 O(nlog⁡n)O(n\log n)。

K

每两个黑块间是独立的，那么我们只需要考虑解决用长度为 kk 的纸条覆盖若干个点，并且具有左右边界这一子问题。

如果没有边界的限制，交换论证法易证每次将纸条的左端点覆盖最左边没有覆盖掉的点，这样使用的纸条数量是最小的。

如果存在边界的限制，那么我们只需要把最右边的纸条往左边挤即可。如果最终左边越界了，说明 ck>lck>l，其中 ll 为当前左右边界确定的区间长度，cc 为最小的纸条数量。

既然最小的纸条数量的长度之和都大于当前的区间长度，那么一定无法覆盖掉这些点， 否则直观上容易知道向右挤的过程一定也会覆盖所有点，并且左边不会越界。

复杂度 O(n+mlog⁡n)O(n+m\log n)，主要在于二分。

G

既然是树上需要在 ⌊log⁡2n⌋\lfloor \log_2 n\rfloor 次解决的问题，考虑点分治。

设当前剩余的节点数量为 mm，每次对剩余节点构成的树找到它的的重心 cc，并且以它为根。

根据重心性质，每一个儿子的大小都 ≤⌊m/2⌋\le \lfloor m/2\rfloor，考虑 cc 有几个儿子。

  1. 若 m=1m=1，我们直接输出这是答案；若 m=2m=2，我们通过一次询问判断答案，否则 cc 不可能只有一个儿子。

  2. 若 cc 有 22 个儿子 a,ba,b，则询问 a,ba,b。容易看出，无论结果如何，剩余的有效点都 ≤⌊m/2⌋\le \lfloor m/2\rfloor。

  3. 若 cc 有 33 个儿子 a,b,ca,b,c，不妨设 sa≤sb≤scs_a\le s_b\le s_c，其中 sus_u 表示 uu 子树的大小，那么 sa≤⌊(m−1)/3⌋s_a\le \lfloor(m-1)/3\rfloor。询问 b,cb,c，讨论三种情况：

    • 若询问结果为 00，则答案只在 bb 子树中，剩余有效点 ≤⌊m/2⌋\le \lfloor m/2\rfloor；
    • 若询问结果为 22，则答案只在 cc 子树中，剩余有效点 ≤⌊m/2⌋\le \lfloor m/2\rfloor；
    • 若询问结果为 11，则答案不在 b,cb,c 子树中，剩余有效点 =sa+1≤⌊(m+2)/3⌋=s_a+1\le \lfloor (m+2)/3\rfloor；

    此时我们只需要证明，对于 m>2m>2，都有 ⌊(m+2)/3⌋≤⌊m/2⌋\lfloor(m+2)/3\rfloor\le \lfloor m/2\rfloor 即可。显然 mm 充分大时此式一定成立，本地暴力验证一下 mm 较小时也成立。

因此无论如何我们一次询问可以将有效点数由 mm 下降到至多 ⌊m/2⌋\lfloor m/2\rfloor，带入初始 m=nm=n，只需要 ⌊log⁡2n⌋\lfloor\log_2 n\rfloor 次询问。

每次暴力找重心即可，其实按照这样的分析，复杂度为 O(n+⌊n/2⌋+⌊n/4⌋+⋯ )=O(n)O(n+\lfloor n/2\rfloor+\lfloor n/4\rfloor + \cdots)=O(n)，并且询问次数严格满足要求。

B

不考虑 22 时，考虑将两种操作统一。

只要将偶数位置取反，就可以将两种操作统一为删除相邻的 0101。

并且删完之后后面接过来的每个位置奇偶性不变。

对于处理之后的 0101 串，答案显然为 ∣c0−c1∣|c_0-c_1|。于是我们只需要把 22 转为 arg⁡min⁡(c0,c1)\arg\min(c_0,c_1) 即可。

复杂度 O(n)O(n)。

M

能攻击到凸多边形的左右边界构成的角度一定不超过 π\pi，否则凸多边形与中心以 dd 为半径的圆相交。

那么我们枚举凸多边形上每一个点做圆的切线：

  • 当凸多边形全在左侧，并且圆在右侧时，这是一个入边界的候选；
  • 当凸多边形全在右侧，并且圆在左侧时，这是一个出边界的候选。

由于 nn 很小，我们可以每次 O(n)O(n) 判断凸多边形是否全都在当前直线左侧或者右侧。

由于一开始的分析，只需要叉积得到入边界和出边界，并且最终和若干个整 2π2\pi 角度区间与最后剩下的 <2π<2\pi 的一个角度区间求交即可。

复杂度 O(n2)O(n^2)。

I

设 pp 为 1∼nm1\sim nm 的一个排列，SpS_p 为 ap1,ap2,…,apnma_{p_1},a_{p_2},\dots,a_{p_{nm}} 这个 Bingo 的每一行元素的最大值与每一列元素的最大值构成的多重集。

min⁡\min 套在 max⁡\max 外面是不好做的，于是考虑 min⁡−max⁡\min-\max 反演：

∑pmin⁡Sp=∑p∑∅≠T⊆Sp(−1)∣T∣−1max⁡T=∑i=0n∑j=0m[i2+j2≠0](ni)(mj)(−1)i+j−1∑p∑Tmax⁡T\begin{aligned} \sum_p \min S_p&=\sum_p\sum_{\varnothing\neq T\subseteq S_p}(-1)^{|T|-1} \max T\\ &=\sum_{i=0}^n\sum_{j=0}^m[i^2+j^2\neq 0]\binom{n}{i}\binom{m}{j}(-1)^{i+j-1} \sum_p\sum_T\max T \end{aligned}

这里 i2+j2≠0i^2+j^2\ne 0 只是说明这两个指标不同时为 00，后面我们枚举 TT 的行数和列数为 i,ji,j，那么易得 TT 一共占据了 C=im+jn−ijC=im+jn-ij 个位置。

我们考虑将 aa 升序排序，枚举 max⁡T=ak\max T=a_k：

∑p∑Tmax⁡T=∑k=Cnmak∑T∑p[max⁡T=ak]=∑k=Cnmak(k−1C−1)C!(nm−C)!=(nm−C)!C∑k=Cnmak(k−1)!(k−C)!\begin{aligned} \sum_p\sum_T\max T&=\sum_{k=C}^{nm} a_k\sum_T\sum_p[\max T=a_k]\\ &=\sum_{k=C}^{nm} a_k\binom{k-1}{C-1} C!(nm-C)!\\ &=(nm-C)!C\sum_{k=C}^{nm} a_k\frac{(k-1)!}{(k-C)!} \end{aligned}

令 Fk=ak(k−1)!F_k=a_k(k-1)!，Gk=1(nm−k)!G_k=\cfrac{1}{(nm-k)!}，只需要求出 HH 为 F,GF,G 的卷积，那么 Hnm+CH_{nm+C} 就是 ∑i=Cnmai(i−1)!(i−C)!\sum_{i=C}^{nm} a_i\cfrac{(i-1)!}{(i-C)!}，注意在 11 到 nmnm 之外的下标 F,GF,G 的值均为 00。

复杂度 O(nmlog⁡(nm))O(nm\log (nm))。

C

如果我们枚举一个 uu，并且从根开始往下做 DP 的话，无论如何也只能得到一个 O(n)×O(n2)O(n)\times O(n^2) 的做 nn 次树上背包类似物。

主要原因是，这种做法相当于对每一种 uu 都独立求解了一个问题，这显然是不太对的。

考虑怎么让 uu 参与进状态转移，考虑设计状态 dpu,idp_{u,i} 表示 uu 最终在位置 ii 的方案数。

但是这样设计状态又会导致 uu 依赖它的子节点，反过来子节点又依赖 uu。为了避免这个问题，将 dpu,idp_{u,i} 的含义转为删掉 uu 的所有后代（不包括 uu 本身）后，最终在位置 ii 的方案数。

考虑转移，设 ff 为 uu 的父亲，sus_u 为 uu 的子树大小，考虑枚举 ff 在 n−sf+1n-s_f+1 个元素的拓扑序中的位置 kk。

一旦确定了 ff 的位置，我们还需要将 ff 除了 uu 以外的所有子树插入到这个拓扑序中。

最后 uu 放到 kk 之后的哪个位置都唯一对应着不放 uu 的一个方案。

首先给 sf−su−1s_f-s_u-1 个节点分配位置。相当于求解 n−sf+1−k+1n-s_f+1-k+1 个未知数之和为 sf−su−1s_f-s_u-1 的非负整数解的个数，直接套公式即可。

dpu,j=∑k=1j−1dpf,k×(n−su−ksf−su−1)×Cf,udp_{u,j}=\sum_{k=1}^{j-1} dp_{f,k}\times \binom{n-s_u-k}{s_f-s_u-1}\times C_{f,u}

这个和式中的变量和 jj 没有任何关系，因此直接前缀和 O(1)O(1) 转移即可。

其中 Cf,uC_{f,u} 可以预处理。具体地讲，我们先对每一个节点 DP 求出没有限制的拓扑序数量 tut_u，那么我们在分配完位置之后，就有：

Cf,u=(sf−su−1)!∏u≠v∈sonftvsv!C_{f,u}=(s_f-s_u-1)!\prod_{u\neq v\in son_f} \frac{t_v}{s_v!}

这个系数可以直接类似换根 DP 时从 ff 传下来即可。

复杂度 O(n2)O(n^2)。

F

定义状态 (l,s)(l,s) 表示线路 ll 的 ss 站，只需要求出这 ∑(pi−1)\sum(p_i-1) 个状态的多源最短路即可。

对于一个站，可能有多条线路换乘，这些换乘之间构成了一个完全图，所以我们不能每次暴力松弛所有邻边。

考虑模拟 Dijkstra 算法，我们需要的是，对于全集 UU，维护已求出最短路的集合 SS，并且用 SS 中的所有节点对 U∖SU\setminus S 的节点进行松弛之后，找到一个 u∈U∖Su\in U\setminus S 并且 dud_u 最小的节点，将 S←S+{u}S\gets S+\{u\}。

假设当前状态为 (l0,s)(l_0,s)，并且有 (l1,s),(l2,s),…,(lm,s)(l_1,s),(l_2,s),\dots,(l_m,s) 个换乘边。

对于线路 l0l_0 上的 ss 的下一站（如果有下一站），我们可以直接松弛，但是对这些换乘边我们不能每次暴力松弛。

观察我们的操作相当于给 dli,s←min⁡(dli,s,bl0×ali+dl0,s)d_{l_i,s}\gets \min(d_{l_i,s},b_{l_0}\times a_{l_i}+d_{l_0,s})，这可以上李超树维护。

然而难点并不是李超树，而是如何用一个正确的复杂度来模拟 Dijkstra。

由于所有的 bib_i 都是正整数，所以这是一个下凸包，而下凸包的函数图像是单调递增的。

所以对于这些换乘，最小值只有可能在最小的 alia_{l_i} 处取到，当然这里要满足 (li,s)∈U∖S(l_i,s)\in U\setminus S。

因此我们只需要松弛这一个 (li,s)(l_i,s)，就可以保证下一次找到的 u∈U∖Su\in U\setminus S 是正确的。

所以我们只需要对于每一个 ss 维护动态开点李超树，并且每次至多对经过 ss 的一个 lil_i 进行松弛操作，但是可能会删掉若干个已经存在于 SS 的 (lj,s)(l_j,s)。然而每一个元素只会被删除一次，因此复杂度还是对的。

将 n,k,∑pin,k,\sum p_i 视为同阶，复杂度 O(nlog⁡n+nlog⁡V)O(n\log n+n\log V)，其中 VV 是 aa 的值域，这部分复杂度由李超树贡献。