2024.10.9 题目

题解：2024.10.9 模拟赛

矩阵交换

排序 贪心

有 $n\times m$ 的整数矩阵 $a$，每个元素均为 $1,2,3$。可以选择任意两不相等的行，将它们交换，使得每一列 $i$ 均单调不减 $a_{j,i}\le a_{j+1,i}$ $(1\le j<n)$。

砖块摆放

找规律 组合数学

有 $n$ 个砖块，第 $i$ 个砖块颜色为 $s_i$（用 $\text{A,B,C}$ 表示，转换成数字为 $0,1,2$）。进行 $n-1$ 次变换，每次变换会将元素数量 $n$ 变为 $n-1$。设 $a$ 为变换前的序列，则变换后的序列 $b$ 满足 $b_i=-(a_i+a_{i+1})\mathrm{mod}3$。

学习 LIS

序列dp 最长上升子序列

有长度为 $n$ 的数组 $a$，满足 $\forall i\le n,a_i\in [1,m]$。已知对于数组 $a$ 的位置 $i$，以 $i$ 结尾的最长上升子序列长度为 $l_i$，求满足条件的 $a$ 的数量。

战略轰炸

并查集 线段树 树状数组

有 $n$ 个军事基地围成圆，第 $i$ 个和第 $i+1$ 个相连。第 $i$ 个军事基地战斗力为 $a_i$，$a_i$ 非正则基地 $i$ 被消灭。有 $q$ 个询问，每次询问给出询问类型 $op$。

• $op=1$，给出询问 $(u,v)$，表示编号为 $u$ 与编号为 $v$ 的基地用桥梁连接，变成了新的一个基地，战斗力为 $a_u$ 与 $a_v$ 的和。若有两座桥梁交叉，则两座桥梁连接的军事基地也联通；
• $op=2$，给出询问 $(k,b)$ 表示有轰炸能力为 $k$、轰炸范围为 $b$ 的轰炸机可以轰炸 $b$ 个不同的未被消灭的军事基地，每次轰炸会对其减少 $k$ 的战斗力。轰炸中途若有军事基地被消灭，则定义为不完美轰炸。询问是否有方案能达到完美轰炸。