牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共24篇）

模拟104 题解

A. 中间值二分答案在数组$a$中的排名，则得到期望的在数组$b$中的排名。当数组$b$中对应的数恰好是大于二分值的第一个数，代表二分到了答案。通过对应的数与当前数的大小关系，可以确定二分方向。同理还应当二分答案在数组$b$中的排名。然而这个做法实现比较困难，还有另一个更帅的二分...

分治二分答案线段树 dp 单调栈

2019-11-07

0 405

模拟107 题解

A. 字符交换枚举最终出现的字符，那么答案具有单调性。之后枚举相同字符的起点，可以计算出终点。最优策略显然是换到中间的字符旁边，所以用前缀和维护一下就完了。 B. 平方数考虑怎样的两个数相乘可以构成平方数：将两个数分别质因数分解，如果二者奇数的质因子集合相同，...

二分答案 dp 容斥

2019-11-10

0 361

模拟110 题解

A. 最大或因为或运算特殊的性质，从高位到低位进行贪心。将$l$，$r$的二进制位分别取出，从高到低枚举每一位，当存在一个二进制位不同，即在此位$l$为$0$而$r$为$1$。那么$x$可以选择后面每个二进制位中的$1$，保证低位贡献的最大化，$y$只要保证高位的贡献就可以了。 ...

图论单调指针位运算二分答案折半搜索

2019-11-11

0 287

网络流杂题一

A. 奇怪的游戏网格图在网络流中往往对应着黑白染色，当然还有四色染色等奇怪的东西。建图并不难，但是二分的思想是很好的。考虑如何检验一个答案$x$，将黑点视为二分图的左部点，白点视为二分图的右部点。一次操作对应一组相邻黑白点$+1$，所以直接建图看能否跑满流就完了。然而需要注意，显...

区间dp dp 二分答案网络流二分图

2019-12-08

0 523

网络流杂题三

A. 1565: 植物大战僵尸考虑保护关系可能会出环，也就是其中任何一个一定不能被选。注意环的出边也是无法被选的。注意要找的环的出边并不是网络流建的图的出边，因为网络流反映的是必须选的关系，即由被保护者到保护者。然后就是简单的最大权闭合子图。 B. 寿司餐厅似乎并不是很难...

网络流二分答案

2019-12-09

0 290

省选模拟5 题解

A. 青蛙因为每个青蛙都可以一步跳到终点。所以二分几个青蛙可以无消耗跳到终点，只要让最贵的几个青蛙跳过去。之后特判一下一个青蛙都跳不过去的情况就好了。 B. 一起自习的日子伯努利数练习题。不断的把自然数幂和用伯努利数展开，顺便二项式展开一下就好了。另外分析可知原式可以...

贪心主席树 lct 二分答案伯努利数后缀自动机

2020-01-12

0 418

省选模拟13 题解

A. 同桌的你每个人渴望与一个人当同桌。容易发现这个关系形成内向基环树森林。问题转化为求基环树森林的最大匹配。任意选一条环上的边，分别尝试该边为匹配边、非匹配边即可。 B. 大水题一个常用的但想不到的东西：将每种颜色出现次数的差值为定值，转化为对颜色序列差分后相等。然...

二分图二分答案 Hash 差分基环树 2sat

2020-02-01

0 474

数学专题测试4

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

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

2020-01-29

0 499

图论专项测试

A. center 分别考虑每一条边。二分答案，问题转化为判定是否存在可行区间。然后列式子发现存在三种限制的形态，而其中的一种（含有或运算）并不是一个线性算法能够解决的。盲猜这种情况并不多见，剪枝暴力$AC$。个人认为三分的算法是伪的，见数据（不能hack三分算法，但不单谷）： ...

二分答案最短路网络流三分二进制分组

2020-01-30

0 488

省选模拟17 题解

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

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

2020-02-03

0 424