20210225 考试总结
Review 爆炸了,毒瘤出题人一场比赛 3 个数学题 solution 题还没有改完 其实是开学了要补作业
20210224 考试总结
改题进度 [ ] T1 [x] T2 [ ] T3 学习进度 [x] 圆反演 [ ] 二次剩余 [ ] NTT [ ] 莫比乌斯反演 [x] Pollard-Rho
圆反演变换
定义 给定反演中心点 OOO 和反演半径 RRR 。若平面上点 PPP 和 P′P'P′ 满足: 点 P′P'P′ 在射线 OP→\overrightarrow{OP}OP 上 ∣OP∣⋅∣OP′∣=R2|OP| \cdot |OP'| = R^2∣OP∣⋅∣OP′∣=R2 则称点 PPP 和点 P′P'P′ 互为反演点。 下图所示即为平面上一点 PPP 的反演: 性质 圆 OOO 外的点的反演点在圆 OOO 内,反之亦然;圆 OOO 上的点的反演点为其自身。 不过点 OOO 的圆 AAA ,其反演图形也是不过点 OOO 的圆。 记圆 AAA 半径为 r1r_1r1 ,其反演图形圆 BBB 半径为 r2r_2r2 ,则有: r2=12(1∣OA∣−r1−1∣OA∣+r1)R2r_2 = \frac{1}{2}\left(\frac{1}{|OA| - r_1} - \frac{1}{|OA| + r_1}\right)...
一些有用的小模板
树状数组 bit.h 12345678//自定义类型需重载 + - 运算符template <typename T, int maxn>class binary_indexed_tree { T c[maxn + 10]; public: void add(int p, T v) { p++; for (; p <= maxn; p += p & -p) c[p] += v; } T query(int p) { p++; T v = 0; for (; p; p -= p & -p) v += c[p]; return v; } T range(int l, int r) { return query(r) - query(l - 1); }}; 可删堆 deletable_priority_queue.h 12345678910111213141516//自定义类型要求同 priority_queue 相同。template...
20210222 考试总结
改题进度 [x] forgive [x] palingenesis [x] destiny Review 人要有梦想,暴力还是要打的,没准就过了呢。 Solution T1 forgive 平面内 nnn 个点 (xi,yi)(x_i,y_i)(xi,yi),每个点有 ppp 的概率出现,保证三点不共线。可以在两个点之间连一条线段,线段之间不能相交,求最多可以连的线段数的期望。 考虑一个平面图,一定是三角剖分时连的线段最多。 对于一个三角剖分 我们想求的就是剖分的线段数。 设边数为 EEE ,点数为 VVV ,凸包上有 kkk 个点,FFF 个有界面,则有结论 E=3V−k−3E=3V-k-3E=3V−k−3 下面证明这个结论。 对于平面图,有欧拉公式 V+F−E=1V+F-E=1V+F−E=1 ,又有 2E=3F+k2E=3F+k2E=3F+k (三角形三条边,加上凸包上的边就都算了两次) 将两个式子做一些运算,即可得到 E=3V−k−3E=3V-k-3E=3V−k−3 。 期望即为...
出题 idea
d8bb691c3eda980fd06150c71a35dc83c34e3376450b9ec0a70aace687932e57430c4d5d5e624d946e5b8852f5289ee9 这里需要密码
线性代数有关内容
感谢来自 zxyhymzg 的线代小课堂(
分散层叠算法
分散层叠用于解决以下问题: 给定总长度为 nnn 的 kkk 个序列,每次询问数 xxx 在每个序列中的非严格后继。 咕咕咕
20210220 考试总结
Review 考试时一直在肝论文,发现 2017 国集论文里面有决策单调性优化 dp 的内容,终于在考试最后 2 分钟调过样例。 结果因为没有滚数组导致 MLE,沦为暴力 20pts。 Solution T1 hike nnn 个点, qqq 个询问 两种询问,分别是合并两树和查询树中里给定点最远的点的距离 LCT 维护树的直径板子题 O(nlogn)O(n\log n)O(nlogn),可惜我不会,只好启发式合并暴力处理倍增数组。 考虑两颗树的直径端点 a,b,c,da,b,c,da,b,c,d ,则合并出的新树直径只有可能是这 4 个数中的 2...
二分图
二分图的结论和算法 防止忘记 匈牙利算法的过程是,枚举每一个左部点 uuu ,然后枚举该左部点连出的边,对于一个出点 vvv,如果它没有被先前的左部点匹配,那么直接将 uuu 匹配 vvv,否则尝试让 vvv 的“原配”左部点去匹配其他右部点,如果“原配”匹配到了其他点,那么将 uuu 匹配 vvv,否则 uuu 失配。 二分图最大独立集等于总点数减去最大匹配