Knights of the Old Republic tag:  2300+cf kruskal，dp  题解： 这题的思路应该考虑利用kruskal的性质，即最小边若连着两个不相同的连通块，那么其他任意的边连接这两个连通块都不会优与这个最小边。 我们可以发现，通过这个性质去理解这题，可以使得连通块共享最小资源产武士的途径，也可以共享所有的武士数量。那么根据kruskal，我们要选择某条边，一定可以把之前所有的边都打通，使得之后的状态都更新到当前的状态下面。 代码：  ///here is jmr's codes ///if you want to copy,please call me 2...

(K. Keylogger)[https://codeforces.com/gym/103185/problem/K] [[TOC]] 目录 tag:  cf分段2100 动态规划，二分查找，计数，前缀差分  题意：  给定矩阵，对于矩阵第i行，每行都是上升子序列。 给定序列，求矩阵转移找满足序列的个数。  题解： 先寻找满足区间范围的数字，用的是两次二分，这样可以快速固定区间。 然后对于区间内静态查询动态修改，可以考虑使用前缀差分来加速。 最后就是滚动dp压缩空间，可以加快访问速度。 代码：  #include<bits/stdc++.h> using namespace std...

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]范围对于i而言除数结果是相同的，只要判定这个范围是否有数字，就判定一次k是否存在序列里即可。 因此这里要用一个简单的前缀和记录数字是否存在。 此时时间复杂度就是c∗log(c)c * log(c)c∗log(c) 代码： #include<bits/stdc++.h> using namesp...

