LibreOJ Round #6 题解

liu_cheng_ao 2017-10-28 23:18:08 2017-11-02 22:33:37

本次比赛的人物设定来源于**《黄金拼图》**(きんいろモザイク)—— 呃没错,就是出现了无数次的九条可怜所在的漫画/动画。

和预告中的「鳞托菊」又有什么关系呢?Rhodanthe* 指的其实就是五位登场角色啦。

为了保持题目的严谨而进行的故事套大量抽象内容所带来的违和感…… 也请大家理解啦 QuQ

T1. 花煎

By cyand1317,题解 By cyand1317

  • 考察选手对贪心性质及其边界情况的分析能力。
  • 枚举 + 贪心
  • 思维难度:NOIP 提高
  • 实现难度:NOIP 提高-

本场的送分题是不是够良心呢 (/ω\)

废话超多,觉得水的部分尽管跳过啦 ///

算法一

哈哈哈哈我会手玩!!手工枚举计算出 k \leq 10 且样例中未给出的 8 种取值的答案,打表输出即可。

时间复杂度: O(T)
空间复杂度: O(k)
预计得分: 25

算法二

太长不看版:暴搜

聪明的你应该已经发现,一个环任意旋转后的色彩值不变。又由于没有「对立元素」的环必然不满足要求,因而我们不妨固定元素 1 \frac n 2 + 1 为「对立元素」。

按照定义,环一定是对称的 —— 即被「对立元素」分隔的子段中,一个属于 [1, \frac n 2] 半圆中的子段总是对应一个 [\frac n 2 + 1, n] 半圆中的等长子段,反之亦然。因而 m = k^2 中的 k 即表示 [1, \frac n 2] 半圆内所有被「对立元素」分隔的子段的长度之积。为简明起见,以下我们均仅对 k [1, \frac n 2] 半圆作考虑。

对于 k \leq 500 ,我们不妨估算一个答案的上界。假设所有的子段长均为 x ,那么可以通过 (x + 1) \cdot (\lceil \log_x k \rceil + 1) 个元素构造出一个符合条件的半圆。取 x = 3 得到最低的上界 (3 + 1) \times (6 + 1) = 28 ,因而在 k \leq 500 时,最优解中半圆的大小不会超过 28

之后枚举半圆的大小,并枚举半圆上的每个元素分别是「独立」还是「对立」,并计算每一种方案的色彩值就可以啦。

时间复杂度: O(2^{4 \cdot \lceil \log_3 k \rceil + 1}) \approx O(k^{2.52}) 或渐近意义下更优
空间复杂度: O(k)
预计得分: 50

算法三

太长不看版:背包

本题至此转化为:找到一个由正整数组成的可重集 \{x_i\} (其中每一个元素 x_i 对应一个长度为 x_i 的子段),使得 \prod x_i \geq k ,同时 \sum (x_i + 1) 尽可能小。

\prod x_i \geq k 两边取自然对数得 \sum \ln x_i \geq \ln k 。这是一个完全背包问题的模型:对于每个正整数 x ,有一种数量无限、体积为 x + 1 、价值为 \ln x 的物品。一个物品实际上也对应了一个长度为 x 的子段,其占用 x+1 个半圆上的元素。

答案为使得总价值不小于 \ln k 所需的最小体积。共有 O(k) 种物品,背包容量为 O(k) ,直接进行 DP 即可。DP 实际上只需计算一次,此后每次询问只需访问数组得到答案。

时间复杂度: O(k^2)
空间复杂度: O(k)
预计得分: 65
参考程序

算法四

太长不看版: k = 4^e, \ k = 4^e \cdot 2 都能达到下界

在以下的讨论中,「物品」与「子段」一一对应,不加以明确区分。

f(x) 为正整数 x 对应的价值与体积之比,即

f(x) = \frac {\ln x} {(x + 1)} \quad (x \in \mathbb{N^*})

通过打表、作图、求导等各种方式可以得知, x = 4 f(x) 有最大值 \frac {\ln 4} 5 。因而:

要达到 \ln k 的总价值,需要的总体积(半圆的元素个数)不小于 \left\lceil \ln k \div \frac {\ln 4} 5 \right\rceil = \lceil 5 \log_4 k \rceil

k = 4^e \ (e \in \mathbb{N^*}) 时,可以通过 e 个长度为 4 的子段来达到恰好 5e = 5 \log_4 k 的元素个数。于是我们证明了如下性质:

