做sequence专项题单
灰的积雨云
·
·
个人记录
做sequence专项题单
题目顺序事按照难度来排序的
大模拟，Skip
$\mathtt \color{green} [done]$[Bracket Sequence Deletion](https://www.luogu.com.cn/problem/CF1657C)
对于`(`, 删`() / (( `。对于`)`从左至右寻找到对应的回文，然后删除
$\mathtt \color{green} [done]$[P1628 合并序列](https://www.luogu.com.cn/problem/P1628)
先对字符串进行排序，然后二分查找满足要求的字符串区间的上界与下届便可
$\mathtt \color{green} [done]$[P1241 括号序列](https://www.luogu.com.cn/problem/P1241)
题意不清，还我时间
建立一个栈，存储未被匹配的左括号（指`(,[`），没当有一个右括号（指`)，]`），如果上一个为被匹配的括号可以匹配，从栈中取出，否则打上标记，在输出时将起填完整，对于那些永远不会匹配的左括号来说也是这个道理
$\mathtt \color{green} [done]$[P1716 双调序列](https://www.luogu.com.cn/problem/P1716)
一眼题，不说了
$\mathtt \color{blue} [done]$[Power Sequence](https://www.luogu.com.cn/problem/CF1397B)
首先指数是爆炸级别增长的，所以在n比较大的时候，c就只可能是`0/1`
在n比较小的时候，不妨枚举c的大小，遍历数组同时计算。而枚举次数做多是$\sqrt[n]{\sum_{i = 1}^{n} a_i}$,总体的复杂度是比较小的。
$\mathtt \color{green} [done]$[Sequence Transformation](https://www.luogu.com.cn/problem/CF1454C)
本质上就是统计出现次数最少的数字，如果在开头或结尾，对应代价少一，模拟即可
$\mathtt \color{green} [done]$[Number into Sequence](https://www.luogu.com.cn/problem/CF1454D)
对n进行质因数分解，为了使k最大，找到出现次数最多的质数p，输出$cnt_p - 1$个p，最后即为除下这些数的商
$\mathtt \color{blue} [done]$[Sequence and Swaps](https://www.luogu.com.cn/problem/CF1455D)
> 命题：遍历时遇到比x大数一定交换
证明：假设当前下表为i的数$a_i$比x大，存在$j > i$并且$a_j > x$。如果选择与$a_j$交换，则交换后$a_j < a_i$并且$i < j$不符合题意
所以找到最后一个使合法序列不成立的数，在此数之前进行上述操作。结束后再遍历一遍数组进行检查。
$\mathtt \color{blue} [done]$[P2193 HXY和序列](https://www.luogu.com.cn/problem/P2193)
DP，考虑n比较小。$f_{i, j}$表示当前在第i个位置，结尾为j
$\mathtt \color{blue} [done]$[Sequence Pair Weigh](https://www.luogu.com.cn/problem/CF1527C)
自己口胡的一种做法是首先考虑暴力，对于每一个位置，所有种类的数字都可以得到贡献，假设当前在位置i，并且考虑的是种类$a_i$的数字的贡献。贡献为$\frac{cnt_{a_i} \times (cnt_{a_i} + 1)}{2}$此处的$cnt_{a_i}$表示的是在$\left [i + 1, n \right ]$中j的数量。
考虑优化，正难则反。考虑一种构造方式得到等价的价值。$\sum_{i = 1}^{n} (n \times \frac{all_{a_i} \times (all_{a_i} + 1)}{2} - (n - i + 1) \times \frac{cnt_{a_i} \times (cnt_{a_i} + 1)}{2})$。此处的$cnt_{a_i}$表示在$\left [1, i \right ]$中$a_i$的数量。
很显然这个做法假掉了
正解是：假设$a_i = a_j = a_k$, 以k作为基准，$\left[1, i \right]$与$\left [k, n\right]$都是可以选择的区间，答案为$i \times \left(n - k + 1\right) + j \times \left(n - k + 1\right) $。设$pre_i$表示$\left[1, now\right]$中那些等于i的数字的下表之和。答案就是$\sum_{i = 1}^{n}pre_{a_i} \times (n - i + 1)
建模题。不想说了，我是将所有出现过的数根据因数关系进行建树。注意数与数之间的阻隔
$\mathtt \color{green} [done]$[P1483 序列变换](https://www.luogu.com.cn/problem/P1483)
在写的时候函数内变量名与全局变量名重了
对于操作1，先放入一个桶中根据x存起来。对于操作2，找到j的因数，此时这些桶中贡献加上原数列就是答案
$\mathtt \color{blue} [done]$[P1645 序列](https://www.luogu.com.cn/problem/P1645)
- Sol1: 贪心
按照右端点排序，我们所要填的数字一定是最靠近右端点的，每填一个数字打上对应的标记，最后统计答案。
- Sol2:差分约束
设$s_i$表示$\left [1, i \right]$中填的数字的个数。如果没有填数字，则$s_{i + 1} - s_{i} \ge 0$，同样的，最多填写1个数字，则$s_{i + 1} - s_{i} \le 1$对应就是`add(i, i + 1, 1)，add(i + 1，i, 0)`，每一次的输入可以转化为$s_r - s_{l + 1} \ge c$跑spfa即可
$\mathtt \color{blue} [done]$[P2659 美丽的序列)](https://www.luogu.com.cn/problem/P2659)
单调栈找到当前这个数右边比起第一个小，左边比其第一个小就行了
$\mathtt \color{blue} [done]$[Sequence Sorting](https://www.luogu.com.cn/problem/CF1223D)
在数字没有重复出现的情况下，发现不用移动的就是此序列中单调非递减的一串数字的个数。不妨称一种类型的数字的占领区间为最左边出现的地方与最右边出现的地方。转换一下，就是求占领区间中的单调递增了，只有两个区间无交集才可以算做答案。