20231013NOIP训练赛#19总结

Timeline

07:40-08:10

通看了一下题目，A 感觉很可做，B 感觉不太可做，C 又是构造，D 不会，先把 A 暴力打了

08:10-09:10

想 A 正解，想到了“正解”，打那个正解

09:10-10:10

写完了，测大样例不对，写对拍，第一组就寄了，发现写的统计的方法不对

10:10-10:45

先把 B,C,D 暴力打了

10:45-11:10

想到了另一种统计方式，这下能过大样例了，但是跑了 1.5s /jk

11:10-11:30

把线段树换成了 ST 表，大样例 0.5s 左右应该稳了

11:30-11:50

GG

Result

$100+15+25+15=155$

Summary

1. 这就是为什么不要摆

2. 大样例错了之后写对拍

3. 比赛结束前 1h 检查一下暴力

Problem

T1

给出长度 $n$ 的序列 $a_i$，最小化分成的段的数量，使得每段内第一项为最小值，最后一项为最大值。

$n\leq 3\times 10^5,1\leq a_i\leq 10^9$

$0.5\text{s}/512\text{MB}$

Solution

对于每个 $i$，二分找 $[i,n]$ 内第一个 $<a_i$ 的位置 $pos$，然后再找里面最大值最后一个位置。

怎么找？离散化，开 $n$ 个 set 存位置，找的时候直接从 set 里二分。

用 ST 表维护能做到严格单 $\log$，时间复杂度 $\mathcal{O}(n\log n)$。

此外还有一种单调栈的做法，维护右侧第一个小于、大于它的第一个数，找最大值的最后一个位置怎么办？直接跳。

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

T2

给出长度 $2n$ 的序列 $a_i$，$\forall i\in [1,n]$ 序列仅有两个 $i$，有两种操作：

• 删除相邻两个相同的数

• 交换两个相邻的数

最小化操作次数使序列清空。

$n\leq 5\times 10^5,1\leq a_i\leq n$

$1.5\text{s}/256\text{MB}$

Solution

最小的操作一定是将互相包含的几对数中先将被包含的两个数先消掉，然后再消掉外面的，因为这样就可以让外面的少移动两步。那么我们可以将两个相同的数看作一段区间，然后再按左端点从大到小排序，然后一个一个区间处理即可。

怎么维护一个数前面有多少个还未删除的数来确定现在的位置？用树状数组维护类似后缀和的东西，至于区间，直接从前往后扫，遇到一个之前没有遇到的 $a_i$ 就将 $a_i$ ​值变成之前遇到的不同的 $a_i$ 的个数加一，等到树状数组的时候，就将新的 $a_i$ 从大到小枚举去计算答案即可。

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

T3

给出 $n\times m$ 的网格，可以往八个方向走，指定起点 $(1,1)$ 和终点 $(x,y)$，给出一种方案使得从起点走到终点且经过每个点恰好一次。

$2\leq n,m\leq 100$

Solution

将大的网格分成多个小的网格去讨论。

详细题解见 https://oj.33dai.cn/d/TYOI/p/N0368/solution 和 https://atcoder.jp/contests/abc232/editorial/3157。

T4

有 $n$ 个点，初始时位于 $1$，走动 $m$ 次，依据走动的路径依次建立有向边，问多少种生成方式使得生成的图为强连通图。

$n,m\leq 300$

Solution

每次移动的位置会影响整个图的性质，故以此为决策，同时若指定从 $1$ 为起点，那么连上 $1$ 绝对为强连通图。由此设 $f_{i,j,k}$ 为走了 $i$ 步，经过了 $j$ 种不同的点，包含 $1$ 的最大强连通子图的个数为 $k$ 时的方案数，对于一个点，有三种情况：

1. 该点未被经过。

2. 该点不包含在含 $1$ 的强连通子图里。

3. 该点包含在含 $1$ 的强连通子图里。

分别对应：

$$f_{i+1,j+1,k}\leftarrow f_{i,j,k}(n-j)\\ f_{i+1,j,k}\leftarrow f_{i,j,k}(j-k)\\ f_{i+1,j,j}\leftarrow f_{i,j,k}k$$

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