牛客237787563号

未归档

/ 注册

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

省选模拟80 题解

A. 数字如果枚举 $x\ and \ y$ 的取值，可以进行一个简单的dp。 $dp_{i,0/1,0/1,0/1,0/1}$ 表示从高到低到第 i 位，最高的几位分别是否与 $lx,rx,ly,ry$ 相同，然后这个 dp 数组的取值也只有0/1。所以可以 dp 套 dp。在考虑过...

分块多项式 dp套dp dp 根号分治矩阵数位dp

2020-04-25

0 408

省选模拟76 题解

A. MiniumCut 首先看到这个题，可以想到最小割树。然后发现原图的最小割树与原图是等价的。那也就是说，答案可以表示为一个树。然后考虑如何求出来这个树。大概的思路就是由小到大考虑每一组关系或者由大到小考虑每一组关系。这里用后一种思路，大概套用一下类似克鲁斯卡尔重构树的思想，然...

最小生成树回文自动机 Hash dp

2020-04-21

0 419

省选模拟75 题解

A. 比特币考虑把第 $k$ 位为 $1$ 的问题放在模 $2^{k+1}$ 意义下考虑，这样问题就简单了。因为若干个循环的贡献被强制放在了同一段上考虑。然后随便弄个数据结构维护一下即可。 B. 测试类似约数个数和一题，可以用类似的构造方法来展开 $d(i*j*k)$ 这个函...

数学莫比乌斯反演多项式 dp 斯特林数

2020-04-20

0 403

图论题解乱写

1.Codeforce 704D 网络流题目的一个经典套路就是将两种选择变形为：首先钦定一种选择，然后尝试替换为另一种选择。如果有流量即为替换，否则算没替换。所以本题直接建图，就得到了一个费用流做法。但是本题还有一个特殊的性质，即 $r,b$ 是固定的，与每个点无关的。所以可以...

2020-04-19

0 429

省选模拟74 题解

A. 签到如果权值在边上，那么问题就简单了，弄一棵生成树，然后对每个环权值塞线性基里就完事了。但是如果权值在点上，这个结论就并不成立了。所以可以联想+手玩发现，如果走一条路径然后回来，造成的贡献是两个端点分别状态取反，中间路径不变。然后可以得到一种构造方法，首先从起点走到终点，然后从...

分块点分治 ST表 bitset 线段树虚树线性基

2020-04-18

0 401

省选模拟73 题解

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

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

2020-04-17

0 383

省选模拟72 题解

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

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

2020-04-16

0 405

省选模拟71 题解

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

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

2020-04-15

0 477

省选模拟70 题解

A. 小 Y 增员操直播群考虑一个暴力做法，每次枚举较小的集合的大小，在判断合法之后可以直接将原问题划分为两个子问题。两个子问题是互不干扰的，所以直接 dp 就好了。然后可以发现枚举大小是没有必要的。考虑与元素 $n-1$ 连边的最小的点 $x$。如果两个集合大小相等，那么 $x...

线段树 dp

2020-04-14

0 362

省选模拟69 题解

A. 最小生成树因为最小生成树上一条非树边的权值必须大于两点的路径上的最大值，所以最优的策略肯定是将这棵树弄成一个菊花图。然后考虑把所有的边权按顺序列出来。如果当前还没有超出 $m$ 条边的限制，那么第 $i$ 条边的贡献就是 $(i-1)*w_i$。那考虑一个特殊的情况，如果说...

二项式反演多项式动态dp dp 分治构造题结论题容斥贪心

2020-04-13

0 381