20230921NOIP训练赛#12总结

Timeline

08:00-08:10

通看一遍题目，A 像性质题，B 6,7 点感觉可以贪（？，剩下的感觉？？？，C 感觉暴力写起来很麻烦，D 无头绪只会暴力，先把 A 暴力写了

08:10-08:40
A 性质没想出来，B 贪想到了一个细节导致代码好难写（也许根本就没法贪）

08:40-09:00

把 C 的部分分和 D 的暴力打上了

09:00-09:30

把 C 的暴力打上了，还顺便把部分分的错找出来了

09:30-09:55

把 B 的暴力打上了，开始罚坐

10:30-11:00
D 写了一个 $\mathcal{O}(qnm\log m)$的 3,4,5，但是常数巨大（或者算错了）极限数据测了一下会 G （希望是随机）

11:30

D 砍去了 $\log$，常数大大减小

Result

$70+20+20+50$，B 贪心写炸了 $-20$，C 部分分挂了 $-20$。

Summary

1. 得加快点写暴力的速度。

2. 先想好怎么写再去写。

Problem

T1

$T$ 组询问，每次给定 $n=\prod p_i^{c_i}$，其中 $p_i$ 为互异的质数，求 $\gcd c_i$。

$n\leq 10^{18},T\leq 10^{4}$

Solution

枚举 $\gcd$ 为 $k$，$k$ 为 $\log$ 级，若 $\sqrt[k]{n}$ 为整数则合法。

WHY?

$$n=p_1^{c_1}p_2^{c_2}\dots p_q^{c_q}=(p_1^{\frac{c_1}{k}}p_2^{\frac{c_2}{k}}\dots p_q^{\frac{c_q}{k}})^k$$

若 $k$ 为 $\gcd c_i$，则有 $\frac{c_i}{k}\in \mathbb{Z}$，又因为 $p_i\in \mathbb{Z}$，故 $p_1^{\frac{c_1}{k}}p_2^{\frac{c_2}{k}}\dots p_q^{\frac{c_q}{k}}\in \mathbb{Z}$。

时间复杂度 $\mathcal{O}(T\log^2 n)$。

T2

$n$ 天要拿 $m$ 件包裹，每个包裹第 $l_i$ 天到货，第 $r_i$ 天之后过期，一次最多拿 $k$ 件，一天内可往返多次，第 $i$ 天往返一次的代价为 $c_i$，最小化代价。

$n,m\leq 4000,\forall i\neq j,l_i\leq l_j\rightarrow r_i\leq r_j$

Solution

排遍序，设 $d_{i,j}$ 为 $\min_{k=i}^{j} c_k$，$f_i$ 为拿走前 $i$ 个的最小代价，故枚举之前的未过期的包裹，注意 $k$ 的限制：

$$f_i=\min f_{j-1}+d_{l_i,r_j}\leftarrow \max(1,i-k+1)\leq j\leq i,l_i\leq r_j$$

时间复杂度 $\mathcal{O}(n^2+m^2)$。

T3

$n\times n$ 的棋盘，其中 $i\bmod d_x=0$ 且 $j\bmod d_y=0$ 的点为坏点，一个点能移动到另一个点，当且仅当两点所成矩形中不含坏点，代价为矩形中数字最小值，求 $(1,1)$ 到每个点的代价。

$n\leq 300$

Solution

对于每个极大互通子矩阵内枚举分界点，对于分出的四个块建立“进点”和“出点”，然后跑 Dijkstra。

时间复杂度 $\mathcal{O}(n^2\log n)$。

T4

给出长度为 $n$ 的序列 $a_i$，$q$ 次询问 $[l,r]$ 内有多少个子序列的和为 $x$。

$n,q\leq 10^5,1\leq a_i,x\leq 300$

Solution

用猫树离线处理，对于当前的 $l,r$，先预处理出 $mid$ 两边每个位置的背包信息，对于每个询问，若 $l_i\leq mid\leq r_i$，则合并这两个背包得到答案，否则划分给 $[l,mid]$ 或 $[mid+1,r]$ 处理。

时间复杂度 $\mathcal{O}(nm\log n+q(m+\log n))$

满分做法过于人类智慧，不作解释。