k 4 的整数次幂,使用 \log_4 k 个长度为 4 的子段是一种最优方案。

而当 k = 4^e \cdot 2 \ (e \in \mathbb{N}) 时, \lceil 5 \log_4 k \rceil = \left\lceil 5e + \frac 5 2 \right\rceil = 5e + 3 ;使用 e 个长度为 4 的子段和一个长度为 2 的子段,元素个数恰为 5e + 3 ,也达到了下界。综合上述分析,有:

k 2 的整数次幂 2^e

  • e 为偶数:使用 \frac e 2 个体长度为 4 的子段是一种最优方案;
  • e 为奇数:使用 \frac {e-1} 2 个长度为 4 的子段以及一个长度为 2 的子段是一种最优方案。

至此,我们顺利解决了第 3 个子任务。

时间复杂度: O(T \log k)
空间复杂度: O(\log k)
预计得分: 15 ,结合前述可得 80

算法五

太长不看版:除了 4 以外的其他选择似乎都比较辣鸡…

以下分析从「对数」的方式回归「乘积」的方式。

根据上面算出的最值,除了 4 以外的其他选择似乎都比较辣鸡,但是又不能忽略(有时我们不得不用它们补足不为 4 的整数次幂的部分)。因此,我们希望证明它们的出现次数都很少

1. 长度为 \mathbf{0, 1} 的子段不出现

否则,直接删掉就可以得到一个更优的解了。

2. 长度为 \mathbf{2} 的子段出现不超过一次

否则,将其中两个替换为一个长度为 4 的子段,元素总个数从 6 变为 5 ,对乘积的贡献保持 4 不变,答案不会变劣。

3. 长度为 \mathbf{3} 的子段出现不超过四次

否则,将其中五个替换为四个长度为 4 的子段,元素总个数保持 20 不变,对乘积的贡献从 243 变为 256 ,答案不会变劣。

4. 长度为 \mathbf{5} 的子段出现不超过一次

否则,将其中两个替换为三个长度为 3 的子段,元素总个数保持 12 不变,对乘积的贡献从 25 变为 27 ,答案不会变劣。

5. 长度大于等于 \mathbf{6} 的子段不出现

否则,将其替换为一个长度为 2 和一个长度为 3 的子段,元素总个数和对乘积的贡献均不变,答案不会变劣。

否则,将其替换为 \left\lfloor \frac {x+1} 3 \right\rfloor 个长度为 3 的子段,元素总个数不会增多,对乘积的贡献从 x 增大为 3^{\lfloor \frac {x+1} 3 \rfloor} ,答案不会变劣。

综上所述,一个最优方案可以只由长度为 2 3 5 的子段组成,且数量极少。枚举它们的个数 c_2 \ (\leq 1), c_3 \ (\leq 4), c_5 \ (\leq 1) ,计算达到要求额外需要的乘积

k' = \left\lceil \frac {k} {2^{c_2} \cdot 3^{c_3} \cdot 5^{c_5}} \right\rceil

添加 \lceil \log_4 k' \rceil 个长度为 4 的子段便能达到要求。对于所有的情况取答案的最小值即可。

另外,我们可以继续优化:除了 4 之外 3 是第二优的答案,在 k 足够大时可以只用 4 3

6. 长度为 \mathbf{2} 的子段不和长为 \mathbf{4} 的子段同时出现

否则,替换为两个长为 3 的子段,乘积从 8 变为 9 ,答案不会变劣。

7. 长度为 \mathbf{5} 的子段不和两个长为 \mathbf{4} 的子段同时出现

否则,替换为四个长为 3 的子段,乘积从 80 变为 81 ,答案不会变劣。

故,我们可以预处理使得这种方案出现的最小值(这个值不大于 2\times 3^4\times 4\times 5=3240 )以内的答案,大于该范围的只枚举 3 的个数即可。

时间复杂度: O(T \log k)
空间复杂度: O(\log k)
预计得分: 95 \sim 100

算法六

\log_4 k

不就是 __builtin_clzll 的事儿嘛。

当然也可以选择各种其它的位运算加速方法,比如 liu_cheng_ao 给出的下面这种:

int _lg4[1<<16|1];

// ...
for(int i=4;i<(1<<16);i++)_lg4[i]=_lg4[i>>2]+1;
// ...

