K0u1e
K0u1e
全部文章
分类
学习笔记(1)
题解(13)
归档
标签
去牛客网
登录
/
注册
K0u1e
Phew~
全部文章
(共12篇)
新技能Splay
新技能Splay 平衡树这种东西很是玄学,操作倒是十分明了就是不知道为什么这么整能有一个合理的复杂度,至少我已经了解过的Treap和Splay就给我这种感觉。大概的思想就是通过把访问的节点旋到根节点使得每条路径都多多少少发生些变化,从而防止对同一条很长的路径多次重复访问,复杂度是据说均摊的。 洛谷P...
2020-02-06
0
871
Codeforces Round #588 (Div. 1)
前言 寒假康复训练Day1,差点爆零了qwq。 题解 C - Konrad and Company Evaluation 题目要求维护,修改是把指向某个点的入边全部改成出边。考虑对点按照度数不升序排序,那么我们尝试分成两部分来做。1.对于位于左边的点,与相连的点必不可能超过。若超过,则说明有超过个点...
2020-01-08
0
967
Educational Codeforces Round 78 (Rated for Div. 2)
前言 挺好一开局,要是D没被卡能把E也写了说不定还能上橙,可惜。 题解 F - Cards 题目要求 把分母拿掉,只考虑分子。根据第二类斯特林数的性质有 代入上式得 交换求和得 把组合数拆开得 化简得 再给后面的组合数乘点东西 于是就变成了 用替换,得到 最终的式子为 第二类斯特林数预处理,求解。
组合数学
2019-12-20
0
960
Codeforces Round #606 (Div. 1)
前言 可能当场上橙的场次,字符串防题根本看不到啊,虽然赛后也写了好久qwq。 题解 D - Tree Elimination 等价于求不同操作序列的个数,考虑树形。令为以为根的子树在节点的删除情况为的方案数,为的父亲。共三种: ,在遇到节点前被删除。 ,在遇到节点时被删除。 ,在遇到节点后被删除。...
树形dp
2019-12-17
0
812
Codeforces Round #604 (Div. 1)
前言 离橙名最近的一场 题解 A - Beautiful Regional Contest 金牌只给题数最多的,然后尝试把剩下两组分成两份,每一份都比金牌人数多。 B - Beautiful Sequence 左边中间右边这样构造。 C - Beautiful Mirrors with querie...
费用流
概率期望
贪心
构造
stl
组合数学
2019-12-06
0
786
Codeforces Round #594 (Div. 1)
前言 自闭场。 题解 A - Ivan the Fool and the Probability Theory 玩一会儿(一个小时)数据以后发现答案等价于用和组成答案为或的加法式子的方案数。
2019-11-28
0
867
Codeforces Round #599 (Div. 1)
前言 签到即结束,当场暴毙。 题解 A - Tile Painting 若只有一个质因数,则答案为该质因数。若有两个以上质因数,则答案为. B - 0-1 MST 显然答案为,然后我就自闭了。维护一个链表记录未被访问过的点。然后对每个未被访问过的点进行。假设当前访问到,枚举下一个点的时候就遍历这个链...
状态压缩
数论
搜索
动态规划
2019-11-26
0
997
Codeforces Round #569 (Div. 1)
前言 Hape线段树题调一年我真是佛辣。 题解 A - Valeriy and Deque 发现次操作后,最大元素一定在队列顶部,这之后的每次操作就是将第二个元素放到队列尾,因此模拟前次操作即可。 B - Tolik and His Uncle 对于最左边的一列和最右边的一列考虑如下构造法,从两边往...
斜率优化
模拟
构造
线段树
树形dp
2019-11-25
0
817
Codeforces Round #602 (Div. 1)
前言 康复训练Day3掉分辣,心疼死辣,区间翻转一生之敌。 题解 A - Messy 我的做法太憨了就8说了。赛后学长说次操作可以构造任意一个括号序列,每次操作一定可以在一个位置上放上你想放的左/右括号,所以就构造就完事了。 B - Optimal Subsequences 优先选值大的,如果值相等...
构造
主席树
平衡树
二分
组合数学
2019-11-24
0
1123
Codeforces Round #596 (Div. 1)
前言 康复训练Day2。wdnmd又双叒叕是赛后1A。 题解 A - p-binary 考虑是否存在使得能被表示成个之和,即二进制表示中的个数小于等于且本身大于等于。暴力枚举就行辣。 B - Power Products 用一个长度为的记录每个数小于的质因子的次数对取模的情况,并根据剩余的最大质因子...
stl
动态规划
贪心
2019-11-22
0
782
首页
上一页
1
2
下一页
末页