牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共5篇）

模拟25A 题解

A. Lighthouse m的范围极小，显然的容斥。总的方案数，减去受任意一个限制的方案数，加回受两个限制的方案数。就能得到受所有限制的的方案数。将选择的一些边所指向的点放在同一个联通块里。方案数其实就是这些联通块的圆排列，再乘上$2^{不为1的联通块个数}$，因为每个联通块...

容斥欧拉路点分治线段树

2019-08-19

0 436

模拟41 题解

A. 夜莺与玫瑰与题解中的定义类似：枚举每个斜率，设为向量$(a,b)$ 如果$gcd(a,b)!=1$，那么直接跳过。考虑每个点(x,y)，它的前趋为(x-a,y-b)，后继为(x+a,y+b)。一个点是合法的当且仅当不存在前趋，存在后继。于是$ans=\sum \limit...

点分治组合计数线段树

2019-09-10

0 346

省选模拟9 题解

A. Surprise me 直接将$\varphi(i*j)$展开为$\varphi(i)*\varphi(j)*\frac{gcd(i,j)}{\varphi(gcd(i,j))}$。于是可以套用莫比乌斯反演。最终的式子大概是$\sum \limits_{T=1}^{n}f(T)\su...

二分图虚树图论结论题莫比乌斯函数点分治提交答案

2020-01-17

0 654

省选模拟35 题解

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

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

2020-03-02

0 334

省选模拟74 题解

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

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

2020-04-18

0 401