rprp

分类

动态规划(12) 图论(6) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 贪心(5) 配置(2)

/ 注册

TA的专栏 1篇文章 0人订阅

1篇文章 660人学习

全部文章（共55篇）

CF1060F Shrinking Tree 题解来自专栏

考试题目的小数版本可以先考虑一个暴力，就是枚举一个点作为最后的点，然后枚举一个删边的序列。这个暴力显然比朴素的暴力复杂度要优秀一点。考虑基于这个思想来写题。可以枚举一个点作为最后的点，然后出所有的删边序列。算出在这个序列下点保留下来的概率，然后把所有的概率加起来，除以也就是左右序列的个数就是...

dp

2020-11-23

0 660

李超线段树复习笔记

复习笔记就离谱好吧用途大概是给你一个序列，然后插入一条线段，然后查询某一个位置上与所有线段交点的纵坐标的的最大值或者最小值。然后就没了。实现定义一个区间的"优势线段"为在这个区间里面有超过一半的点在这个线段上取到最值。考虑维护一个线...

李超线段树

2020-11-20

0 538

Luogu 3748 [六省联考2017]摧毁“树状图”

题目大意：求两条树上边不相交路径，使得删掉这两条路径上的点以后剩下的连通块数量最多。做法两条路径在树上大概会长成两个倒着的‘V’字形，考虑在某一个'V'的最上面那个点统计答案。于是统计答案的时候我们发现有几种统计法：父节点有一个'V'，子节点有一个'V‘。父节点...

2020-11-20

0 475

[CQOI2017]老C的键盘

发现题目给的很像一棵树。。。就把这棵树建出来。发现如果把大于小于号分别看成一条有向边，发现这个题目就是求这个图有多少个拓扑序。对于每一个拓扑序，直接$$12345$$这样标号就可以得到满足题目要求的序列。考虑树\(dp\), 设\(f(i, j)\)为\(i\)这个点在这个子树所形成...

dp

2020-10-15

0 492

题解 [AGC030F] Permutation and Minimum

我们把位置在\((2i - 1, 2i)\)的两个点叫做一对点。显然如果这对点两个都被限定了直接丢掉完事。如果有一个没有被限定就先留下来。注意到其他的形如\((-1, -1)\)的顺序是可以随便变化的，所以先不考虑，最后乘上一个阶乘就可以了。考虑用\(f(i, j, k)\)表示...

dp

2020-10-14

0 480

题解 AGC029E Pairing Points

考虑\(1\)号点向外连出一条边之后，整个圆被分成两个部分，每个部分肯定是内部连边然后一个点连一条边出来跨越一号点连出的那一条线。考虑对这种形状的部分进行\(dp\)。设\(f(i, j, k)\)表示\([i, j]\)这个区间内部匹配， \(k\)点向外连接的方案数， \(g(i,j,...

dp

2020-10-14

0 499

题解 [AGC028D] Chords

首先，按照boshi巨佬的说法，考虑每种联通块的出现次数。如果可以求出，答案就是每种联通块的出现次数和。再按照boshi巨佬的说法，一种定义联通块长相的方法是用编号最小的点和编号最大的点表示。于是设\(f[l][r]\)为\(l, r\)连通且外面的点不连接到里面的点，里面的所有边...

容斥 dp

2020-10-14

0 549

题解 luoguP5466 【[PKUSC2018]神仙的游戏】

显然要是没有限制那就全都是\(1\)对吧，所以考虑这些\(0, 1\)到底限制了啥。首先看到\(border\), 容易想到当年写\(kmp\)求最短回文子串的那题。因为\(kmp\)的\(next\)数组实际上就是最长\(border\)。我们也在那题积累一个结论，就是对于原来的串一个长...

kmp NTT

2020-08-18

0 443

题解 P4233 【射命丸文的笔记】 && 考试T3

考虑每一条哈密顿回路在所有竞赛图中的出现次数。发现如果确定一个环，其他的边乱选就可以保证出现哈密顿回路。所以对于一条哈密顿回路，出现次数为\(2^{C_n^2-n}\), 减去的\(n\)为那\(n\)条边。哈密顿回路是\(1-n\)的一个排列首尾拼在一起，共有\(n!/n\)种。于是总...

计数多项式求逆

2020-08-14

0 503

图论学习（在更）

note: 最小环是枚举已有的最短路和k点连接的两条边，保证三个点不重合。 for(R int k = 1; k <= n; k ++) { for(R int i = 1; i < k; i ++) for(R i...

图论

2020-08-11

0 541