显然，我们可以发现一个序列是“好的”当且仅当这个序列中的最大值等于这个序列中的其他数之和相加，所以我们只需要保证序列单调递减，同时维护一下这个序列里面元素之和我们就可以$O(1)$判断一个序列是不是“好的”序列（$a_1 = Sum - a_1$）

由于题目要求求出去掉哪些元素之后，这个序列会变为一个“好的”序列，所以我们只需要把原序列排序之后再按照刚刚说过的办法$O(1)$判断，只需要吧把原序列之中的$Sum$减去我们需要去掉的元素即可

还有一点需要注意，我们需要特判去掉第一个的情况，这样删去后最大值就是原先的次大数，即$a_2$

上代码QwQ

首先我作为一个蒟蒻，拿到字符串题，首先看看能不能无脑哈希

然后于是我们就发现了一个绝妙的做法：暴力枚举每个字符串能够转换成的字符串

于是我们就获得了$O(N * 8^4)$的优秀复杂度

显然会T飞QwQ

我们考虑再这个基础上进行优化

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

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

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

你照着这么做，就可以获得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的人的名字
• 总体而言，不仅加快了速度，还方便了调试