A

100%

每坚持一年，身高增加 $0.4=\frac{2}{5}$ 厘米。

设需要坚持 $t$ 年，则需要满足：

$$x+\frac{2}{5}t \ge y$$

等价于：

$$2t \ge 5(y-x)$$

因此答案为：

$$t=\left\lceil \frac{5(y-x)}{2} \right\rceil$$

整数实现时可以写成：

$$t=\frac{5(y-x)+1}{2}$$

其中除法为整除。

时间复杂度 $O(1)$。

B

100%

要求找到满足：

$$\frac{a_1+a_2+\cdots+a_y}{y}\ge x$$

的整数 $y$ 的最小值和最大值。

令前缀和为：

$$s_y=a_1+a_2+\cdots+a_y$$

条件等价于：

$$s_y\ge xy$$

由于 $1\le n\le 100$，直接枚举 $y=1\sim n$ 后计算是否满足题目条件即可。

时间复杂度：$O(n)$。

C

100%

一次操作会把 $a_x$ 的值合并到右侧 $a_{x+1}$，并把 $a_x$ 置为 $0$：

$$a_{x+1}:=a_{x+1}+a_x,\quad a_x:=0$$

如果想把连续区间 $[l,r]$ 的和集中到位置 $r$，可以依次操作：

$$l,l+1,\dots,r-1$$

共需要 $r-l$ 次操作。

因此，在最多 $m$ 次操作内，可以把任意长度不超过 $m+1$ 的连续子段和集中到它的右端点。

直接枚举所有区间 $[l,r]$，若 $r-l\le m$， 则用该区间和更新答案。但是如果所有数字均为负，需要特别判断。

同时要注意：

• 可以不进行操作，所以答案至少是原数组最大值；
• 若 $n\ge 2$ 且 $m\ge 1$，可以进行一次操作产生一个 $0$，因此答案还可以和 $0$ 取最大；
• 若 $n=1$，不存在合法操作，答案只能是 $a_1$。

时间复杂度：$O(n^2)$。 空间复杂度：$O(n)$。

D

100%

考虑二分答案，考虑如果当前天数是 $mid$ 时，是否能吃完所有的药。

我们先考虑把 $mid$ 按照 $u$ 分割成若干段：每 $u$ 天的前 $v$ 天两种都吃，后 $u - v$ 天只吃一种，这样就能算出吃两种的天数和吃一种的天数。即：

• 两种都能吃的天数为 $\lfloor \frac{mid}{u} \rfloor \times v +\min{( mid \bmod u , v)}$
• 只吃一种的天数为 $mid -$ 两种都能吃的天数

这样优先考虑把两种都吃的天数消耗掉，再检查剩下的药的数量能否在只吃一种的天数内完成即可。

时间复杂度 $O(\log (x + y))$。

E

100%

任意时刻，当前折痕序列一定是原序列的某个区间，或者该区间整体取反。

由于合法折叠条件只判断两侧是否不同，即 $b_{x-i}\ne b_{x+i}$，如果整个序列同时取反，该条件不变。因此 DP 时不需要记录“是否取反”，只需要记录当前剩余的是原序列中的哪个区间。

定义：$dp[l][r]$ 表示将原序列区间 $[l,r]$ 对应的纸条折叠为空所需的最少操作次数。

对于非空区间 $[l,r]$，枚举本次折叠的折痕位置 $k$，其中 $l\le k\le r$。

• 左侧长度为：$L=k-l$

• 右侧长度为：$R=r-k$

折叠合法当且仅当：

$$a_{k-d}\ne a_{k+d},\quad 1\le d\le \min(L,R)$$

只需要枚举折叠位置后暴力判断该位置是否合法即可。

若合法，则根据题意分两种情况转移。

如果左侧不长于右侧，即$k-l\le r-k$，折叠后保留右侧区间 $[k+1,r]$，于是：

$$dp[l][r]=\min(dp[l][r],1+dp[k+1][r])$$

否则保留左侧区间 $[l,k-1]$。虽然题面中此时折痕方向会整体取反，但整体取反不影响后续合法性判断，所以仍然可以转移为：

$$dp[l][r]=\min(dp[l][r],1+dp[l][k-1])$$

按照区间长度从小到大计算 DP。最终答案为 $dp[1][n]$，初始状态为 $dp[i][i] = 1$。

时间复杂度：$O(n^4)$。

F

100%

根据题意，我们可以这样考虑：可以先固定一条从 $1$ 到 $n$ 的路径，再考虑这条路径上的最优染色。

对于固定路径 $P$，路径权值为：

$$\sum_{e\in P}w_e-\max_{e\in P\cap R}r_e-\max_{e\in P\cap B}b_e $$

要使权值尽量小，就要让：

$$\max_{e\in P\cap R}r_e+\max_{e\in P\cap B}b_e$$

尽量大。

我们可以转换这个 $\max$ 的限制。如果 $R,B$ 已经固定好，也就是选择一个 $R$ 内的边来扣除和选择一个 $B$ 内的边来扣除。显然转换之后，我们肯定还是取 $R$ 内的最大值和 $B$ 内的最大值来进行扣除。

具体来说，这可以理解为在路径上使用两张“优惠券”：

• 红色优惠券：选择一条边 $e$，使该边贡献 $r_e$ 的扣减；
• 蓝色优惠券：选择一条边 $e$，使该边贡献 $b_e$ 的扣减；
• 同一条边不能同时使用红、蓝两张优惠券；
• 两种优惠券都可以不用。

可以发现，上述转换后的最优方案肯定是原问题的方案。

为了解决上述已经转换的问题，建立分层图，状态为：$(u,mask)$，其中 $u$ 是当前点，$mask$ 表示已经使用过哪些优惠券：

• $0$：红、蓝优惠券都未使用；
• $1$：红色优惠券已使用；
• $2$：蓝色优惠券已使用；
• $3$：红、蓝优惠券都已使用。

对于原图中的每条边 $u\to v$，边权属性为 $w,r,b$。

在分层图中进行如下转移。

1. 不使用优惠券：$(u,mask)\to(v,mask)$，代价为：$w$。

2. 如果红色优惠券尚未使用，即 $(mask\&1)=0$，可以使用红色优惠券：$(u,mask)\to(v,mask\mid 1)$，代价为：$w-r$。

3. 如果蓝色优惠券尚未使用，即 $(mask\&2)=0$，可以使用蓝色优惠券：$(u,mask)\to(v,mask\mid 2)$，代价为：$w-b$。

注意不能在同一条边上同时使用红、蓝优惠券，因此没有直接使用两张优惠券的单边转移。

由于题目保证了$w_i\ge \max(r_i,b_i)$，故 $w_i-r_i\ge 0,\quad w_i-b_i\ge 0$ ，分层图中所有边权非负，可以使用 Dijkstra。

最终答案为：$\min_{mask=0}^{3}dist[n][mask]$。

还有一个问题：为什么最短路中允许走出的环不会影响答案？

因为所有转移代价均非负，若最短游走中出现环，删去该环不会使总代价变大；优惠券是可选的，删去环中使用的优惠券后，剩余路径仍然可以正常运行。因此最优解一定可以对应到某条简单路径。

时间复杂度为 $O(m\log n)$。