02/15/2025 模拟赛记录

一场东拼西凑的模拟赛

题意：给 $6$ 个数，$a,b,c,x,y,z$，有一些操作形如 a/b/c -= 2, a/b/c ++ 求经过若干次操作可否使 $a \ge x,b \ge y, c \ge z$

题解：统计多余的可用于重新分配的量有多少，再统计缺多少，作比较即可

题意：鸽

题解：开个桶，注意精度

题意：OEIS上有

题解：注意到显然的 $O(n^3) \text{DP}$，打表即可，也可前缀和优化至 $O(n^2)$

神似超速检测

题意：有一些车会在某一时刻瞬间出现在长为 $n$ 的道路某处，并以恒定速度向某一方向行驶，有一些询问，形如某时刻在道路的奇数、偶数下标各有多少辆车

题解：排个序，将车分为四类，统计四类车各有多少辆。按速度、初始位置奇偶性分类，注意常数

题意：有一个带点权的 DAG，求所有长度至少为 $k$ 的路径中中位数最大为多少

题解：二分答案，拓扑序 $\text{DP}$ 即可，$O(n^2 \log(n))$

题意：求有向图的 DAG 子图数量

题解：考虑状压，结合一些容斥，可得 $O(3^nm) \text{DP}$ 简单优化并预处理可得 $O(3^n+2^nm)$