动态规划
字符串
杂题
A:Animals and Puzzle
B:Vanya and Treasure
根号分治。
实际上是从 ((1, 1)) 先找一个 (1)，再找一个 (2dots) 最后找一个 (p) 然后
依次按最短路走过去。
我们有两种想法， 直接 BFS 递推得到当前点到所有点的距离 或者 直接暴力枚举两个层之间的所有点对， 两种做法的时间复杂度 都是 (O(n^2 m^2))。
考虑缝合， 经过一番神秘的复杂度分析， 我们得到了 (O(nm sqrt{nm})) 的优秀算法。
D:Awesome Substrings
根号分治。
令 (s_i) 表示 (sumlimits_{1}^{i}a_i)， 且 枚举的倍数为 (d)， 则有 (r - l = d times (s_r - s_l))。
直接暴力做是 (O(n^2))， 且不好优化。 我们考虑分块计算的思想， 设阈值为 (T)。
当 (d in [1, T]) 时， 将原式变形可得 (d times s_r - r = d times s_l - l)， 我们设 (f(i, d) = d times s_i - i)， 对于每个 d 可以求出 $ f(0...n, d)$ 的值。 对于每个值 (x)，若有 (k) 个 (i) 满足 (f(i, d) = x)， 它都会对答案产生 (tbinom{k}{2}) 的贡献。 这一部分可以做到 (O(nT)) 的实现。
当 (d in (T, n]) 时， 将原式变形可以得到 (s_r - s_l = dfrac{r - l}{d} < dfrac{n}{d}) ， 即有贡献的 ((a, b)) 对应的区间中 (1) 的个数 (k < dfrac{n}{d})。 因此我们对于每个 (l, k) 找到 (r) 的范围， 其对答案的贡献为 (lfloor dfrac{r - i}{k} rfloor - lfloor dfrac{l - i}{k} rfloor) ， 再减去 (d le T) 的部分。 这一部分可以做到 (O(nfrac{n}{T}))
总时间复杂度为 (O(nT + nfrac{n}{T}))， 当 (T = sqrt{n}) 时最优。
E:PolandBall and Gifts
若将送别人礼物看做一条有向边， 那么排列 p 所形成的是 一些闭合的有向环。 一个人收到礼物当且仅当一条有向边所连接的两个人都带了礼物。
先考虑最大化。 假定环的大小为 k， 对于一个奇环， 当有 (dfrac{k + 1}{2}) 个人不带礼物时， 这 k 个人收不到礼物； 对于一个偶环， 当有 (dfrac{k}{2}) 个人不带礼物时， 这 k 个人收不到礼物。
一个不带礼物的人最多可以影响两个人， 我们考虑尽量使每个不带礼物的人的影响最大。 而对于任意环， 只需要 (lfloor frac{k}{2} rfloor) 个不带礼物的人即可将 可以影响两个人的点位 占满。 我们令 (ans2 = sumlimits{lfloor dfrac{siz[i]}{2} rfloor})， (siz[i]) 表示环的大小。 当 (ans2 >= m) 时， 每个不带礼物的人都能占据一个 影响两个人的点位；
否则的话， 剩余的人就占据奇环上只能影响一个人的点位。
再考虑最小化。 对于一个大小为 (k) 的环， 当环上有 (k) 个不带礼物的人 与 有 (k - 1) 个不带礼物的人都只会造成 (k) 个人得不到礼物。 故而， 将一个环完全占满更优。 原题即转化为 判断是否能找到几个环 使 他们的大小和 为 (m)， 如果能， 答案即为 (m)， 否则的话， 否则，忘带礼物的人的形式就是若干个环加上一条链，而这条链的尾部会有一个虽然带了礼物，但是收不到礼物的人。所以答案就是 (m + 1)。
F:Nastya and Time Machine
构造。
不难发现， 经过节点次数的下界是所有节点的度数的最大值(类比于菊花)。 如何构造出满足下界的答案？
为了方便构造，若进入节点 (x) 的时间点为 (t_x)，则离开节点 (x) 的时间点必须为 (t_x - 1) (这样返回节点 x 的父节点时间点就为 (t_x))
在遍历节点 x 的所有子节点时可能会有如下两种情况：
-
(t_x + deg_x < maxdeg) 则过程中不会超过答案，只需遍历结束后将时间回到 (t_x - 1) 即可。
-
(t_x + deg_x ge maxdeg) 过程中会有某一个节点的时间点超过答案。因为总共会占用 (deg_x + 1) 个时间点，因此当过程中的标号达到 maxdeg 时只需回到 (maxdeg − deg_x) 的时间点即可。
G:Andryusha and Nervous Barriers
直接正向模拟很困难， 考虑从另一个角度解题。
我们可以将板子看成从高到低依次插入得到的， 这样的话， 我们可以不用在意板子 和 球的高度， 只需关注他们的横坐标即可。
那么此时， 一个板子的作用实际上是 求出 一定区间中球的个数 (x), 并使区间两端点 (+x), 将区间(除去端点)赋值为 (0) 。
考虑到球在一定高度下落可能会砸碎板子这一因素， 我们对于不同组的球再记录一个参数 表示他们下降的高度， 用 优先队列 来对高度进行排序。
我们考虑设计一个函数， 询问一定区间内所有 不足以砸碎当前板子的球的个数。 由于对每个横坐标不同的点都需要查找一次优先队列， 时间复杂度过高。
考虑维护一个变量记录区间最小值， 当区间最小值大于 坚固程度时直接返回， 这样和区间取模类似， 在数据随机条件下时间复杂度有保证。
H:Omkar and Landslide
结论题。
-
对山的调整顺序并不影响最终的结果， 且停止时有 (h_{i + 1} - h_i in {0, 1})。
-
可以证明， 停止时 (h_{i + 1} - h_i) 最多有一个为 (0), 其他的为 (1)。
这样的话， 对于一个 n 和 h， 就可以直接确定最终的答案。
J:Goodbye Souvenir
首先， 由于区间中一种数只会计算一次贡献， 那么我们要求的 (last_x - first_x = sumlimits_{i in [L, R]}^{a[i] = x} i - pre_i)， 这是因为对于中间的部分而言， 令 (j) 为下一个位置满足 (a[j] = x) 的下标， 则 (pre_j = i)， 那么 (i - pre_i + j - pre_j = j - pre_i)
那么此时， 我们可以具化出两个不等式， (i le R) ， (pre_i ge L)， 在加入一个时间轴， 即三维偏序。
具体的， 我们有 (set) 来维护每个值的前缀， 修改一个数时需要修改以当前数为前缀 数据。
K:Sources and Sinks
Q:Omkar and Time Travel
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
