小明の雜貨鋪

树的重心 树的重心要么 惟一 ，要么 有两个，且这两个重心相邻。 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半，即 siz[v] * 2 < siz[u]。 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。 求树的重心 1234567891011121314151617vector<int> siz(n), mss(n); // 固定根时的子树大小 最大子树大小auto dfs = [&](this auto&& dfs, int u, int p) -> void { siz[u] = 1; for (auto v : E[u]) { if (v == p) continue; dfs(v, u); siz[u] += siz[v];...

树上思维 2024 CCPC 济南 L. Intersection of Paths 在树上选择 kkk 条路径，路径的 2k2k2k 个端点必须互不相同。最大化被所有路径包含的边权之和。有多次询问，每次询问会临时修改一条边的边权。每次询问的 k 可能不同。 节点数、询问数 5×1055 \times 10^{5}5×105。 可能被端点两两不同的 kkk 条路径包含的边，需要满足把这条边去掉之后，形成的两个连通块大小都大于等于 kkk。在 kkk 固定的情况下，这些边形成了一棵树。所以答案就是这棵树的直径。 kkk 变化的时候怎么办？注意到 k+1k + 1k+1 的树被 kkk 的树完全包含，所以可以将所有询问按 k 从小到大排序，依次处理。 问题变为：每次询问临时修改一条边的边权，以及在 kkk 变大时永久删掉若干条边，求树直径。删掉边可以转化为将边权改成 000。 这就是经典的动态树直径问题。 复杂度 Θ(nlog⁡n+q(log⁡n+log⁡q))\Theta(n \log n + q(\log n + \log...

斐波那契数列的 20 种求法 矩阵快速幂 题意 设 an={an−1+an−2,n⩾31,n=1∨n=2a_{n}=\begin{cases}a_{n-1}+a_{n-2},&n \geqslant 3\\1,&n=1\lor n=2\end{cases}an​={an−1​+an−2​,1,​n⩾3n=1∨n=2​，求 an mod ma_n\bmod man​modm。 解 设 M=[0111]\mathbf{M}=\begin{bmatrix}0 &1\\ 1 & 1\end{bmatrix}M=[01​11​]​，则 [Fn0Fn+10]=Mn−1[1010]\begin{bmatrix}F_n & 0 \\ F_{n+1} & 0\end{bmatrix} =\mathbf{M}^{n-1}\begin{bmatrix}1 & 0 \\ 1 & 0 \end{bmatrix} [Fn​Fn+1​​00​]=Mn−1[11​00​] 于是...

2024 东北四省 K / CC 网络赛模拟 C. Tasks Link [[…/contests/2024-09-07-2024 CCPC 网络赛热身赛 |2024-09-07-2024 CCPC 网络赛热身赛]] 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253int n;cin >> n;using node = struct { int l, r, b, id; };vector<node> a(n);for (int i = 0; i < n; ++i) { cin >> a[i].l >> a[i].b; a[i].id = i;}sort(a.begin(), a.end(), [&](node a, node b) { return a.l == b.l ? a.b < b.b : a.l <...

平面计算几何 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899using T = double;const double eps = 1e-9, pi = acos(-1.0);int sgn(T x) { return (fabs(x) <= eps) ? 0 : (x < 0 ? -1 : 1);}struct P { T x, y; P() : x(0), y(0) {} P(T x, T y) : x(x), y(y) {} // P(T r, double alpha, int _) : x(r * cos(alpha)), y(r *...

博弈论 是经济学的一个分支； 主要研究具有竞争或对抗性质的对象在一定规则下的行为； 考虑个体中的预测行为和实际行为，并研究其优化策略； 通俗地讲，主要研究的是在一个游戏中进行游戏的多位玩家的策略。 公平组合游戏（ICG） 二人参与，轮流决策，每次可以在有限的合法决策集合中选择一种进行操作，双方均知道游戏的完整信息； 在某一确定状态做出的决策集合只与状态有关，与玩家、之前的操作等任何因素都无关； 如果轮到某位玩家的回合时合法决策集合为空（即无法进行操作），该名玩家负。游戏一定会在有限步数之后以非平局结束； 大部分棋类游戏都是非公平组合游戏：国际象棋，五子棋等，因为双方都无法使用对方的棋子。 博弈图 给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。 任何一个 ICG 游戏都可以转化为有向图游戏：把每个状态视为一个节点，向它的后继状态连边，转化为有向图游戏，也称绘制了它的博弈状态图（简称博弈图或者游戏图）。 ...

2024 牛客多校 9I - Interesting Numbers [[…/contests/2024 牛客多校 /2024-08-13：2024 牛客暑期多校训练营 9|2024-08-13：2024 牛客暑期多校训练营 9]] 1234567891011121314151617181920import mathn = int(input())l, r = map(int, input().split())def slove(k) : wei = 10 ** (n // 2) half1 = k // wei half2 = k % wei half3 = 10 ** (n // 2) sqr1 = math.isqrt(half1) sqr2 = math.isqrt(half2) sqr3 = math.isqrt(half3) if sqr3 * sqr3 == half3: sqr3 -= 1 if half1 == sqr1 ** 2: return sqr1 *...

ST Table ST 表 (Sparse Table, 稀疏表) 基于 倍增 思想，用于解决 可重复贡献问题 †^\dagger†，支持在 Θ(1)\Theta(1)Θ(1) 的时间内 区间查询，不支持在线修改。 递推计算所有长度为 222 的幂的区间的结果。对于询问 [l,r)[\mathscr{l}, r)[l,r)，记 k=⌊log⁡2(r−l)⌋k = \lfloor \log_2(r - \mathscr{l}) \rfloork=⌊log2​(r−l)⌋，结果为 [l,l+2k)[\mathscr{l}, \mathscr{l} + 2^k)[l,l+2k) 和 [r−2k,r)[r - 2^k, r)[r−2k,r) 的结果的并。 †:^\dagger:†: 区间询问对应的运算符 ∗*∗ 满足 x∗x=xx*x=xx∗x=x 和结合律 (x∗y)∗z=x∗(y∗z)(x*y)*z=x*(y*z)(x∗y)∗z=x∗(y∗z) ，如 max⁡, min⁡, ∣ , &, gcd⁡\max,\ \min,\ |\ ,\ \&,\...

逆元 模为素数 123456789101112131415constexpr int mod = 998244353;ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res;}int inv(int n) { return qpow(n, mod - 2);} // 1/a (p 是素数) 非固定模数 123456789101112131415161718192021222324252627282930ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}ll exgcd(ll a, ll b, ll& x, ll& y) { if (b ==...

裂项 ∑i=1n(ai−ai+k)=∑i=1kai−∑i=n+1n+kai\sum_{i=1}^{n}(a_{i}-a_{i+k})=\sum_{i=1}^{k}a_{i}-\sum_{i=n+1}^{n+k}a_{i} i=1∑n​(ai​−ai+k​)=i=1∑k​ai​−i=n+1∑n+k​ai​ 约瑟夫环问题 约瑟夫环问题 设 Jn,mJ_{n, m}Jn,m​ 表示规模分别为 n,mn, mn,m 的约瑟夫问题的答案。我们有如下递归式 Jn,m=(Jn−1,m+m) mod nJ_{n, m}=\left(J_{n-1, m}+m\right) \bmod n Jn,m​=(Jn−1,m​+m)modn 这个也很好推。从 0 开始数 mmm 个，让第 m−1m-1m−1 个人出局后剩下 n−1n-1n−1 个人，计算出在 n−1n-1n−1 个人中选的答案后，再加一个相对位移 mmm 得到真正的答案。 题目说是从 kkk 开始报数，所以答案再加上 kkk。 时间复杂度 Θ(n)\Theta(n)Θ(n)： 12345int res = 0;for (int i =...