20210109~10 考试总结
都是雅礼2017集训的题
Day1
T1 决斗
有结论:存在至少一个位置 kkk 满足对于任意的顺序都满足没有精灵从第 kkk 个精灵旁走到第 k+1k+1k+1 个精灵旁。
证明:定义 RiR_ ...
20200116~17 考试总结
这两天考了学长出的一套省选模拟题。(似乎是 Matthew99 /se
Day 1
A
建出 SAM 后就是在 parent tree 上找 LCA。
B
是 CF708c 的加强版。
123 ...
20210129 考试总结
改题去了,等会填坑
20210206~07 考试总结
这两天考的都是 USACO 的题
USACO 2019 December Contest, Platinum
pieaters
区间 dp ,注意枚举端点 i,j,k 的顺序,模拟一下就好了,如果 ...
BSGS
求解满足 ax≡b(modp)a^x\equiv b\pmod pax≡b(modp) 的最小 xxx ( ppp 是质数)
分块?设分块大小为 ttt
考虑 i∈[0,⌈nt⌉],j∈[1,t] ...
Bézout定理
定理
存在整数 xxx,yyy 使得 ax+by=gcd(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b)
证明:
考虑求 gcd(a,b)\gcd(a,b)gcd(a,b) ...
一些有用的小模板
树状数组 bit.h
12345678//自定义类型需重载 + - 运算符template <typename T, int maxn>class binary_indexed_tree ...
二分图
二分图的结论和算法 防止忘记
匈牙利算法的过程是,枚举每一个左部点 uuu ,然后枚举该左部点连出的边,对于一个出点 vvv,如果它没有被先前的左部点匹配,那么直接将 uuu 匹配 vvv,否则 ...
树的重心相关结论
转载:pyqpyq 的Blog
定义
一棵树中以一个节点为根的子树的大小的最大值最小的节点为树的重心。
性质一
一棵树中以重心为根的节点的子树大小均不超过整棵树的大小的一半。
证明:
考虑反证法 ...