A，B，C组各$n$个人，一个队伍要选$3$个学生$a,b,c$（每组一个），每个人有一个点权$v_i$，一个队伍的权值为 $f(a, b)+f(a, c)$。一共要选$m$队，问权值和最大为多少。数据范围 $m\leq n\leq 200, T\leq 10$

$$f(i, j) = (v_i+v_j)*(v_i\oplus v_j) \% MOD$$

转化为最小费用最大流模型，用最大流对应最多选m队的条件，将边权置为负值，即可将求最大权值转化为最小权值。

建边方法如下：

• 将源点$S$拆成两个点$S$和$S’$，建边$S\rightarrow S’$，容量$m$，费用0
• 对每个$b_i$建边$S’\rightarrow b_i$，容量1，费用0
• 对每个$(b_i, a_j)$，建边$b_i\rightarrow a_j$，容量1，费用$f(b_i,a_j)$
• 将每个$a_i$拆成两个点$a_i$和$a_i’$，建边$a_i\rightarrow a_i’$，容量1，费用0，这一步是为了避免一个$a_i$被多个队伍复用
• 对每个$(a_i’,c_j)$，建边$a_i’\rightarrow c_j$，容量1，费用$f(a_i’,c_j)$

关于负边：

• 注意Dijkstra无法处理负边，应使用SPFA的费用流
• 本题中，答案边数是固定的，因此也可以将所有负边加上一个固定值变为正权边，然后用Dijkstra费用流

用$f(x)$表示$x$的所有后缀类乘后对$x+1$取模的结果，如$f(1023)=(3\times 23\times 23\times 1023)\%1024$

用$g(n,m)$表示对$n$做$m$次$n=f(n)$

求$\sum\limits_{i=1}^m g(n, i)$，数据范围 $1\leq n,m\leq 10^9,T\leq 20$

瞎几把手玩了几组数据，感觉 $n$ 实际做不了几次$n=f(n)$ 就会死循环 $n=f(n)$，跟榜直接冲了发暴力就过了

但是这个收敛的次数实在不会证

给一张 $N\times N$ 的完全图，每条边权值相等，再给一个 $N\times N$ 的矩阵 $a$，要求选取几条边，将其余边都删除后，使得对所有 $(i,j)$ ，最短路 $dis_{i,j}=a_{i,j}$ ，问最少选几条边，保证给出的矩阵 $a$ 合法。（即一定存在选边方案）

多组数据，数据范围 $N\leq 10^3, \sum N\leq 5\times 10^3$

由于所有边等长，矩阵 $a$ 又一定合法，因此对于 $a_{i,j}=min(a_{i,j})$ 的 $(i,j)$，一定有直连边，选择这些边即可

坑点是题目只说所有边等长，但没有说边权是多少，一开始默认边权为1，wa了不少发

给一张 $N\times M$ 的格点图，每次移动可以从 $(i,j)$ 移动到 $(i+1,j),(i,j+1),(i+1,j+1)$，要求从$(1,1)$出发走到$(n,m)$，每个点有权值 $a_{i,j}$，走到$(i,j)$可以获取$a_{i,j}$的能量，若$a_{i,j}\leq 0$，表示本格子有毒，需要屏气通过，可以一次性花费 $U$ 的能量开启屏气状态，屏气状态持续$K$步，可以主动取消。

这里题意有点歧义，实际上屏气状态需要在进入毒气区前开启，并在离开毒气区后解除，即如果$K=1$，是无法通过任何毒气区的。

求走到$(n,m)$时，身上最多有多少能量

多组数据，数据范围 $N,M\le 10^3, 1\le K,U\le 10^9,\sum {N\times M}\le 7\times 10^6$

考虑DP，$f_{i,j}$ 表示走到 $(i,j)$ 时最多有多少能量，两种转移：

• 不考虑屏气，则有如下转移式

$$f_{i,j}= \begin{cases} f_{i,j-1} + a_{i,j}& a_{i,j-1}>0 \\ f_{i-1,j} + a_{i,j}& a_{i-1,j}>0 \\ f_{i-1,j-1} + a_{i,j}& a_{i-1,j-1}>0 \\ \end{cases}$$

• 考虑屏气，则有如下转移式

$$f_{i,j}=max(f_{x,y})-U+a_{i,j} \ \ (i-k\le x\le i,j-k\le y\le j)$$

第一种转移比较简单，主要讲第二种转移。

该转移相当于从 $(i,j)$ 的左上角矩阵中取一个最大值，由于转移是从左到右，从上到下进行的，可以对每一列维护一个单调队列，这样就可以在dp到第$i$行时，对每个 $j$ 维护 $max(f_{x,j})(i-k\le x\le i)$。

然后从这一行上的每个单调队列中取出最大值，再做一遍单调队列，就可以得到这个矩阵中的最大值了。

相当于先对每列求最大值，再从中求矩阵的最大值。

复杂度$O(N\times M)$