int lg4(long long x){
	int ans=0;
	if(x>>32)ans+=16,x>>=32;
	if(x>>16)ans+=8,x>>=16;
	return ans+=_lg4[x];
}

时间复杂度: O(T \frac {\log k} {\log w})
空间复杂度: O(\log k)
预计得分: 100
参考程序

T2. 花团

By liu_cheng_ao,题解 By liu_cheng_ao

  • 考察选手对 DP 和分治算法的理解。
  • 背包 DP + 分治
  • 思维难度:NOI-
  • 实现难度:NOI-

算法一

太长不看版:暴搜

注意到任意时刻的物品数 n=O(q)

q 很小时,可以枚举每个物品是否选择计算答案。

时间复杂度: O(q 2^q)

空间复杂度: O(q)

预计得分: 15

算法二

太长不看版:背包

这是个经典的背包问题,可以DP解决。设 f(i,j) 表示在前 i 个物品选择,总体积为 j 的最大价值,转移为 f(i,j)=\max(f(i-1,j),f(i-1,j-v_i)+w_i) 。即 f_j\max =f_{j-v_i}+w_i 。当 n>v 时可以预处理每种体积的最大值。

时间复杂度: O(q v \min(q,v))

空间复杂度: O(v)

预计得分: 35

算法三

太长不看版:bitset做第一问

使用位运算优化第一种询问。设位向量 f 表示每种体积的方案是否存在,转移为 f |= f << v_i 。由于只回答了一个询问,无法解决在线加密问题。

时间复杂度: O(\frac{q v \min(q,v)}{w})

空间复杂度: O(\frac{v}{w})

预计得分: 14\sim 22 ,结合前述可得 43 \sim 51

算法四

太长不看版:线段树分治

考虑对时间分治。预处理出每个物品存在的时间区间,然后每次统计完整覆盖当前处理的时间区间的物品的影响,递归到左右两个子区间,返回时撤销影响即可。

或者这样理解:以时间为关键字建立一棵树,并把每个物品存在的时间区间分解为若干子树的和,在这些子树的根上标记,最后对树做深度优先遍历,维护根到当前节点的路径上的物品的影响即可。使用完全二叉树即可最小化分解后的点数,为 O(q\log q)

这是一个离线算法。

时间复杂度: O(q v\log q)

空间复杂度: O(v\log q)

预计得分: 55 ,结合前述可得 75

算法五

太长不看版:在线的线段树分治

注意到虽然算法四是离线的,但本题有一个特殊条件:给出物品时同时给出了移除时间。由于算法四中对时间是从左到右访问的,只需在第一次处理左起点为 i 的时间区间时加入询问 i 即可。

时间复杂度: O(q v\log q)

空间复杂度: O(v\log q)

预计得分: 100

T3. 花火

By spj,题解 By spj

算法一

对于子任务 1 n\le 4 ,数据极小,可以用深搜或者手算所有 n! 种排列的答案等各种方法通过。

期望得分 : 6

算法二

对于子任务 2 n\le 8 ,数据较小,可以用广搜求解。

以当前排列和是否交换过不相邻元素为状态,通过枚举交换的两个元素来扩展。可以使用类似八数码的Hash记录状态。

状态数为 2\cdot n! ,每个状态有 C_n^2 个扩展,总时间复杂度为 O(n!n^2)

时间复杂度: O(n!n^2)

期望得分: 17

算法三

对于之后的子任务,需要考虑多项式复杂度的算法。

不难分析出以下两个性质:

性质1 总是可以假设交换不相邻元素在第一次进行。

证明 假设交换不相邻元素时,交换的两个元素数值分别为 x,y ,那么去掉这次交换,在所有交换操作前添加一次交换数值为 x,y 的两元素的操作,可以得到同样合法且操作次数相同的方案。

性质2 如果已经交换了不相邻元素,之后的最小交换次数等于此时排列的逆序数,即满足 i<j h_i>h_j 的逆序对 (i,j) 个数。

证明 由于之后只能交换相邻元素,不妨设交换了 h_i h_{i+1} 。显然交换不影响无关 i i+1 的数对的顺序性。

对于形如 (x,i) (i,x) 的数对( x\ne i+1 ),交换后顺序性与 (x,i+1) (i+1,x) 相同;对于形如 (x,i+1) (i+1,x) 的数对( x\ne i ),交换后顺序性与 (x,i) (i,x) 相同。唯一顺序性发生变化的数对为 (i,i+1) ,因此新排列与原排列的逆序数之差为 [h_{i+1}>h_i]-[h_i>h_{i+1}] ,即当 h_i<h_{i+1} 时,逆序数增加 1 ,否则逆序数减少 1

