大家好，这里是第二次参与造比赛工作的jiry_2..

承蒙大家的厚爱，在UOJ一周年零一个礼拜之际，参赛人数创历史新高啦owo

这次的UER好像又造的有点偏难了？不过讲道理这已经比上一场UER简单了很多了吧..

因为有很大一部分内容是JRY熬夜意识模糊下的产物，所以出现了什么纰漏也请大家多多包涵QAQ

[upd]因为A题题解写的比较仓促所以题解写错啦QAQ现在已经更正

[upd]感谢数学迷 nneztlk 提供C题等式的组合解释owo

[upd]A题题解的公式一个变量打错啦..现在已经更正。

[upd]A题中点数为 $300860$ 的数据已由 lll6924 构造出。

万圣节的南瓜灯

By Picks

算法一

原问题相当于判断删除一些格子后的网格是否是一棵树。所以我们可以直接把图建出来然后用并查集来判断。

时间复杂度 $O(nm \alpha(nm))$，期望得分50分（多良心）。

算法二

可以发现当 $nm$ 很大的时候，这个网格一定不是一棵树。因为树满足点数恰好比边数大1，所以就存在不等式：

$$ nm-K > 2nm-m-4K $$

即 $nm < 3K+m$，所以在 $nm > 4 \times 10^5$ 的时候就可以直接输出 No 了，否则就用算法一来暴力判断。

注：$nm=3 \times 10^5$ 的 Yes 数据可以用如下方式构造：$n=10^5,m=3,K=10^5$，所有满足 $x \equiv y \pmod{3}$ 的格子 $(x,y)$ 被破坏了。$nm=3 \times 10^5 +1$的数据已经由 bzoj构造出，如果能早出更大的数据请直接联系我，我会把它添加到题解以及extra test中，谢谢。

万圣节的数列

妹红多萌啊！

大家好这里是扔了一堆错误数据给 jiry_2 的 BillXu2000

算法一

暴力枚举所有的置换，取等差子序列最少的就行啦！

如果用dfs的话时间复杂度是$O((n+1)!)$的。可以拿到$20$分哦！

算法二

我们先来打个表……诶好像长度为$\leq 10$的排列最优解没有长度$\geq 3$的等差子序列！

我们只要打个表，然后把所有数值相等的数放在一起就好啦！

时间复杂度是O(n)的。可以拿到另外的$20$分哦。

算法三

这题这么sxbk一定有结论！诶好像排列都没有长度$\geq 3$的等差子序列！

我来试着构造一下……你看只要分治就好啦！我们先将原序列排序，设$ans_{i}$为排序后答案第$i$位的数值。

对于一个区间$[l,r]$，我们先分治处理$[l,\lceil \frac{l+r}{2}\rceil ]$与$[\lceil \frac{l+r}{2}\rceil +1,r]$。

然后将左区间内的数$\times 2$，右区间内的数$\times 2-1$就可以啦。

为啥这样是对的呢？因为长度为三的等差数列的首项与末项必定同奇偶，然而在我们递归的过程中保证了不会出现这种情况！

时间复杂度是$O(nlogn)$的。又拿到$20$分啦！

算法四

我觉得吧……既然你会做算法三，推广一下就可以啦！

结论是不可能出现公差不为零的长度$\geq 3$的等差子序列。

对于一个区间$[l,r]$，我们只要把奇数全都丢到这个区间的左边，偶数全都丢到右边，所有数右移一位，递归处理就好啦！

时间复杂度是$O(nlogn)$的。AC啦！

吐槽

Q:这题时间复杂度是$O(nlogn)$的，为啥数据范围只有$500$？

因为出题人想了解一些其他靠谱算法哦！

