ryuuko_

题解

数学等结论(1)

/ 注册

全部文章 / 题解（共19篇）

kotori和糖果

递推题合并成一堆的最小代价肯定是分成尽可能相等的两堆再加上这两堆合并的代价(不是0就是1) 那么就这样一直递推下去设堆数为n，记合并代价为dp[n] 如果堆数是奇数那么dp[n] = dp[n/2] + dp[n/2 + 1] + 1 如果堆数是偶数那么dp[n] = 2 * dp[n...

递归

2025-02-27

0 25

数字魔法

去年新生赛预选题目赛时没做出来最小代价其实就是全部变到中位数但是这样需要排序因为本身数组不一定有序那么此时就陷入僵局了但是题目给了一个条件特别重要 1 <= a[i] <= 100 也就是说我最终要变到的中位数的值一定属于[1,100] 所以我可以预先处理a[i]的前n项全...

前缀和

2025-02-24

0 32

时间复杂度

其实题目分析起来还是很清晰的也就是判断循环中是否存在非法操作如果存在非法操作那么就输出ERR 否则就判断最大时间复杂度与所给是否相同相同输出Yes 不相同就输出No 非法操作就两种 1)F和E的数量不匹配这个很好做在循环中F的数量一定多于E 且结束时F，E的数量相同 2)循环出现相同的变...

模拟

2025-02-23

1 36

CF 333E Summer Earnings

题意：在一个平面内给出n(3 <= n <= 3000)个点的坐标，任选其中三个为圆心作半径相同的圆，要求这三个圆不能相交但可以相切，求能画出的圆中的最大半径暴力做法：三重循环枚举三个点，每次更新答案，直至找到最长的最短边但这样三重循环明显超时(虽然程序运行时间设定为了9s) 但其实...

枚举数学 bitset

2025-02-22

0 56

翻转游戏

还没讲完先记录一下目前想法她将灯的亮暗视为灯的两种状态记为1，0 例如一串灯的亮暗情况为： 1010，此时我给出一种按灯的方案(1记为按下开关，0相反) 1100，那么最终的结果应该是(1010)^(1100)^(1100 >> 1)^(1100 << 1) 这是因为...

数学枚举深度优先搜索

2025-02-22

1 55

丢手绢

一开始听课她说只需要从头到尾遍历一遍就可以但是现在想想好像不是这么一回事她的意思是每次j指针后移当累计长度len * 2 >= 总长度sum，这时候更新答案 ans = max(ans, min(len, sum - len)) 但是这样如果j移动到末尾元素(也就是重新回到起点)，此...

枚举双指针

2025-02-21

1 52

带权中位数

嗯这个没什么好记录的纯粹的结论但是在某些情况下需要对问题进行拆分才能使用假设一个数轴上有很多个点这些点上都有人要把所有人移动到同一个点上并且所移动的距离最短结论：将有人的点按大小排序再进行前缀和刚好超过总人数一半的那个点(假设总人数为sum 那么累加的人数>= sum / ...

数学

2025-02-21

0 72

中位数图

注意到只是要求以b为中位数的连续子序列，那么a[i]的大小就不重要了，只需要区分三种情况 a[i] > b 就将a[i] = 1 a[i] == b 就将a[i] = 0 a[i] < b 就将a[i] = -1 又由于这个连续子序列长度为奇数则在更改数值后满足题意的连续子序列的和就为...

数学枚举

2025-02-21

0 42

校门外的树(hard)

之前一直没有想到该怎么去写面对1e9的长度束手无策刚刚听课的时候反反复复听到区间二字一个奇妙的想法就出现在我的脑中既然一棵树只能被拔掉一次那么我只需要将所有区间合并设区间 [l[i], r[i]], 那么拔掉的树的颗数即为r[i] - l[i] + 1 对拔掉树的所有区间求和得到拔树的...

2025-02-19

0 44