zhangxixi的博客

平面几何、多项式、斯特林数听课随笔 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135166276 平面几何 知识点： 平面凸包 闵和，闵可夫斯基和 P4557 旋转卡壳 半平面交 最小圆覆盖 P4586 P9544 {v1,v2,..,vn}\{v_1,v_2,..,v_n\}{v1​,v2​,..,vn​} 的凸组合，满足 α1v1+α2v2+…αnvn,αi≥0,∑iαi=1\alpha_1v_1+\alpha_2v_2+\...

线性代数 听课笔记【上】 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135164326 画图好累~ 域：实数、有限域 向量 向量， x∈Fnx\in F^nx∈Fn FnF^nFn 向量空间——运算满足线性性 加、数乘 八条公理： u,v,w∈Vu,v,w\in Vu,v,w∈V ， VVV 为向量空间， c,d∈Fc,d\in Fc,d∈F ， FFF 为域 u+v=v+uu+v=v+uu+v=v+u (u+v)...

线性代数 听课笔记【下】 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135165435 矩阵“特征”相关的东西 矩阵特征向量和特征值 特征向量、特征值：成对出现，相对而言 非零向量 xxx ，满足 Ax=λxAx=\lambda xAx=λx ， AAA 为方阵（相当于是线性变换），λ\lambda 为数。则称 xxx 为一个特征向量， λ\lambdaλ 为一个特征值。 上面的等价条件： Ax=λIxAx=\lambda IxAx=λIx ，即 Ax−...

计算几何+欧拉回路合并：1222T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135152697 http://47.92.197.167:5283/contest/435/problem/2 2度点直接求夹角即可，4度角我是贪心选最小的情况。 但比如这样子： 我们会贪心选了4个蓝色角，形成红色和黄色两个欧拉回路，这就不是一个欧拉回路了。因此我们要考虑欧拉回路合并。 发现我们对于每个点划分成的两个集合各选一条边练一起，就可以合并两个欧=拉回路了。我们...

求两直线的旋转角 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135152729 如图，求 α\alphaα 。我们采用的是向量法+三角函数法 转化向量 ： (xb−xa,yb−ya),(xc−xb,yc−yb)(x_b-x_a,y_b-y_a),(x_c-x_b,y_c-y_b)(xb​−xa​,yb​−ya​),(xc​−xb​,yc​−yb​) 转化为向量后，相当于是求他们小于180度的夹角 可以先考虑求两个分别的角，再相减 已知...

【听课笔记】析合树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135140754 连续段： r−l=mx−mnr-l=mx-mnr−l=mx−mn ，比如 ｛2，4，3，5｝是，｛3，5｝，｛2，4，3｝不是. 性质1：一个点是连续段，一个排列也是（显然） 性质2：两个连续段的交必为连续段（感性） 本原段：一个连续段，不存在其他连续段和它相交确不包含 一个点表示一个本原段 合点：儿子按顺序递增或递减，比如 性质：任选两个点...

dp状态设计——转封闭形式！：CF1517F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135140525 https://www.luogu.com.cn/problem/CF1517F 一些基本的转化： 求所有方案的 ∑r\sum r∑r ，然后除以 2n2^n2n 可以枚举 rrr ，然后求出答案至少为 rrr 的有多少种。此处不需要差分后再乘 rrr ，我们直接加，类似增量构造的思想即可 我们可以对好人为白，坏人为黑，目标是使黑人在 ...

平面图上最大流通过转对偶图再转成树+set维护计算几何求最小环：qoj5048 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135133585 https://qoj.ac/problem/5048 因此我们可以平面图转对偶图，如下图，假如我们割黄边，就是给所有蓝边加黄边的权值 每次找一条边权最小的边，满足它恰好有一侧是无界区域。将它删 去，将它的边权加到它所在最小环的其他边上。可以证明这个操作前后 任意两点的最大流大小不变。 对于转最小环的过程，我...

增量构造+答案上界推出增量构造上界确定复杂度：CF1063F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135129285 https://www.luogu.com.cn/problem/CF1063F 可以贪心一波， ttt 长度必然是 ans,ans−1,ans−2,ans−3,…,3,2,1ans,ans-1,ans-2,ans-3,\dots,3,2,1ans,ans−1,ans−2,ans−3,…,3,2,1 这样子。 如果一个 kkk 不存...

循环同构串的判断+broder剃头截尾法实现均摊：P3546 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135126979 https://www.luogu.com.cn/problem/P3546 两个串的循环同构可以表示成： AB ， BA ，所以我们等价于在原串求： 显然A可以枚举，我们现在就是要求原串所有中心串的最长不交broder。 这个方法之前提到过，我们可以用broder剃头截尾法。 设 fif_ifi​ 表示 AAA 的长度为 iii...