NBL小可爱纪念赛「 第一弹 」 赛后题解

· · 个人记录

A - NBL与泰国之旅

30 分

直接按题面暴力，搜有多少个位置 (i,j,k) 使得 i<j<k 并且 S_i=I,S_j=O,S_k=I。

45 分

方法 1

对与每个位置，使用前缀和来算出来一个位置前面有多少个 I。

暴力，搜有多少个位置 (i,j) 使得 i<j<k 并且 S_j=O,S_k=I，对与每一对加上位置 i 的前缀和。

方法 2

裸DP，设 A_i 为有多少个 I 子序列在位置 i 结束，B_i 为 IO 子序列，C_i 为 IOI 子序列。

退出来：

A_i=[S_i=I] B_i=[S_i=O]\cdot\sum_{j=1}^{i-1}A_i C_i=[S_i=I]\cdot\sum_{j=1}^{i-1}B_i

答案为所有 C_i 之和。

95 分

考虑优化 45 分 方法 2。

用前缀和优化DP，X_i 设为 A_i 前缀和，Y_i 为 B_i 前缀和， Z_i 为 C_i 前缀和。

退出来：

X_i = X_{i-1} + [S_i=I] Y_i = Y_{i-1} + [S_i=O]\cdot X_{i-1} Z_i = Z_{i-1} + [S_i=I]\cdot Y_{i-1}

答案为 Z_{|S|}。

100 分

卡卡95分的常数。

首先，可以直接用 getchar，大大降运行时间。

第二，只需要保存3个数字，就是上一个 X_i，上一个 Y_i，和上一个 Z_i。

第三，模运算特别贵，所以只判断是否一个数字超过 mod，如果超过就减去 mod。

B - NBL与二次元

20 分

先打出来斐波那契数列前缀和，然后直接按照题目要求做。

100 分

首先，推出来一个重要性质：

\sum_{i=0}^{k}f(i)=f(k+2)-1

如何证明？

f(x)=f(x) f(x)=f(x)+f(x+1)-f(x+1) f(x)=f(x+2)-f(x+1)

现在，

\sum_{i=0}^{k}f(i)=\sum_{i=0}^{k}(f(x+2)-f(x+1))=\sum_{i=2}^{k+2}f(x)-\sum_{i=1}^{k+1}f(x)=f(k+2)-f(1)=f(k+2)-1

那么 f(x) 就直接用矩阵快速幂或者矩阵快速幂提取出来的运算来计算就可以了。

C - NBL与玄学柿子

40 分

直接按题目要求暴力。

80 分

推式子。

\sum_{l=1}^{N} \sum_{r=l}^{N} \sum_{i=l}^{r} \sum_{j=i+1,a_j<a_i}^{r} a_i \times a_j

在这里，考虑有多少个 (l,r) 对满足 l \le i, j \le r。这个就是 a_i \times a_j 被算到最终答案多少次。

显然有 i 个方法来选 l，n-j+1 个方法来选 r，所以选 (l,r) 方案数是 i\times (n-j+1).

\sum_{i=1}^{N} \sum_{j=i+1}^{N} [a_j<a_i]\times a_i \times a_j \times i \times (n-j+1) ## 100 分 继续推。 $$\sum_{i=1}^{N} \sum_{j=i+1}^{N} [a_j<a_i]\times a_i \times a_j \times i \times n-j+1)$$ $$\sum_{i=1}^{N}(a_i\times i\times\sum_{j=i+1}^{N} [a_j<a_i]\times a_j\times(n-j+1))$$ 这样等于维护一个动态前缀和，从 $N$ 往 $1$ 遍历 $a_i$。每一次遍历做这些步骤： 1. 把 $a_i\times i \times([1,a_i-1] \text{所有数之和})$ 累计到答案里 2. 把位置 $a_i$ 加上 $a_i\times(n-i+1)$。 这个动态前缀和可以使用动态开点线段树，平衡树，离散化+BIT，和别的东西维护。 注意玄学摸，需要使用 `__int128_t`，或者可能会在乘法里溢出。 # D - NBL与叠加矩阵 ## 30 分 首先判断所有矩形的面积和是否等于它们最小全部覆盖矩形的面积，如果不等于直接输出 `Guguwansui`。 最小全部覆盖矩形定义：最小全部覆盖矩形的左下角是 $(\min a, \min b)$；最小全部覆盖矩形的右上角是 $(\max c, \max d)$。 然后对与所有对矩形判断它们是否互相冲突，如果没有输出 `Perfect`，否则输出 `Guguwansui`。 ## 60 分 假设已经特判了 $N \le 1000$ 的时候。 第一还是判断最小全部覆盖矩形面积。 然后，做一个二维前缀和，如果在任意位置前缀和是 $2$ 或者以上，输出 `Guguwansui` 并且停止。 如果最大前缀值是 $1$，输出 `Perfect`。 ## 100 分 考虑 scanline （一个类似于离散化的思想）。假设我们已经有一个动态开点 lazy 线段树，支持： 1. 区间设 0 2. 区间加 3. 所有数最大值 还是先判断最小全部覆盖矩形。 还是用60分的前缀和思想。使用这个线段树来维护一个前缀和列的数值。 我们定义一个 event 当四个数字，$(t,v,l,r)$，表示在第 $t$ 列需要把区间 $[l,r)$ 加上 $v$。 对与每一个矩形，会造出来两个 event：$(a,1,b,d)$ 和 $(c,-1,b,d)$。 把这些 event 按递增 $t$ 排序，并且如果有两个相同的 $t$ 但是不同的 $v$ 把 $v$ 为 $-1$ 的放在前面。 对与每一个 event，在线段树里做这个操作。做完，询问序列最大值；如果序列最大值等于或者超过 2 立刻停止并且输出 `Guguwansui`。 成功做完的话，输出 `Perfect`. # E - NBL与花少北 ## 10 分 对与第一个点，$N=1$，所以直接模拟就可以了。 ## 100 分 设 $DP_i$ 为把前 $i$ 字符构成的串变完美的最小修改字符数；如果不能变完美设为 $1005$. 在第 $i$ 个字符的时候，可以枚举用最少修改修成完美串的时候，最后匹配到那个串。 如果固定最后匹配的串是第 $j$ 个串，那代价是 $$DP_{i-|a_j|}+\sum_{k=i-|a_j|+1}^i[S_k\neq a_{j_{k-i+1}}]$$ 所以， $$DP_i=\min_{j=1}^N(DP_{i-|a_j|}+\sum_{k=i-|a_j|+1}^i[S_k\neq a_{j_{k-i+1}}])$$ 初始化 $DP_0=0$。