(其实是误导你们

((真实情况是我们只会写$O(n^{2})$的spj

扩展问题：你们可以想一想算法三的spj怎么做到$O(nlogn)$。

万圣节的糖果

大家好这里是冒充 shanquan2的BillXu2000。

算法一

我们可以先无视集合的顺序进行计算，然后再$\times n!$。我们之后的算法都是基于这一点来做的。

然后回溯一下就好啦！

时间复杂度是$O((\frac{n}{2}!)^{2})$。应该能拿到$20$分吧……(拿不到别打我

算法二

我们令$f[i][j][k]$表示$1~i$这$i$个糖果分成了$j$个最后一个糖果奇偶性与$i$相同，$k$个最后一个糖果奇偶性与$i$不同的集合时的方案数。

那么$f[i][j][k]=f[i-1][k+1][j-1]\times (k+1)+f[i-1][k][j-1]$。

状态$O(n^{3})$，转移$O(1)$，所以时间复杂度为$O(n^{3})$，可以拿到$50$分哦！

算法三

我有一个绝妙的解法，但是这里空白太小了，写不下。

时间复杂度为$O(n^{2}logn)$，可以拿到$70$分哦！

算法四

我们来讲故事！

正当红包在计算方案数时，BillXu2000敲开了红包家的门，高呼着“泉岭精神不朽，汉中诸球永生”的口号冲进来传教。

红包告诉了BillXu2000他正在想的问题，但是BillXu2000过于泉岭精神，并不能算出方案数。

于是，BillXu2000开始鏼划另一种划分糖果的方案，他想的方案与红包的十分类似，但是唯一不同的是BillXu2000希望每个集合中的糖果奇偶性相同。

以下为BillXu2000的思路：

设$g[i][j]$为将i个不同的数划分成$j$个集合的方案数。

$$ g[i][j]=g[i-1][j-1]+g[i-1][j]\times j $$

设$dp[i][j][k]$为bx2k的划分的方案数，定义同$f$。

$$ dp[i][j][k]=g[\lceil \frac{i}{2}\rceil][j]\times g[\lfloor \frac{i}{2}\rfloor][k] $$

“我算出来啦，是#@%！”BillXu2000逗逼地说。

“为啥我也算出来#@%?”红包并不能理解。

BillXu2000发现他不小心把自己带来的一颗糖算进了答案。

经过他们俩一番思考，他们发现$f[i][j][k]=dp[i+1][k+1][j]$。

在窗外的你偷偷地把这个解法实现，交到了uoj上。

“这样的话只要$O(n^{2})$次计算就可以出结果呢……"你趁着夜色逃了回去。

证明

这题可以用归纳法证哦！

当$i=1$时，只有$j=1,k=0$时方案数为$1$，其余方案数均为$0$。

当$i>1$时，若对于任意$j,k$，满足$f[i-1][j][k]=dp[i][k+1][j]$，则

$$ f[i][j][k]=f[i-1][k+1][j-1]\times (k+1)+f[i-1][k][j-1]=dp[i][j][k+1]\times (k+1)+dp[i][j][k]=dp[i+1][k+1][j] $$

就证好啦！

这个思路是不是很自然呢？

证明二

不自然！

比赛结束以后已经有好多人这么抱怨啦..UOJ萌萌哒的题目也被点了很多差评..

这个时候数学迷英勇地站出来拯救世界啦！

（以下是JRY从评论区贴过来的原话

对于一个分拆我们把每个集合都从大到小排序，然后一个数$x$只要不是所在集合内的最大数，就会有一个前驱（就是所在集合内最小的比它大的数）。

然后对于一个红包分拆，我们添加一个单元集$\{i+1\}$, 然后对于一个数$x$, 如果它是所在集合内最大数，就不动它；如果不是，就令它的前驱为原来的前驱加一。（我们可以从大到小枚举每一个数，这样依次定下每个数后来的位置）就得到了一个BillXu2000分拆。

这样变化之后的拆分显然有$k+1$个最大数和$i+1$奇偶相同的集合（原来的$k$个再加上$i+1$本身）和$j$个最大数和$i+1$奇偶相异的集合（即原来的$j$个），然后逆变换也很显然。

这就证明了$f[i][j][k]=dp[i+1][k+1][j]$。

这样是不是就兹瓷了许多啊..

最后还是要感谢业界良心的数学迷提出了一个这么直观的解释owo