issue是云哥的小迷×呀

题解

未归档(1)

/ 注册

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

牛清楚的裙子

由于每条裙子被选中的概率相同,这点可以认为条裙子没有差异那么定义为已经穿过条裙子,为了达到终止条件,期望还需要穿几次意思是,选中穿过的裙子概率,选中没穿过的,然后本次也需要穿次裙子那么化简得到那么上面提到每条裙子无差异,可以认为被穿过的次数相等,所以除以一个每条裙子期望被穿过不难发现...

2021-01-05

3 651

2020牛客跨年ak赛 F.开心消消乐(括号匹配+预处理)

传送门这里只说的把,也就是暴力枚举删除区间似乎有更快的算法,以后再补当删除某段区间后,最终剩下一段前缀和一段后缀作括号匹配会自动消除对于一段序列来说消除的顺序是不影响最终的结果的不妨先对前缀做括号匹配,变成的形式对后缀也做括号匹配,变成的形式不难发现,此时能消除的只剩下前缀后面的...

2021-01-05

2 792

牛牛的反函数

传送门加入一直乘以二加上去的话只能构造到的时候就超过了所以需要考虑为奇数的情况的操作发现每一次递归下去都会让函数值也就是说,奇数和偶数的函数变换只是让函数值而已,那么显然是选择奇数的变换更优也就是说我们倒推回去,一直执行和就能得到最小的这么构造最优,预处理即可发现最大能构造到然而我这...

2021-01-03

2 611

阔力梯的树

人都傻了倒是模板,被的操作搞晕了... 返回一个大于等于查找元素的指针是的末尾位置,但是最后一个元素在末尾位置的前面当返回说明没找到这个元素至于这里用也是有原因的,因为编号不重复,否则需要使用回到这道题,维护每个点的结实度显然想知道一个点的结实度必须要把所有子节点的编号排成一个序列计算...

2021-01-01

2 730

CF1183F Topforces Strikes Back(贪心)

非常巧妙的题(然而有什么用嘛!!!!我又不会) 如果只选一个数,一定选最大的数 Ⅱ 如果选两个数和,一定选掉最大的那个数证明如下 ① 若只有一个数是的约数,那么拿去替换他 ② 若两个数都不是的约数,替换任何一个数都会时答案更优 ③ 若两个数都是的约数,那么最大就是综上所诉,选择最大的才是最优的...

2020-12-27

2 739

Special Matrices(DP的优化)

水过(写这么详细是不是50nb呀!!!) 状态似乎无法压缩,假如压缩需要是一个长位的三进制数,不可取难道就没法了吗考虑到问题的特殊性,在确定了前行后,每列只需要放一个或者两个设目前有列需要填充一个,有列需要填充两个那么有行可以去填充数字,我们来枚举这行转移是截至到第行填充后,还剩下列需要放...

2020-12-26

1 624

[SDOI2017]数字表格

这题其实并不难啊,有个结论比较显然下面推个狮子 #include <bits/stdc++.h> using namespace std; typedef long long LLL; const int N = 1e6 + 10, mod = 1e9 + 7, Mod = mo...

2020-12-26

1 720

Hacker, pack your bags!

传送门对区间按照左端点进行排序那么对于每条线段的右端点因为左端点是递增的m往右二分出一个区间的线段都是不相交的但是还需要找到固定长度的做法枚举每个线段,把这条线段当作右端的线段,去左端的线段里找最小值维护两个线段数组和按照区间左端点小到大排序,按照右端点小到大排序现在考虑线段和哪...

2020-12-25

0 683

每日一题: 小阳的贝壳(线段树维护差分数组)

传送门假设只有操作一和操作三操作一普通线段树可以完成,操作三普通线段树也能完成做法是维护一个数组表示节点表示区间的由于具有传递性,所以很容易维护。假如只有操作一和操作三操作一普通线段树可以轻松完成,操作二的话....势必要维护一个差分数组也就是令在线段树上维护这个数组的关系比如...

2020-12-25

2 729

牛客练习赛74 CCA的图(并查集贪心)

本来不算裸题,但是这个数据范围提示的太明显了先对边按照编号排序先保证最大那么我们的边从一直并查集合并,一旦连通就停下来那么这个一定是最大的现在我们要求最小那我们把并查集数组再次初始化,按顺序加边一旦连通就停下来,此时是最小的正确性显然....(不显然可以留言) #include &l...

2020-12-20

5 529