牛客暑期多校2比赛链接 A. Floor Tiles题目链接 找规律的题目，看题解即可 B.MST题目链接 解：一道使用根号分治的暴力题目。 首先我们一共有两种暴力方式，一种是$O(n^2)$的遍历任意给定的两个点，得到我需要的合法边，再对边进行kruskal算法得到最小生成树 还有另一种方法是$O(m)$的枚举我所有的边，看这个边的两端是否都在集合中，这一步骤相当于是做了一遍kruskal。 第

牛客暑假多校第一场解题报告比赛链接 A. A Bit Common原题链接 题目大意：对于一个序列A（每个数都$\lt 2^m$），存在一个子序列B，使得$AND_{i \in B}B_i=1$，则被计数，问一共有几个这样的序列A，允许有重复数字 解：我们先钦定有序列A的长度是k，那么这k个数一定都是奇数，换句话说他们二进制的最后一位一定是1，现在考虑前面的$m-1$位，显然，如果我想让他们的AN

组合数学例1.硬币购物原题链接 解：这道题目的dp非常巧妙，如果看不懂就死记硬背下来吧。 由于这道题目中中硬币的面值是给定且不会发生变化的。所以我们可以利用完全背包，预处理出$dp[i]$，$dp[i]$表示组成$i$元一共有几种方式（没有限制）。 但是这道问题是有限制的。我们如何利用没有限制的方案数去推导有限制的方案数呢？答案是利用容斥原理。 例如说，对于$i$物品，有$d[i]$的限制，如果我

解题报告比赛链接 F.循环移位原题链接 题目大意：首先我们定义以下概念 现在给你n个整数，你必须分别做一次$L(x),R(y),x \ne y$，问最大的异或和是多少 解： 我们令$res=a_1 \land a_2 \land… \land a_n$，假设我选取了$i,j分别做L(i),R(j)$那么我的答案就是$res \land x_i \land L(i) \land x_j\land

重链剖分1.重链剖分的板子1234567891011121314151617181920void dfsFir(int u, int pre) { siz[u] = 1; for (auto &[v, w] : edge[u]) { if (v == pre) continue; dep[v] = dep[u] + 1;

数论基础1.拓展欧几里得拓展欧几里得就是求形如$ax+by=\gcd(a,b)$的整数解的一组特解 123456//ax + by = d//这个模板中的d = gcd(a, b) 顺便也求出来了inline void exgcd(int a, int b, int &d, int &x, int &y) { if (!b) d = a, x = 1,

树型DP选择节点类的题目例1. 没有上司的舞会原题链接 解：我们设$dp[i][0/1]$分别表示 选/不选 第$i$个人的最大快乐值，设当前节点为u，u的儿子为v，$a[i]$表示i的快乐值 那么，我们可以列出他的转移方程： $\begin{cases} \begin{aligned} dp[u][0] &=\sum \max{(dp[v][0],dp[v][1])} \\ dp[u][

区间DP例1. 关路灯原题连接 大意：给你初始位置$x_0$以及每个路灯的位置$x_i$和功率$p_i$，你的速度为1$m/s$，问关闭所有路灯后，最小的能耗 解： 规定$sum_k=\sum_{i=1}^{k}p_i$ 设$dp[i][j][0/1]$表示关闭$[i,j]$的所有路灯后，你停留在i位置(0)或者j位置(1)的最小能耗 那么对于$dp[i][j][0/1]$有两种转移策略： ​

后缀数组的一些运用和小结论11.最长重复子串原题地址 题目大意：给你一个字符串，让你求出至少出现两次的最长子串 解：这是一道板子题，所谓至少出现两次，其实就是我的$hegiht[i]$，即我的$lcp(s_1,s_2)$。所以我只要求出所有的height取最大值即可 时间复杂度$O(n\log n)$ 2.字符加密原题地址 解：看到环形字符串，下意识就会把它复制一份拼上。之后直接跑一个SA，收集答