牛客237787563号

未归档

/ 注册

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

省选模拟25 题解

A. 环是一道很巧妙的构造题。考虑写出满足条件的 $s_i,s_{i+1}$ 一定满足的式子。设 $x_{i,j}$ 表示 $s_i$ 中第 $j$ 个 $1$ 的位置。由操作A有 $k*t+\sum \limits_{j=1}^k x_{i,j}\equiv \sum \limi...

构造题贪心字符串并查集

2020-02-18

0 344

省选模拟24 题解

A. U.N.OWEN就是她吗？字典序最大，只需要贪心。考虑用网络流来做这个题。每次二分一个答案，然后对当前操作和之前进行的操作与每个元素直接建边，判断是否存在完美匹配。因为题中保证了一个特殊性质，考虑通过霍尔定理优化。点集 $X,Y$ 存在完美匹配，仅当 $\forall Z ...

线段树生成函数二分图多项式最短路

2020-02-14

0 412

省选模拟22 题解

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

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

2020-02-09

0 388

省选模拟21 题解

A. 灯容易发现问题是连通块数，因为原图是树，可以用点数（为$1$的点）减边数（连接相邻的为$1$的点的边）表示。点数是易于维护的，所以问题是维护边数。考虑一个情况，每种颜色的出现次数都很少，那么可以直接在原序列上暴力。另一种情况，每种颜色的出现次数都很多，并且颜色总数不多。那么...

根号分治 dp 图论

2020-02-08

0 317

省选模拟20 题解

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

lct 线段树单调指针

2020-02-07

0 349

省选模拟19 题解

A. 鱼死网破（clash）对于$k=1$的数据，容易发现只要维护每个$x$轴上面的点关于障碍两个端点的极角，并对每个端点对应的极角排序。对于每个$x$轴下面的点，可以通过极角来二分查找哪些点是看得到的。感觉和正解的思想差的不多。正解用到了一步补集转化。考虑每个$x$轴上面的点，...

线段树字符串后缀数组 Hash

2020-02-06

0 413

省选模拟18 题解

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

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

2020-02-05

0 387

省选模拟17 题解

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

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

2020-02-03

0 424

省选模拟16 题解

A. GCD和LCM 简单莫比乌斯反演。因为有一个$a$的限制，我们离线询问，将询问按$a$排序。随时更新要维护来统计答案的数组就可以了。 B. 平面图给出了平面图，所以自然想到对偶图。如果知道平面图上每个点所连的边的顺序，一个平面图转对偶图的方式是：考虑给每条边开两个...

启发式合并并查集莫比乌斯函数

2020-02-02

0 360

省选模拟15 题解

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

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

2020-02-02

0 366