2020 东北省赛


还有个A可能能补

A Micro Structure Thread

// 未补

B Team

题意

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$

Solution

转化为最小费用最大流模型,用最大流对应最多选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费用流

C Function

题意

用$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$

Solution

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

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

D Fall Guys

// TODO

E Liner vectors

// TODO

F Splendor

// 未补

G Halli Galli

// TODO

H PepperLa’s String

// TODO

I PepperLa’s Cram School

题意

给一张 $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$

Solution

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

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

J Color the blocks

签到,懒得写了,略

K PeperLa’s Boast

题意

给一张 $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$

Solution

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

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

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

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

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

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

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

L PeperLa’s Express

不想写了啊啊啊啊啊

出题人题解

Hile_Meow题解