镇海省选集训 Day1

摘要

镇海中学的都是神仙吧

A.Line

平面上有 n 条两两不同的直线 ,现在给出一个左下角为 右上角为 的矩形,问有多少个直线对 满足 的交点在矩形内(含边界)

算法 1:暴力判断两两直线的交点位置,复杂度 .

考虑把在矩形外面的直线都忽略,只考虑与矩形相交的直线,这些直线会把矩形的周长分为两个部分;考虑两条相交的直线,这两条直线各自对应的部分也相交(随便各取一个部分都是相交的). 因此我们断环为链,那么每个直线分割出的部分可以用一个唯一的区间表示,两个相交的直线对应的区间也相交

相交区间

因此问题转化为 个闭区间 中,相交区间的对数. 把区间端点当作二维坐标,就是一个二维数点的问题. 对于两个区间 ,如果 ,那么两者相交. 也就是在确定 的情况下在一个矩形内数点. 采用离线算法,树状数组维护即可.

B.Equation

多组数据,给出整数 ,问存在多少有序二元组 满足

答案对 取模.

.

设答案关于 的函数为 . 可知答案是积性的(据说是中国剩余定理的推论),即当 时,有 .

因此考虑将 分解质因数.

对于 的情况,可以 分解;而对于 的情况使用 Pollard-Rho 质因数分解(先咕着)

于是我们只需要考虑去求 即可,其中 为质数.

为奇质数

要找一个 ,相当于找一个 . 而后者与 是等价的. 因为

那么就可以使用代数变换来在两者之间转换,换言之两者构成双射.

因此我们设 . 我们要找的就是 的有序二元组. 那么 显然是二次剩余. 因为 是奇数,所以 2 有逆元,所以在模意义下可以进行除以 2 的运算;因此只要找到二次剩余对应的根,就能保证 有整数解. 因此我们考虑求 意义下的二次剩余的个数

时,也就是在 意义下,二次剩余的两个根的奇偶性不同. 二次剩余的个数为

考虑 意义下,所有的数可以表示为 的形式. 若 是二次剩余,那么 一定为偶数,即 的形式的数才可能是二次剩余. 推一推式子,就可以发现这样的二次剩余的个数为

那么对每一个 如是计算求和,就可以得到 意义下二次剩余的个数.

求得了个数 ,那么对答案的贡献就是 .(有序数对,乘法原理)

为 2

这个时候,我们的二次剩余不能保证 有整数解(因为没有 2 的逆元)

考虑暴力打表,我们打出 的表即可. 鉴于笔者并没有完全听懂标程的算法,这里简单口糊一下

先打出 比较小的情况下的解,例如 的函数值可以暴力 算. 然后得到答案序列 . 这样的序列通常有一个递推的式子形如

因此我们想办法求出这个 序列的前几项,用高斯消元做,然后找到 序列的规律之类的来得到整个 序列,然后就可以递推算 序列了

C.Bridge

在无向图 中,定义桥为点的三元组 满足 .

求带标号的 个点,至多有 个桥的无向图(不要求连通)的个数,答案对 取模

.

这道题的范围比较吓人,需要去猜一个结论

考虑 个点的连通图有 个桥时:

  • 时,意味着任意两个点都相邻,因此图是一个团.
  • 时,一定满足 .

这个结论放在最后证明. 我们考虑在此基础上的算法过程. 既然桥最多只有 个,那么点最多就只有 个,于是我们可以设 表示 个点有 个桥的连通图个数,把这个表打出来存到数组里,然后跑一个二维的 DP 就做完了.

DP

定义 表示 个点有 个桥的无向图(不要求连通)的个数,在 DP 的时候相当于每次加一个 或者加一个团上去,标号用组合数算即可

打表

对于求 的过程,没什么思维,直接暴搜,做一些能做的剪枝(桥数 >k 就 break),位运算优化一下,用并查集判连通性. 据说标程打下来都花了 10 分钟

结论的证明

证明一下 的情况

假设对于一个 个点的连通图,我们要判断它的桥的个数,我们模拟这个图的构建过程,假设我们往这个图逐渐加点,每加一个点,就把和这个点相邻的边连起来. 假设加了前 个点后,这个图有一个桥 .

我们假设增加第 个点后,桥的个数不会增加. 那么考虑存在 ,因为不增加桥,所以 . 以此类推,所的点,都要与 有连边,否则桥的个数就会增加. 这时考虑桥 ,但 ,因此 会构成一个桥,与假设矛盾.

也就是说,只要这个图在当前状态下有桥,那么每加一个点,就会增加至少一个桥. 于是对于 的情况,我们在模拟构建过程的时候,优先选择三个点构成一个桥,那么随后增加的点都会形成至少一个桥,于是 .

证毕.


  转载请注明: Sshwy's Blog 镇海省选集训 Day1

 上一篇
Hexo 文章加密 Hexo 文章加密
摘要 Hexo 作为简洁高效的静态博客生成,却没有足够安全的博文加密插件。本文记录了笔者一步步探索 Hexo 在文章源代码上加密的过程 效果展示密码是 helloworld 哦~ 不要妄图查看源代码获取内容哦~ 一级二级三级四级五级六级
2019.03.23
下一篇 
点分治入门 点分治入门
摘要 莫名其妙发现这几天遇到了很多点分治的题目,于是来系统整理一下点分治算法 点分治是一种树上分治算法。通常用于解决无根树上的统计问题。对于统计的问题,可以按照结点对其分类,分别统计后再组合成结果。而这类问题的求解复杂度往往和树的深度、大小
2019.03.07
  目录