[2023] 1.1 ~ 1.8做题笔记
Chancylaser · · 个人记录
P4155 [SCOI2015]国旗计划 by 2023/1/1
简单的贪心+倍增优化。
贪心后发现实现起来是平方级别的，所以考虑优化。发现数据是静态不变的，结合倍增的性质，所以使用倍增优化。时间复杂度O(n log n)。
需要格外注意破环成链的细节。
P1198 [JSOI2008] 最大数 by 2023/1/1 （实际上提交时间已经到了二号了）
st表的微进阶操作。
初始序列为空，动态增加数据。这动态修改似乎只能用线段树等在线数据结构维护，但其实st表也能维护，因为修改只在序列最后。这里的修改指添加一个数。
实际上，假设添加后序列长度为n，设f是st数组，我们只需要找出f[i][j]，也就是i往后(1<<j)个数，最后一个数为n，修改这些就可以了，显然最大的修改数为log2(n)。
查询为st表常规查询。
P5648 Mivik的神力 by 2023/1/2
倍增好题。
首先需要一个单调栈来维护a[i]下一个>=它的数的位置，然后倍增就可以了，注意开LL。
感觉单调栈是倍增题目的常见预处理技巧。
P1081 [NOIP2012 提高组] 开车旅行 by 2023/1/3
对我来说较困难的倍增，预处理了5个数组，代码写了120+行。
用了大量的STL，具体细节不好描述。
P3948 数据结构 by 2023/1/4
这是一道水蓝，感觉难度只能到绿。
发现修改多，查询少，故马上反应过来这是一道差分题。发现了这个性质，裸差分、前缀和套上去就能过，跑得还挺快。随机数据
P4552 [Poetize6] IncDec Sequence by 2023/1/4
差分好题，可能不难，但是非常有助于理解差分的用法及性质。
首先求出原序列的差分数组，然后统计差分数组所有正数的绝对值和所有负数的绝对值。然后简单输出即可。
具体推算可以去看题解。
一月五号出去玩了一天，晚上打了个CF，没刷题。
P1052 [NOIP2005 提高组] 过河 by 2023/1/6
分析题目，很容易设计出一个暴力DP。但是发现需要枚举的L太长。
继续观察题目，发现石子的数量极其得少，简单一想便能推出，过于长的空地其实可以忽略掉。所以考虑类似缩点的操作，先对石子排序，假如两个相邻的石子距离很大，那么我们缩小到一个固定的值w，如果距离小于等于这个w则不变。这样的话，暴力DP即可通过。
离散化的思想，好题。
P2652 同花顺 by 2023/1/6
题意很简单。首先离散化，把花色和数字相同的牌扔掉直到只留下一张。然后以花色为第一关键字，数字为第二关键字排序。
从1开始枚举，枚举的是我们最终要构成的顺子的最后端点。显然，我们需要留下尽量多的牌数。我们这里开一个队列维护。
如果当前的花色与上一张的花色不同，我们显然应该清空候选答案；否则，则判断当前的数字与队列中第一个元素的差值是否>=n，如果成立，则pop掉这个元素。while完这个操作后，再push当前枚举到的数字。此时答案显然就是(n-队列长度)。打擂法记下答案即可。
咕咕咕，又咕了好几天。以下的题目的笔记，写得时候已经到11号了
P1593 因子和 by 2023/1/7
简易的题意能让我们快速了解题目问得什么。
利用整数的唯一分解定理，然后推推式子即可解决，利用了一些高中的知识。另外模运算这一块的处理很有意思。
P2672 [NOIP2015 普及组] 推销员 by 2023/1/8
贪心的经典好题。
首先肯定得排序，容易发现：只需舍去最小值来走更远，无需舍去更多数来走更远。然后预处理几个数组解决此题。贪心的题目主要是思路，代码一般不难。
P1080 [NOIP2012 提高组] 国王游戏 by 2023/1/8
又是一道贪心的经典好题。
首先把当前的大臣左右手的表达式写出来，然后通过推式子，发现只要以a*b为关键字排序即可。
不过这道题目需要高精度，有点小烦人。
P2123 皇后游戏 by 2023/1/8
较难的贪心题目。
还是推式子，只不过这式子比国王游戏难上很多。推出来后，发现以那玩意为关键字排序是错的，因为没有使排序能满足传递性，所以需要加点东西，使它满足传递性。
一种解决的办法是，令