K0u1e

分类

学习笔记(1) 题解(13)

/ 注册

全部文章（共12篇）

新技能Splay

新技能Splay 平衡树这种东西很是玄学，操作倒是十分明了就是不知道为什么这么整能有一个合理的复杂度，至少我已经了解过的Treap和Splay就给我这种感觉。大概的思想就是通过把访问的节点旋到根节点使得每条路径都多多少少发生些变化，从而防止对同一条很长的路径多次重复访问，复杂度是据说均摊的。洛谷P...

2020-02-06

0 873

Codeforces Round #588 (Div. 1)

前言寒假康复训练Day1，差点爆零了qwq。题解 C - Konrad and Company Evaluation 题目要求维护，修改是把指向某个点的入边全部改成出边。考虑对点按照度数不升序排序，那么我们尝试分成两部分来做。1.对于位于左边的点，与相连的点必不可能超过。若超过，则说明有超过个点...

2020-01-08

0 969

Educational Codeforces Round 78 (Rated for Div. 2)

前言挺好一开局，要是D没被卡能把E也写了说不定还能上橙，可惜。题解 F - Cards 题目要求把分母拿掉，只考虑分子。根据第二类斯特林数的性质有代入上式得交换求和得把组合数拆开得化简得再给后面的组合数乘点东西于是就变成了用替换，得到最终的式子为第二类斯特林数预处理,求解。

组合数学

2019-12-20

0 962

Codeforces Round #606 (Div. 1)

前言可能当场上橙的场次，字符串防题根本看不到啊，虽然赛后也写了好久qwq。题解 D - Tree Elimination 等价于求不同操作序列的个数，考虑树形。令为以为根的子树在节点的删除情况为的方案数，为的父亲。共三种：，在遇到节点前被删除。，在遇到节点时被删除。，在遇到节点后被删除。...

树形dp

2019-12-17

0 814

Codeforces Round #604 (Div. 1)

前言离橙名最近的一场题解 A - Beautiful Regional Contest 金牌只给题数最多的，然后尝试把剩下两组分成两份，每一份都比金牌人数多。 B - Beautiful Sequence 左边中间右边这样构造。 C - Beautiful Mirrors with querie...

费用流概率期望贪心构造 stl 组合数学

2019-12-06

0 789

Codeforces Round #594 (Div. 1)

前言自闭场。题解 A - Ivan the Fool and the Probability Theory 玩一会儿（一个小时）数据以后发现答案等价于用和组成答案为或的加法式子的方案数。

2019-11-28

0 871

Codeforces Round #599 (Div. 1)

前言签到即结束，当场暴毙。题解 A - Tile Painting 若只有一个质因数，则答案为该质因数。若有两个以上质因数，则答案为. B - 0-1 MST 显然答案为，然后我就自闭了。维护一个链表记录未被访问过的点。然后对每个未被访问过的点进行。假设当前访问到，枚举下一个点的时候就遍历这个链...

状态压缩数论搜索动态规划

2019-11-26

0 1000

Codeforces Round #569 (Div. 1)

前言 Hape线段树题调一年我真是佛辣。题解 A - Valeriy and Deque 发现次操作后，最大元素一定在队列顶部，这之后的每次操作就是将第二个元素放到队列尾，因此模拟前次操作即可。 B - Tolik and His Uncle 对于最左边的一列和最右边的一列考虑如下构造法，从两边往...

斜率优化模拟构造线段树树形dp

2019-11-25

0 818

Codeforces Round #602 (Div. 1)

前言康复训练Day3掉分辣，心疼死辣，区间翻转一生之敌。题解 A - Messy 我的做法太憨了就8说了。赛后学长说次操作可以构造任意一个括号序列，每次操作一定可以在一个位置上放上你想放的左/右括号，所以就构造就完事了。 B - Optimal Subsequences 优先选值大的，如果值相等...

构造主席树平衡树二分组合数学

2019-11-24

0 1127

Codeforces Round #596 (Div. 1)

前言康复训练Day2。wdnmd又双叒叕是赛后1A。题解 A - p-binary 考虑是否存在使得能被表示成个之和，即二进制表示中的个数小于等于且本身大于等于。暴力枚举就行辣。 B - Power Products 用一个长度为的记录每个数小于的质因子的次数对取模的情况，并根据剩余的最大质因子...

stl 动态规划贪心

2019-11-22

0 784