rprp

分类

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

/ 注册

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

1篇文章 668人学习

全部文章（共5篇）

CF1060F Shrinking Tree 题解来自专栏

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

dp

2020-11-23

0 668

题解 [AGC028D] Chords

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

容斥 dp

2020-10-14

0 553

题解 AGC029E Pairing Points

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

dp

2020-10-14

0 508

题解 [AGC030F] Permutation and Minimum

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

dp

2020-10-14

0 491

[CQOI2017]老C的键盘

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

dp

2020-10-15

0 505