tanghg

分类

未归档(2) 题解(2)

/ 注册

全部文章（共4篇）

题解 | Change Matrix

题目大意维护一个阶矩阵，其中最开始，共有次操作，每次操作将矩阵某一行或某一列同乘一个数 ,求每一次操作后矩阵的所有元素之和。对取模。，且保证数据随机生成。思路根据欧拉函数的性质，有则考虑维护个矩阵，的大小为，表示的是在其中一个因数为时另一个要满足的因数的系数...

C++ 数学

2024-08-14

5 137

题解 | A Cake

首先先考虑第二部分。发现对于后手来说是十分被动的，对于能拿的希望拿的多一点，但最终能拿多少全部取决于先手。发现双方的利益取悦于找到一个使得平均分成份让其中的占比最大。则我们维护树上每一个节点边的最优前缀表示其中走到这里选和选的期望占比。其中要取，要取，因为第二部分的选择权...

C++ 博弈论深度优先搜索

2024-08-01

5 137

浅谈珂朵莉树

珂朵莉树珂朵莉树（老司机树/ODT）是一种由李欣隆发明的暴力数据结构，在随机数据下表现良好。珂朵莉树主要用于有着大量区间推平操作的题目，但是在构造数据下表现十分不好。如果区间推平操作较多，则单一操作的时间复杂度为 \(O(\log_2n)\)。在特殊构造下，单一操作则会退化成 \(O(n\log...

2023-12-15

0 0

浅谈 KMP

符号规定先来规定一些符号。 \(\lvert S\rvert\) 代表这个字符串 \(S\) 的长度。 \(S_{l\cdots r}\) 代表字符串从第 \(l\) 个字符到第 \(r\) 个字符组成的字串。 \(F(S,i)\) 等同于 \(S_{1\cdots i}\)（就...

2023-12-13

0 0