9.22 机房模拟赛游记

发布时间 2023-09-23 12:05:51作者: CSP_AK_zyz

感觉游记没得写。(赢麻了,连续 $\text{AK 3}$ 次了,不过好像也没啥可骄傲的。

$\text{T1}$ 

            共 $n$ 个不同种类的元素,用容量为 $k$ 的背包来装,需要把这些元素全部装进背包,且每个背包装的必须是同种元素,问至少需要多少背包?

答案为 $\sum_{i=1}^n\left\lceil\dfrac{a_i}{k}\right\rceil$

$\text{T2}$

            对于一个矩阵,对于任意两个相邻点 $(x_1,y_1)$ 和 $(x_2,y_2)$,求 $\max(|a_{x_1,y_1}-a_{x_2,y_2}|)$。

暴力枚举每个相邻点即可,方向数组可以可不用,但是个人觉得用了有点麻烦。

$\text{T3}$

            有 $n$ 个元素,你有一种魔法,每次使用一次就能让所有元素的值加 $1$,当然如果元素值相同的话只能选其中一个值加 $1$,若元素值达到 $k$,则不在继续加,问至少多少次魔法能使 $\{a\}=k$。

暴力枚举即可,拿个桶判重。

$\text{T4}$

            对于一个序列 $\{a\}$,求是否有 $\sum_{i=1}^n(\pm a_{i})\equiv 0\pmod{k}$。

动态规划,令 $f_{i,j}$ 表示前 $i$ 个数是否能有 $\sum_{t=1}^i(\pm a_{t})\equiv j\pmod{k}$


坑点:需要预处理将 $a_i$ 变为 $|a_i| \text{ mod}\text{ } k$。

转移方程:$f_{i,j}=f_{i-1,(j-a_i+k)\%k}|f_{i-1,(j+a_i)\%k}$。