由于当排列未排成升序时必存在相邻的逆序对,故可以每次交换一对相邻的逆序对直至排成升序,因此最小交换次数即为逆序数。

基于这两个性质,不难设计出这样的算法: O(n^2) 暴力枚举交换第一步哪两个元素,对每种第一步的交换用 O(n^2) 的时间计算逆序数。

时间复杂度: O(n^4)

期望得分: 33

算法四

求逆序数是一个经典问题,可以用分治法或者树状数组在 O(n\log n) 时间内解决。

这样就可以将算法三优化到 O(n^3\log n)

时间复杂度: O(n^3\log n)

期望得分: 41

算法五

我们发现每次求逆序数时,排列只有两个元素发生了改变,没必要整个数列再求一遍。

首先我们求出初始排列的逆序数 A ,然后枚举第一次交换的数对 (i,j) i<j ),即交换了 h_i h_j 。显然交换不影响无关 i j 的数对的顺序性。

对于形如 (x,i) (i,x) 的数对( x<i x>j ),交换后顺序性与 (x,j) (j,x) 相同;对于形如 (x,j) (j,x) 的数对( x<i x>j ),交换后顺序性与 (x,i) (i,x) 相同。

只有形如 (i,x) i<x\le j )和 (x,j) i<x<j )的数对顺序性发生改变,则新排列逆序数为

A'=[h_j>h_i]-[h_i>h_j]+\sum_{x=i+1}^{j-1}([h_j>h_x]+[h_x>h_i]-[h_i>h_x]-[h_x>h_j])

h_i<h_j ,则 A'=A+1+\sum_{x=i+1}^{j-1}2[h_i<h_x<h_j]

h_i>h_j ,则 A'=A-1-\sum_{x=i+1}^{j-1}2[h_j<h_x<h_i]

显然计算出初始排列的逆序数 A 之后,对每种第一次交换的情况,可以 O(n) 暴力计算出新排列的逆序数 A'

时间复杂度: O(n^3)

期望得分: 54

算法六

由于交换 h_i<h_j 的数对 (i,j) 是不优的(逆序数反而增加),故只需考虑满足 h_i>h_j 的数对。

我们把每个元素 h_i 看成二维坐标系中的一个点 (i,h_i) ,那么对于每一对 (i,j) h_i>h_j ),计算 \sum_{x=i+1}^{j-1}[h_j<h_x<h_i] 就是统计以 (i,h_i),(j,h_j) 为左上角和右下角,且边平行与坐标轴的矩形内有多少个点。

这是经典的二维数点问题,用可持久化线段树或者离线之后树状数组即可解决。

时间复杂度: O(n^2\log n)

期望得分: 61

算法七

算法六中使用数据结构其实是数据结构学傻了。

可以直接用二维前缀和的方法, O(n^2) 预处理每个点右上角有多少个点,用前缀和加减的方法可以 O(1) 查询矩形内的点数。

时间复杂度: O(n^2)

期望得分: 67

算法八

观察算法六建出的二维坐标系,我们可以进一步发掘性质:

性质3 总是可以假设第一步交换的数对 (i,j) 满足: (i,h_i) 的左上方没有点, (j,h_j) 的右下方没有点。

