前言

单调队列一种非常经典的将O(n^2)的DP优化的O(n log n)的方式，在一个点可以更新一个范围的时候可以发挥很大作用。

记得当年NOIp2017我考PJ（那年的T4考到了单调队列），当时还不会，在考后听教练讲了一遍之后仍旧处于懵逼状态，大概1个月前照着题解打了一遍，但是到了现在已经忘得差不多了QwQ，于是写了一遍优化过的多重背包来练练手。

$$ \texttt{ Writer：世界最蒻Dilute}$$

$$\texttt{ #A 某脱碳甲醛的电磁炮题}$$

$\texttt{ 出题人 Dilute}​$

电流公式$I=\frac{U}{R}$大家都知道（不知道的话在题面中也给出了）

所以直接输出就可以了（ps：C++中除法自动向下取整）

首先我们考虑一件事：如果存在一个人，使任何一个人都不认识，我们称这种人为“孤独”的人，那么警察只能通过调查他来取得他的身份。

然后对于一个不“孤独”的人，我们发现他们肯定至少被一个那些“孤独”的人直接或间接的认识。

所以我们得出结论：只要统计“孤独”的人的数量即可。

你照着这么做，就可以获得100 mod 10分的好成绩。

一道非常好的练倍增的题目

思路很简单，就是倍增处理出每个点往后$2^i$个点的路径权值和与最小值，同时要注意一下$k​$要用longlong存，否则会挂掉

如果不会倍增的右转百度找其他博客去吧……我这里就不赘述了

欧洲退火！

没错你没有看错这么一道Heap的题我拿出了退火来做！

那么模拟退火的基本思路这里不讲了如果要看右转P1337去看。

废话不多说，上思路

竟然没有人写题解2333那本蒟蒻就来$H_2O$一篇吧

首先，看完题面不难想到DP，之后再看数据范围考虑$O(N^3)$DP，之后瞎搞一通可以想到

$f[i][j]$表示在前$i$个里面经历$k$次出逃可以取到最少的修改数

那么接下来我们就发现$f[i][j]$可以影响的范围为$f[u][j+1]$($i < u ≤n$)，然后我们就可以写出如下的程序：

暴力赛高！暴力是全世界最最最（以下省略2147483647个人最）NB的算法！

AC记录

这里似乎没有朴素的算法啊（啊当然Pascal不算哈）

我开始做题的时候还专门为了求稳去学习了一下$nlogn$的最长上升子序列呢

其实我们会发现，暴力的时间复杂度其实根本不是$O(n^2)$，就让我们来分析一下暴力的时间复杂度。

令人智熄的二分操作

AC记录

要看正常的解法请看其他题解

而且还蛮快的。。。

其实，这是非常奇葩的一个想法

总体思路就是：二分答案

你没听错，二分答案

我们从题面中可以看到，其实这道题的拥挤度也就$10000$而已，所以我们就会发现二分似乎可以？？？

存图存完之后直接二分，二分的$Check()$里面打一个$BFS$，来求能否通往终点，就好了

具体的东西就上代码来看吧

STL大法好！

（看到楼下的大佬们都没有用我这个方法，我就来脱碳甲醛一下辣~~）

以上都是废话

我所说的这个方法，具体思路是这样的：

• 最首先，基础的并查集大家应该都会，如果不会的话可以看代码或者出门右转P3367并查集模板
• 然后，STL中的Map可以直接方便地解决字符串哈希的问题
• 但是，每次都用一遍Map似乎显得有些不优美，似乎有些慢的说
• 所以，我们需要引进两个数组，一个Num和一个Names
• Num是一个Map，它的作用就是Num[“A”]表示名为A的人的编号
• 于是，Names就是反过来的Num，Name[i]表示编号为i的人的名字
• 总体而言，不仅加快了速度，还方便了调试