IMMC?
\(IM^2C\)
\[ \begin{align*} 数学剑魔 \end{align*} \]
题目链接
\(Day_0\)
晚上8:00开腾讯会议发题
高中组只有\(A\) \(B\)两道可选
第一题
初印象觉得是\(Floyd\)加搜索或者\(dp\)
但是仔细一看发现不对，如果真搜索那复杂度\(\omicron(m^n)\approx 9^{32}\)
如果以计算机\(10^9/s\)的计算速度粗略估计，那么需要约\(1.0888139967949368\times10^{12}\)个世纪才能完成……
叶老师发了个针对第一题图论的材料，还好我看了看，对后续旅行商的思路有一定的启发
这个时候\(rc\)发现第二问还书量很少，认为不用纠结，事实证明这很有远见
一晚上都在想怎么做第一题正解……
第二题
纯纯的搜资料题
题面里“最近公共祖先”倒是给我兴奋了一把，可惜根本用不到
用不到那你出题人为什么要写它
第一问超级简单，\(rc\)人型计算器加\(Excel\)十分钟搞定，拟合度\(98.58\%\)
不过我们觉得作为第一问显然不可能这么简单，肯定是我们有什么没有考虑到的
事实证明第一问就是这么简单
\(Cyk\)和\(Hyd\)分工看文献
\(Day_1\)
早上起来突然想到\(A\)题好像能判环+“小范围”枚举+差分约束，不过在\(Day_3\)的时候被我发现这个方法有大问题（悲
其实就是学差分约束太久忘记形式了……\(\sum_i x_i\le b\)并不构成差分系统，\(x_i-x_j\le b\)才是
之后去\(cyk\)那里（感谢\(rc\&Cyk\)！
在车上被老师催，决定做\(A\)题
\(rc\)他爸建议手动决策树先求个模糊解
模糊解这个提醒确实把我从坑里拉出来了，并且很大程度上影响了我后续的思路，毕竟这玩意确实很难做到精确
某场外援助说看着像状压\(dp\)并且再次提醒我这好像不是一道\(Oi\)题（正确的，感谢\(Zzy\)！
到了\(cyk\)那里之后开始讨论具体实施
这里我也不知道该怎么做了，只能走一步是一步
8:00叶老师的破题，不能说是意义重大，也可以称得上是毫无卵用了
甚至连\(Dijkstra\)和\(Floyd\)的时间复杂度都讲反了
\[ \begin{align*} Dijkstra&:O(n\log{n})\\ Floyd&:O(n^3) \end{align*} \]
中间顺便上了堂化学课，四个人没一个听的，\(Wcy\)甚至点名提问
\(rc\)开始做源数据的格式化，\(Cyk\)人型计算器先搞出了个第一问可行解，总路程\(90\)多公里，总时间\(5\)个多小时
事实证明，这个可行解已经十分优化
甚至比某组的蚁群算法的结果更加优化
漫无目的逛百度的时候发现了\(vrp\)和\(cvrp\)，\(cvrp\)问题的描述和题面高度相似，思路开始转向
其实这个时候已经查到ortools这个库了，但由于想法上还是局限于精确解，并且\(CSDN\)上的博文质量实在不敢恭维，导致我并没有深挖
中午吃完必胜客！饭把思路捋了捋并决定用遗传算法解决\(cvrp\)
flowchart LR 源数据 --Floyd--> 多源最短路 多源最短路 --拆点法--> 以书本为节点的全连接无向图 以书本为节点的全连接无向图 -.节点一次性.-> 路线规划 以书本为节点的全连接无向图 --cvrp--> 路线规划 源数据 -.连接成环.-> 路线规划 路线规划 --递归枚举--> 结论
开始写\(Floyd\)和拆点法，两个小时搞定
之后就在找遗传算法现有的代码了，从GitHub上下了一个，经过漫长的调试，效果还没\(Cyk\)的可行解快，实在锂镤
此时还没有想好怎么解决充电站单程的问题
\(Day_2\)
早上起来思如泉涌，想到可以添加节点控制单向路径以解决充电桩
到地方之后开始注意ortools
途中省略C++和Python环境调试……
C++调不出来的原因竟是因为ortools不支持Visual Studio Code只支持Visual Studio
抄了个\(CSDN\)代码，效果拔群，第一问路径优化到\(86.7km\)
写完递归枚举之后时间结论优化到了\(4.86h\)
此时我还没意识到手打的辅助点\(id\)写错了
直到晚上差不多把第一问答案搞出来了
开始认真研究\(rc\)找的ortools官方api并发现了自己忽略的很多用法
比如可以添加松弛条件，让机器人在某“多书”站点不取完所有书，也就不必写拆点算法了
\(<0\)有一种语言艺术的美
\(Day_3\)
早上想了个第二问处理充电桩的方法，但是早上和\(Cyk\)讨论发现了误区
和叶老师开了个会，意识到第一问方案很可能可以直接运用到第二问中
\(Cyk\)开始人工校验
\[ \begin{align*} 科技民工！&\\ &——Hyd \end{align*} \]
最终历经波折，第一问的结论真的可以用到第二问！
其中需要把一组的路径规划反过来（环具有对称性）以确保不会超载
下午\(Cyk\)校对的时候发现我昨天辅助点的错误，好在第二天改完之后对第二问影响不大，路径长度甚至优化到了\(86.5km,4.82h\)
\(Day_4\)
居家改论文
实在折磨，\(\LaTeX\)技术力过低，版本控制不力，总之……\(Hyd,rcnb!\)
不过最终还是有很多纸面上的错误
改进
完全不在我的控制范围之内
每一天都出乎意料
从精确解到模糊解
从遗传迭代到引导式搜索
也只是摸着石头过河
下次再发题之后应该有一个更明确地思路，比如这道题就应该直接看出旅行商问题的本质，而不是固执地想精确解，毕竟这真的不是\(Oi\)题
或许是阅历不足的原因罢
VS code Live Share插件共同编辑\(\LaTeX\)论文Git版本控制，合并不同修改Python，一定程度上能减少科技民工的工作量- 尝试使用\(\LaTeX\)画图，如果太难了那就试试矢量绘图软件吧，会好看一些
一定要改，要不然会疯的
……没什么可改的
为数不多体验很爽的小组合作任务