提高组复习『拓展算法』

Tip：这里介绍的是不在提高组考纲内，却仍然非常实用的万能算法。在提高组的比赛中甚至能碾压正解，拥有奇效。 # 拓展算法 - ## 模拟退火 小范围数据的万能算法。掌握一个随机算法，增强骗分能力。 **入门**： - [**[HAOI2006]均分数据**](https://www.luogu.com.cn/problem/P2503) - [**Haywire**](https://www.luogu.com.cn/problem/P2210) 模拟退火不只是随机。solve函数和随机的变量也是有思维难度的~~（如果是欧皇可以忽略）~~。 **提高**： - [**[JSOI2008]球形空间产生器**](https://www.luogu.com.cn/problem/P4035) - [**[SCOI2008]城堡**](https://www.luogu.com.cn/problem/P2538) - ## 网络流 虽然不是万能算法，但有时却能轻易解决非常难的题目。 **入门**： - [**【模板】网络最大流**](https://www.luogu.com.cn/problem/P3376) - [**【模板】最小费用最大流**](https://www.luogu.com.cn/problem/P3381) ~~鲁迅说过~~，网络流代码只有普及组难度，建模才是难点。无论多离谱的题目，也许都能建模。 **提高**： - [**餐巾计划问题**](https://www.luogu.com.cn/problem/P1251) - [**负载平衡问题**](https://www.luogu.com.cn/problem/P4016) - ## 树链剖分 树上问题的万能算法。常常可以将树上的思维题转化树链剖分的通解。 **入门**： - [**[HAOI2015]树上操作**](https://www.luogu.com.cn/problem/P3178) - [**[ZJOI2008]树的统计**](https://www.luogu.com.cn/problem/P2590) 树链剖分的方式大同小异，但是其中的线段树维护的方式变化很多，要灵活运用。 **提高**： - [**[SDOI2011]染色**](https://www.luogu.com.cn/problem/P2486) - [**[NOI2021] 轻重边**](https://www.luogu.com.cn/problem/P7735) - ## 分块 数据结构的万能算法。万物皆可用分块维护，运用范围非常广。 **入门**： - [**【模板】线段树 1**](https://www.luogu.com.cn/problem/P3372) - [**【模板】线段树 2**](https://www.luogu.com.cn/problem/P3373) 分块的缺点是 $O(\sqrt n)$ 的时间复杂度以及构造。所以，卡常与处理块的技巧是不可或缺的。 **提高**： - [**[Violet]蒲公英**](https://www.luogu.com.cn/problem/P4168) - [**[Ynoi2017] 由乃打扑克**](https://www.luogu.com.cn/problem/P5356) - ## 莫队 离线处理的万能算法。将难题离线处理后，问题总能简化。 **入门**： - [**小B的询问**](https://www.luogu.com.cn/problem/P2709) - [**数列找不同**](https://www.luogu.com.cn/problem/P3901) 区间转移是莫队的难点。有时甚至要套上其他数据结构来进行转移。 **提高**： - [**[AHOI2013]作业**](https://www.luogu.com.cn/problem/P4396) - [**可怜的狗狗**](https://www.luogu.com.cn/problem/P1533)