(G. Remove the Prime)[https://codeforces.com/gym/103260/problem/G] tag:  cf2000 博弈，Pollard-Rho  题意： 对于连续序列，两个人执行操作，对[l,r]区间指定一个被这些数字都可以整除的质数，使得区间内所有数字被该素数除至不能再除 重复操作至所有数字变为1 先后手均使用最优解，求谁赢。  题解： 首先是考虑所有数字均做一次pollard-rho，求所有数字的质因数序列。 然后求所有质数的连续操作序列，记录长度。 此时我们就会得到一个小小的博弈状态。对于每个人都可以通过[l,r]操作变成下一个状态。这有点类...

(B. Repetitions Decoding)[https://codeforces.com/problemset/problem/1641/B] tag:  cf2000 构造模拟  题意： 给定序列，通过添加一堆两个相同的相邻数字构造相同子串，求构造过程  题解： 简单来说，这题其实就是找到一个简单的规律去消去相同的数字 我们不妨先把相同的最近两个数字先消去，要想消去这两个数字，就要在其中添加一系列数字 例如：1 2 3 1 2 3 我们要想消去1，那么可以这样构造 1 2 3 1 (2 ( 3 3 ) 2 ) 2 3 此时剩余 3 2 2 3 尽管肉眼检查发现已经可以了，但是我们依然...

交换 tag:  cf分段1800+ 字典树，哈希hash，枚举  题意： 给定连续操作序列，对于操作序列l，r，使其实现交换当前位置上的数字 给定一堆未完成的排列，利用连续操作序列使其变成顺序递增排列  题解： 这题最先通过连续操作序列这一点就能想到o(n2)o(n^2)o(n2)的枚举状态获得对应操作结果。 那么如果我们可以记录下所有操作对应的结果，然后通过逆向操作就能知道当前序列最后操作的结果是什么情况。 比如说我们操作 3 2 1，我们的一个连续操作序列可以使得原串 1 2 3 变成 3 2 1 ，那么他就可以使得原串为 3 2 1的序列变成 1 2 3 然后就是查询的问题 ，根据某沙...

金牌厨师 tag：  二分 前缀 差分 1900  题意： 有m个人，每个人可以拥有l-r区间的忍受值，k为选出的人，x为这些人可以忍受的最大区间。求min(k,x)的最大值。 求最小的最大，铁二分题了。 连续二字，必须要考虑到前缀和差分的相关性，可能可以成为突破口。 解： 二分答案，二分的主体是忍受范围的区间。其实这点是很难想到的。我们知道，如果考虑二分的人，是很难确定选择哪些人，但是如果把问题转变成二分容忍区间，就可以利用上差分的作用，创建出一些小的连续区间，代表在这些区间内，存在某些人的容忍度可行。 example：  ve[x[i].first + mid - 1] ++ ; ve[x...

炸鸡块君与FIFA22 tag:  2100 线段树 st表分块  题意： 给定一个长度为 n 的字符串，m 次询问，每次询问 [ l , r ] 区间以起始 s 分的最终得分 得分规则为遇到 W 加一分，遇到 D 分数不变，遇到 L 若此时分数不是 3 的倍数则减一分 解： 考虑线段树，一个线段树维护三个状态，分别代表到这场比赛的之前的分数对三的余数（0 1 2 ）。因此根节点的维护方案就是左区间值为右区间起点数值，左右区间之和减去多算的一次左区间终点余数得分。 因此查询也要左右分开查询，左边查询的结果作为右边的初始值。 #include <bits/stdc++.h> #def...

这题是一道比较反常的dp逆向思维解决问题的题。 刚开始思路局限于对逆元的处理，当视野不再放在逆元之后，把样例拿来模拟了一番突然发现了解题的关键。我们会发现，第一个样例和第二个样例如果可以通过模拟的手段解决，那么本题就找到了解决的方法。 对于样例，我们发现111有且只能被西瓜质量为222组成，进而推广，假设前面均为000，那么第一个出现的数字必然是一个西瓜劈成两半的结果。因为西瓜的数目控制在了1e31e31e3，因此不可能出现0但是有1e9+71e9+71e9+7个西瓜。依照此法，我们发现，接下来的解决方案依然是一个dp，也就是记录下个数，然后使用背包方案，每次的背包方案与原先比较，如果不为00...

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每次可选择+++还是−-−这个数。但+操作最少能做mmm次。 A需要最大值，B需要最小值。A选择的实数已知，求最终结果。两人均最优操作。 思路： 本题可以说是一道经典的博弈dp题，利用博弈+数学得到一个函数规划，然后通过函数规划推出动态规划的转移方程。 首先，发挥灵感，大胆下结论，这是一道dp。我们需要做的事情就很明确，就是构建转移方程。 将m=...

Trade 题目连接 tag：  背包dp 数学推导 超大容量背包 cf分段2100+ 铜牌题左右的背包问题  题意： 给定一些物品和钱s，购买物品数量为k时其他物品的价格会增长 当购买k件物品时，其他物品的价格为x[i] + p[i]*k 求最大购买物品量  很显然能想到是一个背包dp问题，但是数值是一个非常困难的问题。我们发现s其实非常大，所以从这里考虑就知道背包的第二维度肯定不是金钱而是物品个数。 那么问题就转化为了dp[i][j] = k 代表前i个物品中购买了j个物品，此时花费的最小值。 我们这里就要简单证明一下购买的物品在限定金额内不可能无限量购买，就要简单的计算一下按照最劣情况购...

小沙的remake（普通版） tag:  线段树，树状数组，dp cf分段1800+  两个题就一起讲了： 找到连续的，上升子序列且下标之差满足某个范围 求方案数  题目挺简单的，特别是你如果马上能利用dp计数方案的思维去思考这题，就会立马发现这题首先要做的一点就是存储下标+排序 排序完了之后就是寻找当数字之前且下标也在他之前的方案数量，存储到当前数字的下标的数组里。 这个维护手段就是树状数组，所以如果能把dp和树状数组结合起来，这题就是秒切了。 #include<bits/stdc++.h> using namespace std; namespace GenHelper { i...

牛妹的数学难题 tag：  逆元，组合数，前缀记忆 cf分段1900  题意： 已知一堆序列范围在0 1 2当中 求公式结果  公式如下： ∑i1=1n∑i2=i1+1n...∑ik=ik−1n∏j=1naij\sum_{i_1 = 1}^{n}{\sum_{i_2 = i_1+1}^{n}{...\sum_{i_{k} = i_{k-1}}^{n}{\prod_{j = 1}^n{a_{i_j}}}}}∑i1​=1n​∑i2​=i1​+1n​...∑ik​=ik−1​n​∏j=1n​aij​​ 方案采用枚举组合数的情况，本质上这题可以归结为 num2 = C(sum2,i)//这里表示从所有...

小y的序列 tag:  st表o1查询套二分 cf分段1800+  简单讲一下题意： 给定一个序列和k值 找到连续区间max-min = k的个数  解： 优先考虑st表，只要最大最小问题就先想一想能不能套st表。 然后发现，当起点固定的时候，他们的最大值是单调递增的，最小值是单调递减的。 有可能是单调队列，但我后面的想法更接近的是二分。 遵从单调性优先考虑二分。因此我立马反应过来这题的解法是二分+st表。 此时就要枚举起点，时间复杂度就成了o(nlogn)o(nlogn)o(nlogn) #include<cstdio> #include<cmath> #includ...