牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共10篇）

模拟33 题解

A. 春思比较简单的一道题，甚至是见过的原题。约数和是积性函数，搞一搞等差数列求和，乘到一起就可以了。 B. 密州盛宴显然，方案合法的条件是苏轼每轮都能吃到菜。所以就发现任意后缀0,1个数必须满足，$sufcnt_0-sufcnt_1<=1$。所以当不满...

dp 数学结论题单调指针

2019-09-03

0 348

模拟34 题解

A. 次芝麻显然答案是$min(n*2^k$%$(n+m),(n+m)-n*2^k$%$(n+m))$ 因为每一次乘2，在取模意义下，选大选小是等价的。 B. 喝喝喝 $a_x$%$a_y=k$ $a_x-k=a_y*m$ 所以直接对$a_x-k$质因数分解，两个单调指针乱...

dp 中国剩余定理结论题单调指针

2019-09-03

0 367

模拟35 题解

A. 公园长度放不进状态，那就把遍历的点的个数放进状态，使长度最小。然后就变成了DAG上最短路问题。设个源点汇点，直接拓扑排序就完了。 B. 计划设$mn(i)$表示左端点选i，最小的愉快的旅行。显然$mn(i)$是单调的，单调指针扫过去就完了。然后对询问...

dp 拓扑排序单调指针分块期望高斯消元

2019-09-03

0 308

模拟45 题解

A. kill 显然本题可以二分答案。于是问题转化为判断一个距离是否可行。将人和怪物分别按位置排序，那么每个人选择范围内可以选择的最靠左的怪物，不会使答案更差。单调指针扫一遍就可以了。 B. beauty 统计每条边儿子方向上的关键点数量，设为$cnt[i]$...

二分答案单调指针结论题 lct 最小生成树

2019-09-18

0 369

模拟56 题解

A. Merchant 看到一次函数，马上想到维护一个凸包，或许可以维护一下前m大一次函数的总和？然而想了想并不会维护，于是转换了下思路。似乎答案具有单调性：除去答案为0的情况，其它一定具有单调性。结论是显然的。不妨考虑任何一个组合。一些一次函数的和仍为一次函数。如果总一次...

二分答案高斯消元树状数组单调指针

2019-10-03

0 322

模拟110 题解

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

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

2019-11-11

0 287

省选模拟18 题解

A. 编码一眼原题，是一道数据结构（？）优化2-SAT建图的题。 2-SAT还是比较容易看出来的，每一个串只有$0/1$两种取值，一个串对另一个串起到了限制的作用。于是暴力的做法就是先将所有的串按照长度排序，由小到大分别将两个副本插入字典树。对字典树上每个节点维护一个vector，表示...

单调指针 Hash dp 高斯消元二分答案折半搜索 2sat trie树

2020-02-05

0 387

省选模拟20 题解

A. Ring 似乎算是一道半原题，原题的做法是维护环上的最小编号边，然后替换。本题的是否存在环更好维护。容易发现对于一个左端点，右端点的答案是单调的。存在一个分界点，满足分界点左侧没有环，分界点右侧有环。因为单调，所以可以在左端点移动的同时，右端点用单调指针维护分界点的位置。 ...

lct 线段树单调指针

2020-02-07

0 349

省选模拟35 题解

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

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

2020-03-02

0 334

省选模拟38 题解

A. Inverse 似乎这类问题的套路都是考虑每一个点对。然后考虑一个 dp 。设 $f_{k,i,j}$ 表示考虑后 $k$ 轮，最终 $i$ 在 $j$ 左面的方案数。对于每个 dp 值可以简单枚举翻转区间， $O(n^2)$ 转移。然后发现这个玩意可以优化，如果枚举翻转区间...

分块单调指针差分 dp 计算几何平衡树凸包

2020-03-05

0 428