牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共3篇）

数学专题测试4

A. 猜拳游戏看到这个数据范围多半是高斯消元。所以问题是如何处理出每局的胜率。容易发现平局是没有意义的，要求的是最大的胜/负，这是一个分数问题，无法进行简单加和。所以正确的做法是01分数规划。通过二分答案，将分母部分直接作减法。于是只要维护最大的分子-$k*$分母就可以了。 ...

dp 高斯消元二分答案多项式拉格朗日插值分数规划

2020-01-29

0 499

省选模拟17 题解

A. 选择可以发现问题是$a$ $b$是否在一个边双里。因为没有强制在线，所以将难处理的删边转化为加边。对于一棵树上的加边操作，只要将两个点之间的路径上的点，添加到同一个边双集合里即可。因为边双的特殊性质，加上并查集的操作，这样只考虑树边的做法是正确的。具体的实现方法实际上通过并...

多项式并查集线段树树链剖分拉格朗日插值二分答案矩阵树定理

2020-02-03

0 424

noi前第九场题解

A. s1mple 可以发现 0/1 这个限制类似于求路径数，使得路径经过的边权恰好合法。显然可以用容斥来求，这样可以将问题转化为钦定其中若干条边权为 \(1\)，其他边权任意的路径数。这样做有一个好处，原来问题中的 \(2^{n-1}\) 的集合可以缩减状态数。对于钦定之后的若干条 \(1...

dp 多项式后缀自动机拉格朗日插值启发式合并状压字符串

2020-07-21

0 379