SHOI

Description \(n\leq 5\times 10^4\)，树的深度 \(\leq 100\)。 Solution 对于每个 \(x,y\)，满足 \(d(v,x)\leq d(v,y)\) 或者 \(d(v,x)\geq d(v,y)\) 的点一定构成一个子树，所以可以枚举这个子树的根， ......

[SHOI2007] 园丁的烦恼 题目背景 很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。 有一天国王漫步在花园里，若有所思，他问一个园丁道： “最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……” “那么本质上 ......

Description 给定一棵树 \(T=(V,E)\)，其中 \(V\) 为节点集合，\(E\) 为边集合。对于 \(V\) 中的每个节点 \(v\)，有一个权值函数 \(W(v)\)，该函数的值均为正整数。记 \(d(u, v)\) 为节点 \(u\) 和 \(v\) 之问的距离，表示它们之问 ......

具体思路 设 \(f_{i,x}\) 表示 \(i\) 个盘子从 \(x\) 柱子出发的步数。 设 \(g_{i,x}\) 表示 \(i\) 个盘子从 \(x\) 柱子出发到哪个柱子。 记 \(y=g_{i-1,x}\)，\(z=6-x-y\)。 其中，\(y\) 代表将前 \(i-1\) 个盘子从 ......

P3989 bzoj #4416 先考虑部分分，看到 \(n \leq 20\) 容易想到这个部分可以用状压 起初可以设 \(dp_{S,i}\) 表示在前 \(i\) 个数中选出集合 \(S\) 中的字母是否可行，转移即枚举下一个字母是什么 这个 dp 有一个很显然的性质：他肯定是前缀一段 \(0 ......

看到不好维护的取模相关信息，想到根号分治。设值域为 \(V\)，根号分治的阈值为 \(B\)。 对于模数不超过 \(B\) 的情况，我们需要利用情况数为 \(O(B)\) 这一性质。在每次插入元素时动态维护所有情况的答案，查询时查表回答即可。 对于模数超过 \(B\) 的情况，我们需要利用商数个数为 ......

LG 任意时刻每个点最多被一条线段覆盖 暴力删每条线段是对的 插入 \([l,r]\) 时需要删除的线段要么被 \([l,r]\) 包含，要么覆盖 \(l\) 或 \(r\) 性质非常强所以做法非常多 一种比较神奇的：对于两条线段 \([l_{1},r_{1}],[l_{2},r_{2}]\)，定义 ......

求解$\sum_{i=0}^kC(n,i)\mod 2333$ 值得一提的是$2,23,233,2333$均为质数。 这次是对行求和。并没有很难好的公式。 但是由于模数非常特殊可以使用卢卡斯定理。 $C(n,i)\%\ p=C(n\%p,i\%p)\cdot C(n/p,i/p)$ 不妨设$f(n, ......

##[$P4344$ [$SHOI2015$] 脑洞治疗仪](https://www.luogu.com.cn/problem/P4344) ### 一、题目描述 曾经发明了自动刷题机的发明家 $SHTSC$ 又公开了他的新发明：脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。 为了 ......

第一道有关极限期望的数学题，记录一下。 我们设 $f_i$ 是凑齐前 $i$ 个球星期望需要买的饮料数。 $$ E = 1 \times \dfrac{n - i}{n} + 2 \times \dfrac{i}{n} \times \dfrac{n - i}{n} + 3 \times \left ......

蒟蒻提供一种fhq-treap的做法，但是不如其他题解的快（也没有stl快，不开O2 1.8s），但是比较好想，扩展了fhq的模板，也算是为使用fhq提供一个新方法。 首先，fhq-treap是什么，如果有同学不清楚，请[点击学习](https://www.cnblogs.com/Konnyaku4 ......

# [SHOI2011]双倍回文 题解 > 看了一些写回文自动机的大佬的代码，我深感敬畏，于是我转身向Manacher走去 现在荣登最优解第一页……  说实话，这个方法的复杂度是很 ......

感谢审核人 ## Description 给定 $n$ 个点，椭圆长轴的方向 $a$ 和放大倍数 $p$，求覆盖全部点的最小椭圆的半短轴长度。 ## Solution 让我们求最小覆盖椭圆，但是椭圆不具有什么好的性质，我们可以把椭圆转化成圆来做，这样，题目就转化成了最小覆盖圆，这个用随机增量法来做就 ......

有两个操作： 1. 将 $u$ 到 $v$ 路径增加 $k$ 2. 询问 $u$ 节点的子树和 显然，我们可以用树链剖分+线段树来做。 代码： ```cpp #include #include #include #include typedef long long LL; typedef unsig ......

##题目 洛谷P4287 [SHOI2011]双倍回文 ##思路 回文子串题，马拉车感觉不太好做，那就把回文自动机建出来看看。 好的现在我们有了一个$PAM$，这个$PAM$上储存了所有普通回文子串的信息，然后我们考虑所谓“双倍回文子串”和普通回文串有啥关系。 首先双倍回文子串一定是一个回文串，所以 ......

VP 省选。之前没有进 NOIP 伏笔了。 Day -5 USACO Ag。前情提要：寒假的时候 Ag 因为开 A 10min 没有想出来就提前跑路了。 先秒了 A，然后 B 没有思路，开 C 想了一会觉得有点典，会了，就润回去看 B。还是没有思路，把 C 写了，一发就过了。然后想着 B 打点部分分 ......