开学前的作文

by Starzxy

首先，光标移动范围不可能超出 $(1,1)-(n,m)$ 的方格。其次，只有 →，↓ 与 Fn 是有效的按键。（很显然吧……

算法一

枚举每一种不同的操作,时间复杂度$O(3^{n+m})$。可以获得10分。

算法二

设 $N[x],x\in$｛↓ , →｝表示按下 $x$ 键后光标行位置的变化。

设 $M[x],x\in$｛↓ , →｝表示按下 $x$ 键后光标列位置的变化。

用 $F[n][m][k_1][k_2]$ 表示光标移动到第 $n$ 行第 $m$ 列最后分别按下的 ↓，→ 或未进行按键操作是 $k_1$ 与 $k_2$，则 $F[n][m][k_1][k_2]=min(F[n-N[k_2]][m-M[k_2]][k_x][k_1],F[n-N[k_1]-N[k_2]][m-M[k_1]-M[k_2]][k_1][k_2])+1$，$k_x$ 为任意操作，$\mathrm{DP}$ 可以做到 $O(nm)$ 的复杂度。可以获得50分。

算法三

对于只有一行或者一列的情况，多枚举一些就能找到规律。（啊啊啊就在右（下）边我要拼命按右（下）按Fn！

可以获得20分，结合算法二可以获得70分。

算法四

若没有 Fn，最优操作序列必然是 $x$ 个 ↓ 加上 $y$ 个 →，且操作序列中任意两个元素可交换。

由于加入了 Fn，我们就希望通过改变序列排列使得重复的尽可能多的靠在一起被 Fn 消去。

设 $n\le m$，经过尝试（对拍）我们发现 ↓，→，Fn，Fn……Fn，（$1$ 或 $2$ 个 →），Fn，Fn……Fn 为最优操作。时间复杂度$O(1)$。可以获得100分。

AC代码在这

开学前的日历

by loriex

算法1

10pts，应该讲什么呢。。。

算法2

10pts，直接暴力搞每个操作，组合数预处理，$O(n^2q)$

算法3

10pts，注意到$q$很大而$n,m$很小，则最多有$O(n^3)$个不同的操作，合并相同操作之后暴力，$O(n^5)$

算法4

20pts，再次考虑每一个操作，定义新的操作$G(u,v,k)$表示$F(u,v,k)-F(u,v,k-1)$，则一个$F$操作可以分解成$O(n)$个$G$操作，把题目所给的$F$操作分解成G操作之后最多也只有$O(n^3)$个不同的$G$操作，然后暴力进行$G$操作，一次$G$操作是$O(n)$的，总复杂度$O(n^4)$

算法5

20pts，对于$F(u,v,k)$操作，我们从$0$到$k$枚举$i$，然后对于点$(u+i,v+k-i)$，我们把它加上$\binom{k}{i}$。进行完所有操作的复杂度是$O(nq)$的，然后我们$dp[u][v]+=dp[u-1][v]+dp[u][v-1]$。$u$从$1$到$n$枚举，$v$从$1$到$m$枚举。总复杂度$O(nq+n^2)$。听说没卡常数的同学也能拿10pts。

算法6

30pts，对于$F(u,v,k)$操作，$dp[u][v][k]$++。进行完所有操作后，$dp[u][v][k]$+=$dp[u-1][v][k+1]+dp[u][v-1][k+1]$。进行完这一步后，$dp[u][v][0]$+=$dp[u-1][v][0]+dp[u][v-1][0]$。

其本质是有$q$个源点，对于每一个点，求有多少条从源点向下或向右移动抵达它的路径。

但是加上了距离限制$k$，索性用加维的dp来解决。

出题人很良心的设了梯度数据XD

开学前的涂鸦

by jiry_2

其实这题根本不是我出的..本来给了vfk一道傻逼题想弥补我从来没有出过A题的遗憾，结果和懒癌一样喜闻乐见的被改成了C。

这道题目不算特别难，但是不同的做法还是有很多的..这儿就简单介绍一下（其实是为了拖篇幅让它显得很厉害的样子）。

算法一

对于$k=1$的点，显然连出来的图是一个基环外向树。方案数是环的大小+1。DFS找一下环然后输出就好了。

期望得分10分。

算法二

对于$k=2$的点，我也不知道有什么做法..不同状态数还是挺少的，估计分类讨论每种情况算算就行了？如果你写了标算但是细节写炸了，这一部分分就送给你了，当做是安慰吧..

算法三

把额外加的边的两端作为关键点，然后建原树上这些节点的虚树，再把额外加的边连上去。这样就得到了一个点数至多$4k$，边数至多$5k$的图。我们把这一张图的边权$w_i$设为它是由原树上多少条边缩成的。那么可以发现对于这张图的每一个联通生成子图，它的贡献是$\prod_{i \text{被删除}}w_i$。（接下来所有算法讨论的图均为缩点之后的图）

所以只要枚举所有生成子图，判断一下这一张图是否联通，如果联通就计算一下贡献然后累计到答案中。时间复杂度$O(2^{5k}m)$，期望得分30分。

算法四

其实题面是拿来误导你的，树边和额外边根本没有区别。所以可以直接把最终的图连出来，然后随便找一棵DFS树当成初始树然后非树边当成额外边。

