题解

## 前言： ~~都大半年没在洛谷上提交过题解了。~~ SPOJ 上有双倍经验，题号为 SP7602。 我看题解区的大佬们有的正经用博弈论做，有的打表，但是感觉没有讲得很形象，这篇题解将**生动讲述打表做法**，同时为了让大家在感性理解后，还可以理性理解，会附上证明（这部分参考了别的题解）。 ## ......

[题目传送门](https://www.luogu.com.cn/problem/CF54C) # $Solution$： 一个比较简单的数位 dp处理技巧加上一个暴力的 dp。 设 $p_i$ 为区间 $[l_i, r_i]$ 中出现 $1$ 开头的数的概率。 考虑 $solve(x)$ 函数为求 ......

## 题意 给出 $n$ 个点，$k$ 条未钦定边权的边和 $m$ 条已钦定边权的边，要求为这 $k$ 条未指定边权的边分配权值使其均在图的最小生成树中且最大化这 $k$ 条边的边权之和。 （$1 \le n,k,m \le 5 \times 10^5$）。 ## 题解 首先满足要求这 $k$ 条边 ......

[题目传送门](https://www.luogu.com.cn/problem/UVA1108) # 题意 在一个无向图上选择尽量少的点涂黑，使得删除任意一个点后，每个连通分量里都至少有一个黑点（多组数据）。 # 正文 观察题意，发现这是个 Tarjan 求点双连通分量的板子。 考虑在求点双连通分 ......

[题目链接](http://oj.daimayuan.top/problem/464?locale=zh-cn) 可持久化平衡树看上去很行的样子，但是我不会啊。。。 先来考虑一个简化版的问题：求区间 $[1,n]$ 中 $\le H_i$ 的元素个数。 这显然是好做的，用权值树状数组就行。 回到本题 ......

[题目传送门](https://www.luogu.com.cn/problem/UVA12390) ## 题意 有 $n$ 个城市，$b$ 个投票箱，第 $i$ 个城市有 $a_i$ 人，每个人均有一张票，将 $b$ 个投票箱分给 $n$ 个城市，每个城市的票分摊在投票箱里，求所有城市中最多的投票 ......

### 思路 - 只需要让z串做到和y串一样，就得让y串每个字母（题意如此）均小于x串。 - 所以只要x串有一项小于y串，那么就输出-1，否则输出y串。 下面是核心代码： ```cpp #include using namespace std; int n; string x,y; int main ......

点权转边权，把边权设为两个端点的 $\min$，然后发现询问 $x$ 的答案，就是询问 $x$ 与所有黑点的虚树，边权的 $\min$ 是多少。假设要判定答案是否 $\geq k$，那么就是询问 $x$ 只经过 $\geq k$ 是否能到达所有黑点，于是想到建立 Kruskal 重构树，那么 $x$ ......

### 思路： - 利用桶存储轰炸区域，双重循环。 - 在存储轰炸区域时将次数刷新，也就是`pos[j][k]=i;`。 下面是核心代码： ```cpp for(int i=1;i>x1>>y1>>x2>>y2; for(int j=x1;j<=x2;j++) { for(int k=y1;k<=y ......

## [P8816 [CSP-J 2022] 上升点列](https://www.luogu.com.cn/problem/P8816#submit "P8816 [CSP-J 2022] 上升点列") ## 题目大意 给定 $n$ 个点，你可以任意添加 $k$ 个点，从中选择若干点使得序列中任意相 ......

## Div2 A 答案取决于 `_` 连续段长度，有一些细节，比如什么时候答案要加一减一，以及字符串是单独的 `^`。 ## Div2 B 首先先把全 $1$ 串给特判掉。 记将字符串视为首位相接的环的时，最大 $1$ 连续段长度为 $x$，答案为 ${\lfloor {x+1 \over 2} ......

## 题意 有一个 $n\times n$ 的方格图，坐标编号类似平面直角坐标系，左下角为 $(1, 1)$。 这个方格图被分成了 $n$ 层，左下角 $(1, 1)$ 为第一层，随后每层都向外拓展一圈，如下图就是 $n=5$ 的时候的情况： ![](https://espresso.codefor ......

标准的算法竞赛题有下面几个，写这篇博客主要是这个 M 很有意思，一直没绕过来这个弯 如果你有更牛逼的构造方法欢迎交流指导。 # B > 构造边长为 $n$ 的矩阵，使得每个 $2\times 2$ 的子矩形的权值和的极差最小 两个指针 L=1,R=$n^2$ 。将网格黑白染色后按照顺序遍历，黑色填 ......

LeetCode 算法题解之 26 进制转换 All In One 171. Excel Sheet Column Number 171. Excel 工作表列号 168. Excel Sheet Column Title 168. Excel 工作表列头 ......

先 reverse 一下。 不难看出选出的字符串长度为 $1,2,\cdots,k$ 一定不劣，仅考虑这种形式的。 然后考虑一手 dp，设 $f_{i}$ 表示最后一个子串是 $i$ 为结尾，最长长度是多少。 这样转移就是 $f_i\gets f_{j}+1,iff\ s[j-f_j+1,j]\te ......

特判 $m=0$。然后考虑做一个容斥。令 $F(E)\;(E\subseteq\{0,1,2\})$ 表示边权集合 $\subseteq E$（没有不在 $E$ 内的数字）的方案数。那么答案为 $$F(\{0,1,2\})-F(\{0,1\})-F(\{1,2\})-F(\{0,2\})+F(\{0 ......

[Lnk](https://www.luogu.com.cn/problem/CF757G)。这是一个 dfs 序 + 主席树的乱搞做法。 首先把树上距离拆开，令 $\operatorname{dis}(u)$ 表示 $u$ 到根的路径长度： $$\left(\sum_{i=l}^r \operat ......

## [CEOI2011] Matching 题解 ### 题外话： 看了其他人题解后作为初学 $kmp$ 的我非常蒙，因为对这个算法的核心掌握不太好，不知道怎么维护动态的序列，因此写下此题解共享经验，建议只会打模板的看看。 ### 参考资料： https://www.cnblogs.com/fus ......

原题链接 解题思路 这是一道经典的动态规划题目。 如果尝试使用深度优先搜索（dfs）或广度优先搜索（bfs）做就会获得 TLE （注意数据范围）。于是我们想到了更为高级的动态规划（Dynamic Programming, dp）。 简略介绍动态规划算法的核心思想：把原问题分解为相对简单的子问题的方式 ......

[原题](https://www.luogu.com.cn/problem/P9570) [更好的阅读体验](https://www.luogu.com.cn/blog/356277/p9570-glaciaxion-ti-xie) 直接遍历字符串，如果当前字符为 `N` ,就判断编号 $1 \si ......

[原题](https://www.luogu.com.cn/problem/P1371) 题目要求的很简单，就是问一个任意加了 $ N,O,I $ 三个字母中的任意一个打的字符串里面能组成几个 $ NOI $ 。 先考虑不加字母的情况，直接枚举每一个 $ O $ 的前后 $ N $ 和 $ I $ ......

题目给出两个数列 $a$,$b$，均按不降序排序，要求 $a$ 数列中的数在 $b$ 数列中出现多少次。 刚开始是想用一个数组来记录 $b$ 数列中的数出现的次数，然后再枚举 $a$ 数列中的每个数是否在 $b$ 数列中出现来累计答案，但是后面看到 $ 1 \leq n, m \leq 10^7 $ ......

~~蒟蒻第一次发题解qwq~~ $$ S=a_1 \times a_2+a_1 \times a_3+a1 \times a_n+a_2 \times a_3+···+a_n-2 \times a_n-1+a_n-1 \times a_n $$ 从样例来看 4 1 3 6 9 这道题就是要求 $$ ......

模拟退火的题解。 题目的难点在于如何计算点到所有线段的距离。 我们可以通过求线段的直线解析式，然后计算与其垂直的直线的斜率，将随机出来的点带入求得直线解析式，然后求两直线交点，判断是否在线段上进行分讨即可，但是我可能写挂了，所以改成用的向量。 ![](https://cdn.luogu.com.cn ......

看到这题，自然的想到 DP 啦！ 如果设 $f_{i,j}$ 为到第 $i$ 个位置前面的都合法且最后一段和为 $j$ 是否可行，那么转移十分显然，但是状态会炸。 此时我们考虑在状态上进行优化来减少时间，把 $f_i$ 设为到第 $i$ 个位置分段数量最多的情况下且最后一段和最少的和，以及能分成几段 ......

题意很清晰，直接跑 SPFA 求最短路。 只是我们在松弛操作时，需要注意从 $u$ 是否可以到达 $v$。 怎么判断呢？ 请移步下面三个部分。 ## Part 1 先解释一下，下面点 $i$ 的信息分别为以下变量： + `color` 表示颜色， `1` 表示蓝色，`0` 表示紫色 + `num` ......

## Div2 A 容易发现最后要存活下来一定要每次和 $1$ 号做出相同的选择，直接数就好了. ## Div2 B 容易发现当 $n$ 为奇数的时候无解。 考虑 $n$ 为偶数的情况怎么构造，有一种方案是在 $a_i=i$ 的基础上调整，交换一下 $a_{2i-1}$ 和 $a_{2i}$，证明考 ......

## 思路 题目给我们一个数组 $a$，那么我们可以算出其异或前缀和 $sum$。 我们知道，算出 $[l, r]$ 的异或和可以这样计算：$sum_r \oplus sum_{l - 1}$。 那么问题就转换为了 $sum_{0\sim n}$ 这 $n + 1$ 个数字两两异或之和（当然 $su ......

```cpp #include using namespace std; using pii = pair; constexpr int N = 3e5 + 5, S = 2e3 + 5, K = 1e2 + 5, INF = 0x3f3f3f3f; int n, m, T, poi[N]; int ......

## 题面 给定 $x, y$，求 $$\sum\limits_{a = 1}^{x} \sum\limits_{b = 1}^{y} \left[\left\lfloor\dfrac{a}{b}\right\rfloor = a \bmod b\right]$$ （$1 \le x, y \le ......