R2A

A

判断$\underbrace{x…x}_{m} \mod k$ 是否等于$c$

同余 快速幂
$10^m - 1 = \underbrace{9…9}_{m} = \underbrace{x…x}_{m} /x * 9$
$\frac{x(10^m - 1)}{9} \pmod k = \frac{(10^m \mod 9k) - 1}{9} * x \pmod k$

用快速幂算$10^m$即可
复杂度$O(log(m))$

B

给定一个序列,一些数的位置给定,其数字任放,求$max{a_0a_1 + a_1a_2 + … + a_n-1a_n}$

状压dp
$d_{s,i}$ s记录当前取的数字集合,i为最后一个取的数字位置,注意若位置给定,则只能放在s中1的个数等于其位置的时候

复杂度$O(n^22^n)$

C

一棵树,n个点,每个点有一个权值,
m个修改/查询,修改某点的权值,查询从根节点(0)出发,经过结点k的的最大路径

dfs序线段树

我们以树的dfs序列建立线段树,维护根到每个结点的路径的值
每次更新即更新以某点为根的子树区间,查询即查询以k为根的子树区间。

复杂度$O((n+m)log(n))$

D

给定一段序列和一个公差集合D,每次可以删去一段公差在D内的等差序列
问最多可以删掉多少数字

区间dp
$dp_{i,j}$表示区间[i,j]的最优值
若$dp_{i,j} = j-i-1$,则可以将其视为空
每次转移即从$dp_{i+1,j-1}$ $dp_{i+1,j}$ $dp_{i,j-1}$
其中第一个公差在D内即可,后两个公差需和转移前的区间公差一致

复杂度$O(n^3)$

E

s_1 = B
s_2 = BBD
s_3 = BBDBBDD
s_n = s_n-1 + B + reverse(flip(s_n-1))
flip 即翻转B/D
s_2^1000[L,R]中的B的个数

迭代
通过观察,发现序列有特殊性质,而且这里只会计算到s_61
预处理出前61个s的len和B的个数
根据 s_n = s_n-1 + B + s_n-2 + D + s_n-2 来求

F

一个排列1-N,其分数为扫一遍,加上到目前位置的最小值,现给出一些偏序关系,求最大分数。

拓扑排序
直接拓扑排序,每次选则一个权值最大的节点开始扩展,把队列改成优先队列就行了

复杂度$O(E + nlog(n))$,$nlog(n)$为优先队列的复杂度,也可以用dfs,可以省去。

R2B

A

随机给一段序列,区间价值定义为区间最大值*最小值,求每个长度的区间的最大价值

单调栈 RMQ

先用单调栈预处理出每个值作为最小值的区间,然后再RMQ其区间最大值,求出其区间的价值
有一些区间没有取到,然后每个长度的区间的答案取比其长的区间的最大值
因为区间的最大值和最小值之间的值在两者之间,任取一个和最大值乘起来都比原来区间的价值大

当然,由于数是随机的,所以有很多均摊复杂度为$O(log(n))$的算法都可以过
比如递归遍历(最大(小)值位置,最小(大)值位置)的区间

B

最小乘积生成树

TBD

C

一个nxm的矩形中,每步可以从当前点移到其左下角的任意一个点,问从$(1,1)$到$(n,m)$的路径数

打表 组合数

打个表发现答案为$C(n-2+m-2,m-2)$

D

一个序列1-n,表示n个点,从一点走到与之相邻的点消耗为1,
现可以建立一个虫洞,可以消耗为0地从X走到Y
给m个点对,求使得运输的最大消耗最小是多少
(注意道路是双向的)

二分答案 不等式
我们设建立虫洞的两点为l,r,设最大消耗为d
则对于任意两点L,R 满足 $|L-l| + |R-r| \leq d$
这个不等式可以转化为4个不等式
$l+r \leq L+R+d$
$l+r \geq L+R-d$
$l-r \leq L-R+d$
$l-r \geq L-R-d$
二分d,现在我们即对于$R-L > d$的区间合并,判断l+r和l-r是否同时满足(即l,r是否存在)

E

一个序列,给定一些区间,求其中k个区间的交区间的最大和

滑窗 multiset
将区间按左端点排序,枚举左端点,每次向multiset中加入右端点,直到size >= k,
此时multiset中的最小值便是答案区间的右端点,更新答案
然后删除最小的值直到multiset的size == k

F

一个序列,每个数都不相同,问每个数在每个区间作为中位数的次数

暴力
枚举每个数,并统计其到左边和右边的每个位置比它大的数(++)和比它小的数(–)
最后答案为$\sum_{i+j=0}l_ir_j$ $l_i,r_j$ 表示比当前位置数大/小的个数 i 和 j