证明 如果 (i,h_i) 的左上方有点 (i',h_{i'}) ,那么把 i 换成 i' ,以 (i',h_{i'}),(j,h_j) 为左上角和右下角的矩形包含了更多的点。对于 j 同理。

于是可以预处理出两个点集 U D ,其中 U 中的点满足左上方没有点, D 中的点满足右下方没有点。这一步可以预处理序列 h 的前缀最大值 pre_i=\max_{j\le i}\{h_i\} 和后缀最小值 pos_i=\min_{j\ge i}\{h_i\} ,得到 U=\{i|h_i=pre_i\} D=\{i|h_i=pos_i\} 。于是可以假设第一步交换的数对 (i,j) 满足 i\in U j\in D

这一步有什么用呢?不难发现:

性质4 U D 中的点均满足 h_i i 单调递增。

证明 由于前缀最大值 pre_i 递增的,而所有 i\in U 满足 h_i=pre_i ,所以 U 中的点 h_i 关于 i 递增。对于 D 同理。

这个性质十分有用。考虑对于每个点 x ,有哪些数对 (i,j) 对应矩形包含点 x 。可以得到约束

i<x,j>x,h_i>h_x,h_j<h_x

l U 中满足 h_i>h_x 的最小 i r D 中满足 h_j<h_x 的最大 j ,由递增性,可以将上述约束写为

i\in[l,x-1],j\in[x+1,r]

这等价于点 (i,j) 在二维坐标系中以 (l,x+1) 为左下角, (x-1,r) 为右上角的矩形内。

用这种方法,我们可以将每个点转成一个矩形,其中 l r 可以简单地通过 O(n) 预处理 U D 中每个数的前驱后继以 O(1) 查询。

之后只需找一个被最多矩形覆盖的点,覆盖该点的矩形数目就是答案。将所有矩形按照下边界排序,然后从下往上扫描,遇到下边界时将矩形对应的横坐标区间加 1 ,遇到上边界则减 1 ,用线段树维护每个横坐标的覆盖数,整个过程中覆盖数的最大值就是答案。

时间复杂度: O(n\log n)

期望得分: 100

算法九

我们也可以发现对于两个左端点 l_i<l_j ,它们对应的最优的右端点满足 r_i<r_j ,即决策单调性。

我们可以直接分治转移,每次转移中点并递归到左右两侧。另外用一棵树状数组维护当前转移区间内的区间和。使用宽度优先顺序转移即可保证转移区间的端点移动总次数为 O(n\log n) ,总时间复杂度 O(n\log^2 n)

时间复杂度: O(n\log^2 n)

期望得分: 100

T4. 花札

By liu_cheng_ao,题解 By liu_cheng_ao

  • 考察选手的博弈论、二分图匹配和网络流知识。
  • 带约束二分图匹配 或 最大流
  • 思维难度:NOI+
  • 实现难度:NOI

为了渐进记号的使用方便,设 n = n_1+n_2 ,且有 m,c=O(n)

算法一

m = c = 1 时,所有牌都一样,谁的牌多谁赢。

时间复杂度: O(n)

空间复杂度: O(1)

预计得分: 9

算法二

n_1, n_2\le 10 时,由于牌的数量很少,考虑记录每张牌是否已经使用,状态压缩DP即可。

时间复杂度: O(n^2 2^n)

空间复杂度: O(2^n)

预计得分: 19

算法三

m,c \le 2 时,只有至多 4 种牌,于是可以分别记录每种牌的数量,DP即可。

时间复杂度: O(n^{mc})

空间复杂度: O(n^{mc})

预计得分: 20 ,结合前述可得 30

算法四

太长不看版:二分图匹配

前面几种方法太暴力了,我们需要找一个多项式复杂度的算法。

考虑图论模型:对每张牌建一个点,向能够作为它后继的点连边。由于能作为后继的条件是对称的,故这是一个无向图。另外,由于两个人交替出牌,这还是一个二分图。为了方便,不妨设神犇的 n_1 个点在左侧,LCR 的 n_2 个点在右侧。

于是题目变成了:初始时在二分图的一个点上,两人轮流沿着边走,不允许重复访问节点,不能移动者输。

这是个经典问题(Undirected Vertex Geography)。对于该问题有以下定理:

起点 v 是先手必胜的,当且仅当它在所有最大匹配上。

证:
必要性:若存在一个最大匹配 M 使得起点 v 不在其上,那么先手每次操作时,要么无路可走,要么走到了某个匹配点上(否则就找到了一条增广路)。于是,后手只要每次走到 M 中与该点匹配的点即可。
充分性:若 v 在所有最大匹配上:
我们有增广路定理的如下推论:对于无向图 G 和其任一最大匹配 M ,点 v 必定在最大匹配上,当且仅当对于 M v 在匹配上且不存在以 v 为一端的偶数长度交替路。
于是,我们取任意最大匹配 M ,现在先手把 v 移动到 M 中与之匹配的点上。那么由于不存在以 v 为一端的偶数长度交替路,移动后并删去点 v 的图中也不存在增广路,于是由增广路定理从 M 中删去先手走的边后仍然是最大匹配,且现在 v 在未匹配点上。于是情况和必要性证明中相同,先手必胜。

如果您不知道上面说的无向图匹配的知识,请参考这里

我们只需建出二分图,然后求出左侧每个点是否一定在最大匹配上。

可以这样求:删去这个点后求一次最大匹配,看与不删相比答案是否减小。

采用这种方法需要枚举 O(n) 次,二分图的点数和边数分别为 O(n) O(n^2) 。求最大匹配的算法复杂度 O(n^{2.5}) (HK、Dinic)到 O(n^3) (EK)不等。

或者用上下界网络流也可以得到类似复杂度的方法。

时间复杂度: O(n^{3.5})\sim O(n^4)

空间复杂度: O(n^2)

预计得分: 42\sim 55

算法五

太长不看版:二分图匹配后删点后重新增广

考虑优化求必定在匹配上的点的方法。

我们可以使用线性代数方法在 O(n^3) 或更小的时间复杂度内不确定地解决该问题,但由于常数过大很难通过 n=1000 的数据。考虑图论方法。

根据算法四中提到的增广路定理的推论,只需判断在匹配上的点是否存在以之为一端的偶数长度交替路即可。

现在考虑一个在匹配上的点 v ,要判断是否存在以 v 为一端的偶数长度交替路,可以删去点 v 并从 v 原来的匹配点开始找增广路,若能找到则存在。单次时间复杂度 O(n^2)

或者在网络流模型上退流也可以得到类似复杂度的方法。

时间复杂度: O(n^3)

空间复杂度: O(n^2)

预计得分: 55\sim 69

算法六

太长不看版:优化连边+退流

二分图上我们要连 O(n^2) 条边,这太多了,考虑优化连边数量:

为了减少边数我们使用网络流模型。对每个颜色和点数建立一个新点,我们这样连边:从源点 S 向左侧每个点连容量 1 的边;从左侧每个点向它的颜色和点数分别连容量 1 的边;从颜色和点数向右侧对应的每个点分别连容量 1 的边;从右侧每个点向汇点 T 连边。(以上均为有向边)

这样只要连 O(n) 条单位边就可以了。这样,点边和边数都是 O(n) 的,Dinic 算法可以获得很高的运行效率(一个上界是对于单位网络的 O(n^\frac{5}{3}) )。

仍然可以用退流来判断一个点是否一定在最大匹配中。这部分复杂度为单次 O(n) ,总共 O(n^2) ,是时间瓶颈。

时间复杂度: O(n^2)

空间复杂度: O(n)

预计得分: 84

算法七

太长不看版:Dinic+残量网络上搜索

考虑优化判断一个点是否一定在最大匹配中的方法。

注意到一个点 i 一定在最大匹配中等价于所有最大流中 S 到该点 i 的边有流量。

这个命题等价于:在某个最大流中 S i 的边有流量,且残量网络上不存在 S i 的路径。

证:
充分性:若残量网络上存在 S i 的路径,则将这条路径和 i S 的边取反即可得到一个新的, S i 无流量的最大流。
必要性:假设存在一个 S i 无流量的最大流,考虑该最大流与现在的最大流之差,每个点的流量必定平衡。于是由欧拉回路定理,该图必定可分解为若干简单环的和,取其中包含 S i 边的一个即可构造出原来残量网络上 S i 的路径。

故我们只需在残量网络上从源点开始搜索能到达的点即可。这部分时间复杂度 O(n)

另一个方法是建立二分图的交替路图,并分析每个点所能到达的点中是否有未匹配点。但直接利用这种方法判定的时间复杂度为 O(n^2) (二分图的边数)。不过利用和网络流图类似的优化方法也可降低图的边数,并解决本问题。

时间复杂度: O(n^\frac{5}{3})

空间复杂度: O(n)

预计得分: 100

共 7 条回复

__stdcall

O(n^2logn)都能出到1e5了? 要是告诉我是O(n^2logn)我也会做。。。

liu_cheng_ao

T4 latex已修

yfzcsc

T4的算法四有个地方latex打错了

OwenOwl

T1真就是一个打表+lower_bound题

WAAutoMaton

先Orz kczno1 t1题解好数学啊...我dp预处理一下然后二分答案就做完了(不过好像和kcz大爷的做法不太一样)。 t2题解真奇妙啊,考场上只会做离线做法,在线居然也是在线段树上做.. 人太菜t3t4只会打暴力...

kczno1

t2 O(qvlogq) q和v都出到1.5*10^4?

kczno1

t1不是暴力dp+二分答案吗