序列
本题作为一道签到题考察了选手对题意操作的转化能力以及对于最优解模型的理解。
算法零
乱搞。
算法一
对于所有$a_i\geq 0$的点直接输出序列最大值，为什么后面会讲。可能打表选手也能发现。
复杂度$O(n)$。
期望得分12。
算法二
考虑原序列的前缀和序列$b_i=\sum_{j=1}^{i}a_j$，每次操作相当于交换$b_i,b_{i+1}(1\leq i\leq n-2)$，所以无限次这个操作之后相当与把$b_i$任意重新排列。我们的目标变成了$max_{i=1}^{n}|b_i - b_{i-1}|$相当与固定起点$b_0$和终点$b_n$你要重新排列中间的其他数。
这也就是为什么$a_i\geq 0$的时候答案是最大值了，因为$b_i$递增，答案是理论下界。
我们直接暴力枚举所有$b$的全排列，计算每一种的答案。
复杂度$O(n!n)$
结合算法一，期望得分40。
算法三
我会状压DP。
考虑把全排列变成状压DP，$f_{\{S\}i}$表示使用了$\{S\}$集合内的所有数最后一个数是$b_i$的最小值。
复杂度$O(2^nn^2)$。
结合算法一，期望得分52。
算法四
不妨设$b_n\geq 0$，我们称连续递增/减的数是一段，则最优的排列方法分为三段（如果大于等于四段你考虑你可以合并中间至少两段值域在$[0,b_n]$之间的数使得答案不会变的更劣）---从0到最小值，从最小值到最大值，从最大值到$b_n$。
我们再从值域考虑（从现在开始段的定义不同于上面），第一段从0开始逐渐递减然后再递增到最后一个小于0的数，这一段包含所有$\leq 0$的数。第二段包含所有$[0,b_n]$之间的数。第三段：从第一个大于$b_n$的数开始逐渐递增然后再递减到$b_n$，这一段包含所有$\geq b_n$的数。
中间那一段显然是递增排列，第一段和第三段是一样的可以一起考虑。以第一段为例我们从大往小加数，像一个V字形，可以看成是两边往中间加。
我们设$f_{ij}$表示V字的左边最小值为第$i$个数，右边为$j$的最小答案。转移$O(n)$需要枚举下一次的一整段放到一边。
复杂度$O(n^3)$。
结合算法一，期望得分72。
算法五
我们发现一定对于一个V字形一定是从大到小，一个放在左边，一个放在右边，一个放在左边....为什么呢，因为考虑第一个不满足这个的位置，我们把后面更小的左右反转显然答案不会变的更劣。
直接模拟即可，但需要排序。
复杂度$O(nlogn)$或$O(n)$（基数排序）。
期望得分100。
随机
本题考察了选手在动态规划，二分技巧方面的知识。
本题可能题意有点绕，实在是抱歉在下语文水平欠佳。
算法零
乱搞。
算法一
设$f_{ij}$表示当前在$i$，已经走过$j$的时间的答案，显然转移有重开和往下走两种。
直接暴力枚举每个转移是重开还是往下走并计算。
复杂度$O(2^{nmw}nmw)$实际上根本到不了。
期望得分12。
算法二
发现如果$f_{ij}$选择重开则$f_{ij+1}$一定也是重开。
暴力枚举分界点。
复杂度$O((mw)^{n+1}n)$
期望得分20。
算法三
三分套三分套三分???
不知道能不能把6号点过掉?
算法四
对于所有边起点都是$1$的数据直接解个方程就好了。
复杂度$(n+m)$。
结合前面的算法可以得到40-44分。
算法五
对于外向树的点，我们发现每个点只有一条从$1$到他的路径，所以我们可以直接枚举每个点是否重开。
复杂度$O(n2^n)$。
结合前面算法能得到56-60分。
算法六
对于外向树，设答案为$x$，设每个点的答案为$f_i$，则$f_i$一定可以被表示成$min_{k}[a_kx+b]$的形式也就是一堆关于$x$的一次函数取min。
为什么呢，你考虑如果一个点的儿子全都是这个形式的话，你的转移是一个线性变换再和$x$取个min所以仍然是这个形式。
然后你可以暴力维护出所有这样的线然后算答案。
复杂度$O(n^2)$。
结合前面的算法期望得分68-72。
算法七
为什么算法6不能放在图上呢。首先你要受到值域的限制，其次我可以构造一个类似链但是相邻节点有多条边的图你的直线数量就是指数级的。
所以我们不能显式的维护。
考虑最后算答案的时候我们要算两个函数的交点，除了直接解以外我们可以二分$x$，二分之后每个点在每个值域下的状态的从若干条直线变成了一个值。
具体来说就是二分$x$之后，每个点的转移有两种一种是直接走$x$另一种是往后走。
最后看一下第一个点算出来的最小值和$x$的差。
时间复杂度$O(nmwlogANS)$。
实际上可用状态没有那么多。
当然你也可以理解为给你增加一个以$x$的的时间结束游戏的按钮，如果你在一开始就按了说明原本答案大于$x$，否则如果你走下去了说明原本答案小于$x$。
期望得分100。
计数
本题是个诈骗题，其实是一道非常裸的群论基础题，你只要会polya/burnside并且敢上就能过。
算法一
枚举所有可能值判断是否同构。
复杂度$O(???)$。
期望得分8。
算法二
对于所有$w2=w3=1$的点我们只需要考虑$w1$。
你把所有的情况都变成最小表示就变成了一个经典的组合问题。
答案是$\tbinom{n+w1-1}{n}$。
复杂度$O(n)$。
期望得分24。
算法三
我会群论！
直接枚举所有可能$n!$种置换，对于每种置换算出不动点数和对应答案。
不会群论的同学请自行上网百度哦(OwO)
时间复杂度$O(n!(n+logw))$。
结合前面的算法期望得分48。
算法四
发现答案只跟每种循环节个数的情况有多少种，换句话说，每种置换只有不动点数重要，也就是说我们可以枚举置换的每个环长。
我们惊喜的发现：50的拆分数只有204226!
然而你可能需要一些卡常技巧比如预处理gcd。
复杂度$O(204226\times n^3)$，其实远不到，因为里面算不动点的$n$是循环个数，（又没有人会证一个更紧地下界）。
期望得分100。
一些事
本场考试有1人AK，所有至少提交了一份代码的人的平均分是：158分整。
符合赛前预测。
"本场比赛并没有难度顺序"-----个鬼啊！（只是想让大家多看看想想后面的题）
这次考试的前两题都是我曾经给蓝桥杯供的压轴题。
第三题是改自外省某训练题。
这次考试中间题意出了一点锅以及这次考试的部分分设计可能或多或少有一些不合理，给大家道歉。
希望我的题能让大家学到知识和掌握技巧，并享受这场考试。
