猫猫是战旗小家伙

分类

题解(15)

/ 注册

全部文章（共15篇）

题解#Knights of the Old Republic#

Knights of the Old Republic tag: 2300+cf kruskal，dp 题解：这题的思路应该考虑利用kruskal的性质，即最小边若连着两个不相同的连通块，那么其他任意的边连接这两个连通块都不会优与这个最小边。我们可以发现，通过这个性质去理解这题，可以使得连通...

C++ 数学动态规划最小生成树

2022-03-07

0 356

题解#K. Keylogger#

(K. Keylogger)[https://codeforces.com/gym/103185/problem/K] [[TOC]] 目录 tag: cf分段2100 动态规划，二分查找，计数，前缀差分题意：给定矩阵，对于矩阵第i行，每行都是上升子序列。给定序列，求矩阵转移找满足序列的...

C++ 动态规划二分查找

2022-03-07

0 596

题解#B. Integral Array#

B. Integral Array tag: cf2000 数论分块，调和级数前缀和，桶排题解：这题我们可以通过枚举，把所有c上的数字都跑一边，寻找是否存在结果。这时候我们就发现，对于第i个数字，他的[i∗k−1,i∗k−i][i*k - 1,i*k-i][i∗k−1,i∗k−i]范围对...

C++ 数学

2022-03-07

1 609

题解#G. Remove the Prime#

(G. Remove the Prime)[https://codeforces.com/gym/103260/problem/G] tag: cf2000 博弈，Pollard-Rho 题意：对于连续序列，两个人执行操作，对[l,r]区间指定一个被这些数字都可以整除的质数，使得区间内所有数字...

C++ 数学博弈论

2022-03-07

0 753

B. Repetitions Decoding

(B. Repetitions Decoding)[https://codeforces.com/problemset/problem/1641/B] tag: cf2000 构造模拟题意：给定序列，通过添加一堆两个相同的相邻数字构造相同子串，求构造过程题解：简单来说，这题其实就是找到...

C++ 模拟枚举递归

2022-03-07

0 586

题解#小白月赛-交换#

交换 tag: cf分段1800+ 字典树，哈希hash，枚举题意：给定连续操作序列，对于操作序列l，r，使其实现交换当前位置上的数字给定一堆未完成的排列，利用连续操作序列使其变成顺序递增排列题解：这题最先通过连续操作序列这一点就能想到o(n2)o(n^2)o(n2)的枚举状态获得对...

C++ 字符串模拟字典树随机化枚举

2022-03-07

2 460

金牌厨师

金牌厨师 tag：二分前缀差分 1900 题意：有m个人，每个人可以拥有l-r区间的忍受值，k为选出的人，x为这些人可以忍受的最大区间。求min(k,x)的最大值。求最小的最大，铁二分题了。连续二字，必须要考虑到前缀和差分的相关性，可能可以成为突破口。解：二分答案，二分的主体是忍...

C++ 二分查找前缀和

2022-03-07

0 383

炸鸡块君与FIFA22

炸鸡块君与FIFA22 tag: 2100 线段树 st表分块题意：给定一个长度为 n 的字符串，m 次询问，每次询问 [ l , r ] 区间以起始 s 分的最终得分得分规则为遇到 W 加一分，遇到 D 分数不变，遇到 L 若此时分数不是 3 的倍数则减一分解：考虑线段...

C++ 线段树

2022-03-07

1 513

智乃买瓜（another version）

这题是一道比较反常的dp逆向思维解决问题的题。刚开始思路局限于对逆元的处理，当视野不再放在逆元之后，把样例拿来模拟了一番突然发现了解题的关键。我们会发现，第一个样例和第二个样例如果可以通过模拟的手段解决，那么本题就找到了解决的方法。对于样例，我们发现111有且只能被西瓜质量为222组成，进而推广...

C++ 动态规划

2022-03-07

0 315

D1. Game on Sum (Easy Version)

D1. Game on Sum (Easy Version) tag： 2100 dp 博弈game 数学时间复杂度 o(n∗m)o(n*m)o(n∗m) 题意：有nnn次操作，博弈先手A每次操作可以枚举0−k0-k0−k中任意一个实数，后手B每次可选择+++还是−-−这个数。但+操作最少能...

C++ 动态规划博弈

2022-03-07

0 462