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)