十一期间的考试
甜美考试，快乐补题
聪明智慧的 Augury 考了两次第一
Day1 T1 U249249 单峰
题意简述
- 用
1\sim n 中的数组成一个「单峰数列」 - 单峰数列：当且仅当存在一个位置k使得
a_i < a_{i+1} (i<k)且a_i > a_{i+1} (i≥k) - 比如：
1,3,2 - 结果对
10^9+7 取余
做法
推式子
因为是个「单峰数列」，所以最大值肯定在中间
那么要考虑的数只有左边和右边，即
因为「单峰数列」是有序的，所以选数的顺序不重要
容易发现，只要确定了左边的数，右边就可以确定了
而左边有多少选法呢
是时候呼叫「超级卢贞昊」了！！！
那就是
所以答案就是
注意事项
-
n\le 10^{18} 是不是会
\color{052242}\texttt{TLE} 呢?
是时候呼叫「超级卢贞昊」了！！！
快！使用！「快速幂」！吼！吼！哈！嘿！ - 取余
推荐题目
P1226 【模板】快速幂||取余运算
P1965 [NOIP2013 提高组] 转圈游戏
P3197 [HNOI2008]越狱
Day1 T2 U249250 序列变换
全村人的噩梦
通过
老师造的数据比原题强哎
题意简述
- 你有一个长度为
n 的序列，你要支持两种操作 - 操作一：把所有的
x 替换成y - 操作二：询问当前数列分成几段
- 注：我们将连续的相同数字看做一段
做法
- 既然是一段，那么这堆数就都是一样的
那么它无论怎么变都是一段，不会被像卢贞昊和某某某一样被分开
所以用「链表」维护这个数列
两个相同的数就删掉一个 - 把一个数替换成另一个数，反正都是把两种数合并在一起
那么，把数量少的数替换成数量多的数
然后，你会发现，你再次操作的时候，他就错了
所以记录一下每个数被表示成了什么就行了
注意事项
- 您要写链表是吧
\color{ff3500}「吃饱喝饱，一路走好」
推荐题目
P1996 约瑟夫问题
P1160 队列安排
Day1 T1 [CSP-S2019 江西] 和积和
题意简述
- 你有两个数列，长度均为
n - 定义函数
S(l,r)(1\le l\le r\le n) 为：\sum_{i=l}^r a_i\times \sum_{i=l}^r b_i - 然后让你求出下列式子的值：
\sum_{l=1}^n \sum_{r=l}^n S(l,r) - 输出结果
mod 10^9+7 的值
做法
- 我们要求和的积的和，不是吗
那么我们在求和的积中的「和」时，就可以使用「前缀和」维护
那么就获得了\Theta(n^2) 的复杂度
可以得到70 分的好成绩 - 看看这个求和的式子
对于每一个l ，式子可以表示为\sum_{r=l}^n S(l,r)=\sum_{r=l}^n(suma_r-suma_{l-1})\times(sumb_r-sumb_{l-1}) =\sum_{r=l}^n suma_r\cdot sumb_r-suma_r\cdot sumb_{l-1}-sumb_r\cdot suma_{l-1}+suma_{l-1}\cdot sumb_{l-1} =\sum_{r=l}^n suma_r\cdot sumb_r-\sum_{r=l}^n suma_r\cdot sumb_{l-1}-\sum_{r=l}^n sumb_r\cdot suma_{l-1}+\sum_{r=l}^n suma_{l-1}\cdot sumb_{l-1} =\sum_{r=l}^n suma_r\cdot sumb_r-sumb_{l-1}\cdot \sum_{r=l}^n suma_r-suma_{l-1}\cdot\sum_{r=l}^n sumb_r +\sum_{r=l}^n suma_{l-1}\cdot sumb_{l-1} - 然后惊奇地发现，这个式子又是一堆定值的区间和包括：
- 如果
i 是「不好的数」而且vis_i=1 ，那么什么也不用干，因为i 的倍数一定被标过了 - 如果
i 是「好的数」，那么什么也不用干 - 这个过程很像「埃氏筛」
- 那么怎么查找下一个「好的数」呢
- 定义一个数组
nxt 表示下一个「好的数」 - 核心代码
for(int i=maxx;i>=1;i--){
if(!vis[i]){
nxt[i]=nnx;
nnx=i;
}
}- 如果当前这个数是「好的数」，那么它就是它的上一个数（如果有）的下一个「好的数」
- 那么倒序循环，当前这个数就是它的下一个数（如果有）的上一个「好的数」
- 那么定义
nnx 表示「下一个好的数」 - 如果
vis[i]==0，那么nxt[i]=nnx,nnx=i - 查询时直接输出即可
推荐题目
P3383 【模板】线性筛素数
P1865 A % B Problem
Day2 T2 P7913 [CSP-S 2021] 廊桥分配
题意简述
- 有一个有
n 个廊桥的机场 - 这个机场分为两个部分：国内区和国外区
- 你要把这
n 个廊桥分给这两个区 - 有
m 架飞机，每架飞机都属于两个区中的一个，如果飞机所属的区有空的廊桥，那么它会停在远机位 - 廊桥的使用符合「先来后到」的规则
- 现在你知道每架飞机的降落时间和起飞时间，问你怎么分配这
n 个廊桥，可以使尽量多的飞机能停靠在廊桥
做法
- 飞机占用廊桥遵循「先来后到」的规则，那么我们在意识形态上强制每一架飞机停在编号最小的、空闲的廊桥，然后记录每个廊桥上有多少飞机停过，用
f_i 表示第i 个廊桥停过的飞机数量 - 一开始假设每个区域都分配了
n 个廊桥 - 然后发现，无论怎么分配这几个廊桥，
f_i 的数值都是不变的！ - 这是因为飞机占用廊桥遵循「先来后到」的规则，「得不到的总是得不到，能得到的也肯定能得到」
- 那么，对
f_i 求「前缀和」sum 。因为两个区都要有廊桥，所以f 和sum 都要有组，分别记为f1,f2,sum1,sum2 - 那么，最后的答案：对于每一个
i(1\le i\le n) ，答案即为\max(sum1_i+sum2_{n-i}) - 上面还说了，我们要在意识形态上强制每一架飞机停在编号最小的、空闲的廊桥，这个用一个小顶堆时间即可
- 所以，最后的时间复杂度是！
\Theta(n\log m) （确信）
注意事项
- 廊桥的「借与还」很容易写错，还有就是当
n 个廊桥也不能满足所有的飞机时，就要放下一些飞机，容易写错（TQI亲身试错）
Day2 T3 P5658 [CSP-S2019] 括号树
快乐的树题
TQI 在考场上推式子推错了，然后得到了
题意简述
- 给定一棵树，每个节点上都有一个括号的一部分（「左括号」或者「右括号」）
- 然后让你求从根节点到每个节点的路径上的「互不相同的」「合法括号串」的个数
本题中合法括号串的定义如下：
()是合法括号串。- 如果
A是合法括号串，则(A)是合法括号串。 - 如果
A，B是合法括号串，则AB是合法括号串。
本题中子串与不同的子串的定义如下：
- 字符串
S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置l 与终止位置r 来表示，记为S (l, r) （1 \leq l \leq r \leq |S | ，|S | 表示 S 的长度）。 S的两个子串视作不同当且仅当它们在S中的位置不同，即l 不同或r 不同。
做法
- 最最最朴素的做法：跑出树上的每一条路径，然后暴力计算每一个区间是不是「合法括号串」
- 这样能得到
40 分左右 - 考虑每一条链，就是求一个「括号串」中「合法括号串」的个数
- 考虑
DP - 定义
dp_i 表示以i 结尾的最长「合法括号串」的长度 - 那么，如果
s_i=")" ，那么考虑dp_i 的转移
- 如果
s_{i-dp_{i-1}-1}="(" ，那么dp_i=dp_{i-1}+2 - 如果
1 成立，那么定义j=i-dp_i ，然后将dp_i 加上dp_j
- 现在我们处理出了长度，然后就是处理数量
- 定义
k_i 表示以i 结尾的「合法括号串」的数量 - 那么在
dp 转移的时候，顺便转移一下k -
k_i=k_{i-dp_i}+1(dp_i\ne 0) - 那么当前串中「合法括号串」的数量就是对
k 求前缀和 - 既然在链上是这样，那么在树上也别无二致
- 每次到达新的节点时，不用重新计算整条链上的答案，只需要计算「贡献变化」即可
- 就是只需要对当前节点的
dp,k,sum 进行修改 - 最后复杂度在
\Theta(n) 级别
推荐题目
P1944 最长括号匹配