这样的好处在于所有的额外边都变成了返祖边。这样算法三建出来的虚树点数至多为$3k$，边数至多为$4k$。

再使用算法三中的算法，时间复杂度就变成了$O(2^{4k}m)$，期望得分50分。

算法五

算法三和算法四在处理的问题其实就是对于一张没有特殊性的图，怎么求它的联通生成子图的权值和。

这个显然是可以容斥的，因为这个算法对处理这个问题来说没有什么好的效果，就不多说了。时间复杂度$O(3^{3k})$，期望得分50分。

算法六

因为这张图的边数相对点数来说是很少的，只比点数多一点点，可以猜测可能联通生成子图的数目很少。所以算法三算法四的枚举大部分都是无用功。只要有一种快速的搜索方法也许就能得到比较高的分数。

接下来就是普及组内容咯..我们把所有边标个顺序，然后按照顺序来搜索删边或者不删边，如果发现删了这条边图已经不连通了，那么就退出。

这样时间复杂度最坏是$O(\text{方案数} \times m^2)$，期望得分50分至60分。

算法七

这个算法由鏼鏼鏼友情提供..

删掉一些边，然后判断一张图连不连通。这个问题大家是不是和眼熟呢？对，就是DZY loves chinese II。

在这题中我们可以把每一条非树边分配一个二进制位，每一条树边的权值为覆盖它的所有非树边的权值和，这样最多有$3k$种不同的权值。删掉一个边集后这张图仍然联通的充要条件是这个边集不存在一个子集的权值异或和为0。证明的话大家可以自行百度DZY loves chinese II。

于是就可以枚举每一个不同的权值的子集，表示删掉这个子集中每种权值各一条边，消元一下看一下是否线性无关。如果用搜索的方式进行，复杂度最坏是$O(2^{3k}k)$，但是因为搜到已经线性相关了就可以退出，所以常数非常小。期望得分70分，而且感觉像是可以A的样子..至于能不能AC就看看有没有老司机愿意写一发咯，至少这个算法要比标算好写到不知道哪里去咯..

当然我们也可以用这个方法来优化算法六判断连不连通的部分，时间复杂度最坏可以降到$O($方案数$\times m)$，期望得分70分。

算法八

最后来讲一下标算。这个算法是叉姐玩出来的！

缩点之后的图依然是有树边和非树边的区分的。我们依然保留树的形态，把其它的边视为额外边，因为所有额外边都是返祖边，所以可以对所有额外边定义下端点和上端点。

令$dp_{i,j,k}$为以$i$为根的子树中，所有下端点在以$i$为根的子树中，上端点为$i$的祖先的额外边的上端点的联通情况为$j$，$i$所在联通块的编号是$k$的方案数。这样显然是可以树形DP的。这个树形DP也没有什么好说的，合并两个子树的时候就是把两个子树的所有状态给合起来得到一个新的状态，然后再把所有同一状态的函数值给并起来就好了。细节比较多..题解里也不可能说得清楚，大家就随意脑补一下吧。

至于复杂度，一个节点的状态数最多为$k \times Bell_k$（$Bell_k$指的是贝尔数，不知道的同学可以百度一下），而合并两个状态的复杂度是$O(k)$的，所以复杂度的一个上届是$O(k^4Bell_k^2)$。

然而考虑合并的过程，考虑合并一个上端关键点个数为$a$的节点和一个上端关键点个数为$b$的节点，它们合并的复杂度上届为$O(ab(a+b)Bell_aBell_b)$。

容易发现的是$Bell_aBell_b \leq Bell_{a+b}$，证明很简单，左边的式子代表了$a+b$个点，前$a$个点和后$b$个点之间没有边的连通性数量，右边的式子代表了$a+b$个点的连通性数量。显然有左边不大于右边。

所以可以得到复杂度的一个上届是$O(k^3 Bell_k)$（至于为什么是$k^3$而不是$k^4$可以看HAOI2015那道树形DP的复杂度），然而常数非常小，对于$k=10$的数据值需要跑30ms左右，$k=11，k=12$的数据跑得也很快。但是为了防止程序被叉，或者比赛的时候有人想到标算但是因为$k$太大不敢写，所以考虑再三把数据范围还是放在了$k=10$。这一点也体现出了我是一个多么业界良心的出题人。

这个算法的细节比较多，由于比赛时间比较紧，如果我每一个subtask都放十几个数据的话可能大部分考场上写标算的人都拿不到比暴力高的分数，所以除了最后一个subtask以外每一个subtask都是随机的五个数据左右，也是希望大家可以得到一个更高的分数。

当然最后一个subtask也只有20个不到的数据，可能会有一些错误的程序AC，到之后就要靠hack的力量咯。

当然我的标程也不见得是对的（大雾）。

最后扯点题外话，最近总有人说我毒瘤，我自己其实很不理解啊..1.毒瘤题基本都不是我出的。2.从数据的分配就可以看出其实我一点也不毒瘤啊。3.不管怎么样也不能再比赛结束看到自己的题目被很多人碾过去之后发出这样的叹息：

最后还是谢谢大家对UOJ的支持啦~(≧▽≦)/~！