【笔记】题集1
才几个题就一篇博客太占空间了，整个题集
这种零散地记录题目到底有没有用呢...反正先记了再说
CF773div2 D. Repetitions Decoding
题意：称一个长 2k(≤500) 的串 s 满足 \(s_i=s_{i+k}\) 为好串。给定一个字符串 s，每次可以往 s 的任意一个位置插入两个相同字符[c, c]。构造一种方法最终使得 s' 可以划分成若干好串。
hint
考虑这个操作可以等价成什么更有意义的操作
solution
考虑字符 xy，可以有：xy → xyxx → xyxyyx → yx，既然有了交换相邻字符这个操作，我们就能任意排列这个原串
CF773div2 E. Anonymity Is Important
题意：一个长为 n(≤2e5) 的 01 数组，初始所有值均已确定但未告知，需要在线通过以下操作推测数组：
1 l r：[l, r] 均为 0
2 l r：[l, r] 存在 1
3 p：根据已有信息，回答 p 的值（0，1或未知）
hint
相信你已经得到了一个O(nlog^2n)的算法，但是它真的需要一个log^2的做法吗
solution
首先操作1可以直接线段树维护，对于操作2，它生效的条件就是它所在的区间里有且仅有一个未确定的未知，其余均为0不为1 我们需要把已经确定为1的位置标记上1吗？ 我们把每个位置定义为两种状态，要么为0，要么不确定，当然，这个不确定指的是仅仅考虑所有操作1情况下的不确定 那么我们用set（强烈建议使用set！好写好调比线段树维护什么左右连续一段还要考虑查询什么的方便多了）维护所有不确定的位置 对于一个询问p，若p当前不确定，记p左右第一个也不确定的位置为pl和pr，那么等价于，是否存在一个之前的操作2 l r，满足 pl< l ≤ p ≤ r < pr 我们对于这个问题，如果看成二元坐标，可以有个o(n√n)的离线分块做法；我们也可以考虑这么存储[l, r]：**往左边界对应的节点上存右边界的信息** 建一个线段树，每个节点里放一个set，对于[l, r]，在包含l的log个区间内塞r，回答询问时，我们只需在这个logn个set中lower_bound一下是否有位于[p, pr)的节点就行了，这是个单次log^2的做法 但是实际上，由于pl，pr的实际含义，(pl, p)之间肯定不会有右端点的信息，所以不用set，而是对应地维护一个最小的右端点的信息就行了，所以是nlogn的
LeetCode周赛282
题意：给一个长为 n(≤1e5) 数组 tires ，其中 tires[i] = \([f_i, r_i]\) 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 \(f_i * r_i^{(x-1)}\) 秒。
比赛总共包含 num(≤1000) 圈，你可以选择任意一种轮胎开始比赛。每一种轮胎都有无数条。每一圈后，你可以选择耗费 T 秒换成任意一种轮胎（也可以换成当前种类的新轮胎）。求完成比赛需要耗费的最少时间。1≤f, T≤1e5, 2≤r≤1e5
hint
难道你在考虑求连续x圈的最小代价时，怎么维护这个像下凸壳一样的东西吗
solution
注意到指数的增长是极快的，真要维护那个下凸壳，你甚至很快就没法直接存下这么大的数