## 前置芝士 KMP。 ## 题意简述 给定两个长度相同的字符串 $a,b$，长度均小于等于 $10^6$。每次操作可以把 $a$ 的第一个字符移到最后，求至少多少次操作才可以让两个字符串相同。无解输出 $-1$。$t$ 组数据。 数据保证：$1\le t \le 10000$，字符串 $a$ 的长度总和不超过 $1…

## 前置芝士 尺取法。当然可以用二分替代，但是时间复杂度是 $O(n \log n)$ 的。 ## 题意简述 给定一长度为 $n(1\le n \le 3\times 10^5)$ 的仅包含小写字母 `a` 和 `b` 的字符串 $s$ 以及两个数 $A,B(1\le A,B\le n)$，求出二元组 $(l,r)$…

## 题目描述 给定两个个 $n\times n$ 的方格图，第一个是初始图，第二个是目标图，里面都有红绿蓝三种颜色。 现在有三种操作：顺时针旋转 $90^\circ$，逆时针旋转 $90^\circ$，把某个位置颜色换成另一个颜色。 求最少需要多少次操作可以把初始图变成目标图。 ## 思路 首先，我们要发现一些性质：…

## 题意简述 有一个长为 $n(1\le n \le 2\times 10^5)$ 的字符串 $s$，每个位置要不然是 `.`（洛谷原题面写的是字母，感觉应该是翻译的问题），要不然是 `#`。从位置 $k(1\le k \le n)$ 出发，方向向右。保证该位置不为 `#`。每个单位时间向当前方向走一步，然后： -…

## 前言 bfs 板子题。 ## 题意简述 给定一个 $n\times m$ 的网格图，从左上角开始，每次必须移动到不同颜色的格子，求移动到右下角的最小步数。 ## 思路 看到这题，很容易想到搜索。那么，我们应该选择什么搜索算法（bfs 还是 dfs）呢？ 这里我们要看看两种算法的区别：dfs 是“不撞南墙不回头”，…

在讨论《求题》回复：

@[Charles_with_wkc](luogu://user/1015002) https://www.luogu.com.cn/problem/P14313

在讨论《求题》回复：

@[New_Void](luogu://user/1048576) 随便哪题都行吧

在讨论《斤氏后人，如果你20pts》回复：

疑似 miya 姐姐说 P 话。

在讨论《蒟蒻被这题严肃拷打求调》回复：

@[New_Void](luogu://user/1048576)看不懂代码。

在讨论《蒟蒻被这题严肃拷打求调》回复：

@[New_Void](luogu://user/1048576) 你这不会算重吗

在讨论《蒟蒻被这题严肃拷打求调》回复：

啊是空函数巨佬在P，我没救了

在讨论《二分答案最后输出l，middle还是r啊啊啊啊啊》回复：

@[yongshao](luogu://user/1015008) 对的（不好意思没看到）

在讨论《二分答案最后输出l，middle还是r啊啊啊啊啊》回复：

@[yongshao](luogu://user/1015008) 没事 都一样（因为我讲的时候根本没看你代码实际写了啥，就是拿你的判断举个例子）

在讨论《二分答案最后输出l，middle还是r啊啊啊啊啊》回复：

其实这个技巧的本质在于（我拿你这题的代码举个例子） ```cpp if(cnt>=m){ l = mid+1; } ``` 这里是如果当前mid满足条件，那么`l = mid+1`。所以 $l-1$ 总是满足条件的，而二分的性质可以保证 $l$ 肯定不满足条件，所以输出就是 $l-1$ 也就是二分结束后的 $r$。

在讨论《二分答案最后输出l，middle还是r啊啊啊啊啊》回复：

@[yongshao](luogu://user/1015008) 对于你这种二分风格 我有个技巧 首先你这种二分结束以后肯定满足`l = r+1`。（不用解释吧） 然后你看一下答案是越大越容易满足条件还是越小越容易满足条件。如果是越大越容易满足，输出 $l$（因为结束以后 $l$ 更大），反之就输出 $r$。

## 前言 很好的一道 DP 题，但是要对图论的概念有所了解。 ## 前置芝士 ::::info[DFS 中的边概念]{open} 首先，对于一张**有向图**做**深度优先遍历**，把所有遍历到的边放进一个森林里，形成的森林叫做**深度优先森林**（当然很多情况下最后形成的是一棵树）。例如，图中的深度优先森林可以长成…

在文章《题解：P3441 [POI 2006] MET-Subway》发表评论：

@lujunxuan123 感谢提醒，已改正

在讨论《20pts AC #3#4求助！》回复：

ber你们要把这个求助帖打造成神帖吗（）

rt，样例过了（虽然样例确实很水）。 ```cpp #include using namespace std; #define int long long int n,dp1[5005],dp2[5005],id[5005],vis[5005],maxn; struct node{ int to,d; }; struc…

## 题目翻译 ### 题目描述 有一个 $n\times m$ 的网格，将其中所有格子从 $1$ 到 $n\times m$ 编号，第 $i$ 行第 $j$ 列的格子编号 $(i-1)\times m+j$，现给定一长度 $n\times m$ 的序列 $a$，表示填充格子的顺序。如果 $a_b$ 填充完了后，有一行…

注意，若查询时 $u = v$，请特判（可行）。

在讨论《警示后人》回复：

@[Charles_with_wkc](luogu://user/1015002)我是不能理解 这么简单的题为啥会有人想到明显不正确的状压 DP

在讨论《tell 后人》回复：

@[Charles_with_wkc](luogu://user/1015002) 堆的时间复杂度多个 log，很明显deque更优

在讨论《tell 后人》回复：

@[Charles_with_wkc](luogu://user/1015002)这个很显然吧 0-1 bfs 肯定要用 deque 啊

## 前言 比较简单的一道题，有点诈骗。 ## 题意简述 给定两个长度分别为 $n,m(1\le n \le 2\times 10^5,m \in \{n,n+1\})$ 的数组 $a,b(0\le a_i,b_i\le 10^9)$，从 $b$ 中选 $n$ 个数排列，得到新数组 $c$，求 $\sum\limits…

## 前言 比较简单的一道题。 ## 题意 给定一个非负整数 $n(0\le n\le 10^9)$。每次操作把 $n$ 变成 $\left\lceil\dfrac{n}{2}\right\rceil$，求 $k(1\le k \le 10^9)$ 次操作后 $n$ 的值。共 $T(1\le T\le 10^3)$ 组…

在讨论《O(n^2)过 5e4???》回复：

@[RainySoul](luogu://user/654577) 不一定。$10^9$ 的代码只有常数很小的时候才能跑

## 前言 感觉和分块没啥关系，只是要用到了一点点分块的思想。个人认为难度和[数列分块入门 $1$](https://www.luogu.com.cn/problem/P13976) 差不多。请先保证会上面那道题再来做这题。不会的话可以学一学，[我的题解](https://www.luogu.com.cn/articl…

## 前言 和[数列分块入门 $2$](https://www.luogu.com.cn/problem/P13977) 思路差不多，如果做过思路部分可以基本略过。如果没做过，那么最起码要会做[数列分块入门 $1$](https://www.luogu.com.cn/problem/P13976)，最好[数列分块入门…

## 前言 不知道为啥这个算入门题，感觉有一点点思维。 最起码会做[数列分块入门 $1$](https://www.luogu.com.cn/problem/P13976) 之后再来做本题，最好[数列分块入门 $4$](https://www.luogu.com.cn/problem/P13979) 也要了解一下。如果…