牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共73篇）

省选模拟11 题解

A. 组合数问题还没想明白如何做，待补。 B. recollection 因为原图为trie树，树上两个点的lcp长度等于两个点的lca深度。考虑通过广义sam来维护两个点的lcs。树上同时对应着一个$endpos$，树上两个点对应的$endpos$对应的广义sam上节点在后缀...

并查集平衡树后缀自动机线段树

2020-01-29

0 405

省选模拟12 题解

A. Colorado Potato Beetle 暴力做法是直接bfs。优化的方法是离散化。将特殊的点的横纵坐标抽出来，然后用这些横纵坐标为1e12*1e12分成一个个块，容易发现每个块内的状态是一致的。然后用与暴力类似的方法即可，注意最后统计的是每个块的实际大小。 B. D...

后缀自动机 dp 状压搜索树链剖分线段树

2020-02-01

0 359

省选模拟17 题解

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

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

2020-02-03

0 424

省选模拟19 题解

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

线段树字符串后缀数组 Hash

2020-02-06

0 413

省选模拟20 题解

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

lct 线段树单调指针

2020-02-07

0 349

省选模拟24 题解

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

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

2020-02-14

0 412

省选模拟26 题解

A. 染色问题不然想到一个50分的dp，然而我的dp转移和正解不一样所以没法优化所以就死了。。要是用我的dp推正解大概只能考虑实际含义。考虑每次在已有的颜色序列中间插入一段，那么考虑转移的方案数，不难得到一条dp转移路径的贡献是每次颜色序列长度+1的乘积。所以枚举一共经过了多少次转移，转...

dp 倍增多项式二项式反演容斥线段树

2020-02-22

0 388

省选模拟29 题解

A. circle 容易发现，如果存在一组合法答案，那么 $k$ 个钦定点之间和 $n-k$ 个不被钦定点之间一定都是存在拓扑序的。考虑一个不被钦定点不被删去，一定满足这个点的连边情况恰好满足在 $k$ 个点的排名上存在分界点。上面那个条件使得不存在不被钦定点与两个被钦定点之间的环，另一...

线段树树链剖分 lct dp 竞赛图

2020-02-23

0 313

省选模拟31 题解

A. Skip 一眼决策单调性，但是感觉因为带个权值就不好处理了。实际上对权值开个线段树，然后直接在线段树上维护决策单调性就完事了。而且这个式子是一个显然的斜率优化 dp ，在权值线段树上维护凸包也挺套路的。感觉这题没做出来比较可惜，没有想到通过对权值开线段树，来实现权值的无关操作。 ...

状压线段树凸包 dp 决策单调性

2020-02-26

0 410

省选模拟34 题解

A. 倚天剑的愤怒考虑特殊的情况，如果 $a_i <0$ ，那么最优的决策一定是把最差的跳过。然后可以考虑如果存在一个 $a_i>0$ ，那么这个 $i$ 无法对前面的操作产生影响，但是可以是把后面的一些小于 $0$ 的元素抵消掉。抵消之后呢？问题仍然是把最差的跳过。所以...

并查集分治贪心线段树直径

2020-02-29

0 327