传奇团子师傅题解

传奇团子师傅题解（模拟退火）

申明：

本篇题解借鉴了：

https://www.luogu.com.cn/blog/SDNetFriend/solution-p7218

这篇博客（主要在bitset部分）。

题意：

给你个矩阵，包含三种颜色，一个美丽串要求你横着或者竖着或者斜着串成一串的三个颜色有特定的顺序，求拿取最多美丽串的方案是什么。

题目分析：

1. 先考虑不同的较为优秀的方案区别在哪里。显然的是，他们不同在于至少存在一个颜色会被同时占有。否则的话我肯定可以两个都选择使得答案更优秀，不符合上述假设。
2. 有了情况一的结论，于是我们就可以想到“有你没我，有我没你”的一种抽象转化。然后我就开始往二分图方向去想，却发现一种颜色会用多次（反正就是很难受），最终又想到了一般图的最大独立集。
3. 再次转化，思考怎么建图。显然的是我们不能让共同占有同一个位置的美丽串放在一种方案中，所以建图大方向肯定是向着这边的。因为是以“串”为单位建图，又考虑到每个串是规定了顺序的，以及存在着“反转也成立”的情况，最简单的建图应该是考虑一定在一个串正好中间的 $w$。然后呢，对于能够结成一个串的三个位置上打上这个串的 $id$ 做标记以便于连边，这个过程可以使用 vector 来解决。
4. 现在转化为求最大独立集了，在这个图上求最大独立集就是在他的补图上求最大团。直接硬做的话，可能会达到一次求解 $n^{n/3}$ 这个复杂度，而这个 $n$ 看样子有点大（当然我没学过Bron-Kerbosch也不会做）。于是用模拟退火（听说爬山也可以）来考虑。（但其实反正是提交答案题，不会有太大关系吧）
5. 现在开始考虑模拟退火怎么做了。首先肯定要随便跑出来一个东西作为最初的解吧。然后每一次随机一个点，要求这个点在目前做出的最大独立集中没有出现过。然后把他选进最大独立集中，把和他有矛盾的点退掉就好了。
6. 优化：首先就是参数的问题（调参太痛苦了，所以我嫖的其他题解相对较好的参数）。其次，可以用数据结构来维护没选到的这个点的集合。最后，也像我觉得写得较好的那偏题解一样，可以用一个参数k来放大概率。

代码：

其实我觉得我代码真的不行，会卡很久很久（大概一个午休），建议要用要抄的话可以看看别人的代码，真的不如爬山写得好（蒟蒻的眼泪）。