牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共23篇）

省选模拟15 题解

A. 倒计时考虑50%的部分分。分块来削这个数。后四位形成一块，预处理出9991~9999在前五位的最大值为0~9情况下分别会削到的值和削的次数。对于零散的后四位暴力削，这样就可以通过根号预处理，根号削$n$了。容易发现，对于$n$比较大，我们多分几次块，每次用较小一级的块来预处...

网络流后缀自动机分块容斥

2020-02-02

0 366

省选模拟22 题解

A. 遮天蔽日学习了计算几何相关的很多新技巧。求过一点$P$，圆$O$的切线：通过两点距离、半径，用反三角函数可以解得一个角度，然后就可以算了。求直线$PQ$，与圆$O$的交点：作点$O$关于$PQ$的垂线，通过半径和垂线长度，可以算得垂足与交点的距离，然后就可以算了。求多边形的重心...

回文自动机网络流 manacher 计算几何

2020-02-09

0 388

省选模拟35 题解

A. two 考虑现在要通过蓝边删掉红边。其实等价于要找出有哪些红边，满足恰好只有一个端点在蓝边的儿子方向子树中。考虑对蓝树跑出一个 $dfs$ 序来，那么问题转化为恰好一个端点在给定区间中。这像是一个二维偏序问题。考虑以线段树下标为其中的第一维，第二维进行排序处理。然后用一个 $...

单调指针点分治多项式二分图网络流线段树

2020-03-02

0 334

省选模拟40 题解

A. 染色问题考虑对每条边 $(a,b)$ 附加两种边权 $(x,y)$ 。对于一种染色方案，当 $col_a=col_b$，边权为 $x$，否则边权为 $y$。取 $x=1,y=0$，一种染色方案的贡献是所有边权的乘积，那么答案就是对于每种染色方案的贡献的和。发现这个玩意可以合并。...

组合计数状压网络流二项式反演

2020-03-08

0 754

省选模拟41 题解

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

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

2020-03-09

0 359

省选模拟51 题解

A. 数学利用本题的特殊性质，可以得到如果 $n$ 为奇数，那么答案为 $(ab)^{\frac{n+1}{2}}$ ，对这个玩意平方一下即可发现是对的。对于 $n$ 为偶数，可以把 $2$ 全都提取出来，然后对剩余的部分取得一个解。然后不断缩小 $2$ 的次数以迭代，当缩小为 $2^0...

数学构造题 dp bitset 网络流

2020-03-22

0 410

省选模拟59 题解

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

区间dp 二分图 tarjan dp 网络流

2020-04-01

0 336

省选模拟71 题解

A. 王子这个数据范围加上很奇怪的限制，其实就应该是网络流了。可以首先钦定选择了 $A$ 类，然后将其中的一些替换为 $B$ 类。其实与志愿者招募那个题挺像的，只不过原来是对于每个点选择 $[l,r]$ 个区间。但是现在的问题是要求每个区间选择 $[l,r]$ 个数点。其实并不难...

网络流分块 trie树 AC自动机线段树 set

2020-04-15

0 477

省选模拟72 题解

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

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

2020-04-16

0 405

省选模拟73 题解

A. 决战因为把暴力放过去了，所以这题就成水题了。其实正解的做法与那道求匹配方案权值和的题在链上的情况很类似。大概就是说整一个分治出来，然后 $dp_{l,r}$ 处存放一个多项式。其中 $l,r$ 分别表示左右两个端点的状态，$x^k$ 项系数表示放置了 $k$ 个人的方案数。 ...

莫比乌斯反演分数规划二分答案多项式数学网络流

2020-04-17

0 383