牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共14篇）

省选模拟41 题解

A. 要换换名字显然二分一个答案，然后问题转化为二分图中是否存在一组完美匹配。然后发现，如果一个字符串的子序列个数超过 $n$ ，那么就没有必要接着连边了。所以对每个字符串建出不超过 $n$ 条边，然后跑个网络流就完事了。 B. 动态半平面交因为太菜了，所以只会用一些套路来做...

数学二分图二分答案差分网络流线段树

2020-03-09

0 359

省选模拟59 题解

A. 杨柳考虑实际上有这样一个结论，棋子之间是互不干扰的。可以使得最优方案上不存在两个棋子中途碰上的情况。然后问题就是一个二分图最小匹配，一个简单的想法就是 bfs 然后跑一个费用流，点数不多，边数很多。另外一个做法是直接在原图上建图跑个费用流，点数很多，边数不多。经过实验，只有...

区间dp 二分图 tarjan dp 网络流

2020-04-01

0 336

省选模拟72 题解

A. 新访问计划 B. 计算几何其实题中这个常数 $c$ 的定义很奇怪，所以大概可以猜想，对于所有的情况都是有解的。然后有这样一个做法，考虑弄一条直线出来，然后把 $n$ 条线段的对应端点都映射到这条直线上。比如坐标系上的点 $(x,y)$ 映射到倾斜角为 $a...

矩阵树定理计算几何分治二分图网络流线性代数凸优化

2020-04-16

0 405

省选模拟87 题解

A. a 直接构造一个简单的生成函数，就转化为求 $A^n(x)$ 的前 $x$ 项系数。一个很神奇的解决多项式 $A^n(x)$ 前 $n$ 项系数的做法。复杂度为 $O(nk)$，其中 $k$ 为 $A(x)$ 的项数。做法是这样的，对 $A^{n+1}(x)$ 分别用乘法 $A(...

网络流构造题二分图多项式

2020-05-04

0 402