BestCoder #17

题目链接

嗯……这场是我们出的,好像的确是难了吧。 但这些题在自己看来还是很棒的啊尤其是03,被诟病也都无所谓了。

1001 Chessboard

首先,若$n \lt k$,则棋盘连一个$1×k$的矩形都放不下,输出$0$。 我们只需要考虑$n≥k$的情况。将棋盘类似于黑白染色,按$(i+j)$模$k$划分等价类,给每个格子标一个号。 标号之后,会注意到每条从左下到右上的斜线数字都是相同的,那么对于$s×s$的格子,其内部数字有且恰好有$2s-1$种,所以当$s<={k\over2}$的时候,内部数字有$floor({k\over2})*2-1\lt k$种,所以不能有更佳的方案。 从而证明最优的方案一定是仅剩下一个$s×s$的正方形区域没有被覆盖到,其中$s≤{k\over2}$。 而令$l=n$ mod $k$之后,根据$l$大小的不同,可以构造出中心为$l×l$或$(k-l)×(k-l)$的风车形图案,又通过上面证明这个$l$(或$k-l$)就是之前的$s$,所以是最优的。 所以令$l=n$ mod $k$,如果$l≤{k\over2}$,最多可覆盖的格子数即为$n^2-l^2$,否则为$n^2-(k-l)^2$,显然这样的方案是可以构造出来的(风车形)。

1002 Select

给定一些集合,选择两个来自不同集合的数,加和大于$k$,问有多少种选择方案。 答案=从所有数中选择的两个加和大于$k$的数的方案数-在同一个集合中选择的两个加和大于$k$的数的方案数 而对于同一个集合中选择的两个加和大于$k$的方案数是可以直接排序然后利用双指针或者二分快速统计出来。

1003 The K-th Distance

把所有边$(u,v)$以及$(v,u)$放入队列,队列每弹出一个元素$(u,v)$,对于所有与$u$相邻的点$w$,如果$w\not=v$,就把$(w,u)$入队,这样就能一个一个生成前$K$小的距离。 注意到每条边实际上会入队两次,只要把$K$翻倍且把ans除以2即可,时间复杂度为$O(n+K)$

1004 RootedTree

题解: 做法一: 状压dp,先考虑二叉树的情况,设$f[opt]$为以opt(二进制状态)中所有节点构成一棵有根树的方案。则我们每次需要枚举以哪个节点为根和哪些节点放在左子树,然后剩下的节点放在右子树,最后将两棵子树的方案相乘累加到$f[opt]$。但是这样做可能会重复,我们可以随便固定某个节点一定在左子树,这样就可以解决重复的问题。多叉树可以通过左儿子右兄弟的方法转化成二叉树的问题,这时只需要加一维状态$f[opt][0/1]$, 0的意义和二叉树一样,1的意义是以$opt$构成一个有根树森林的方法,转移方式和二叉树类似。dp的状态总数为$O(2^n)$,转移先枚举根节点再枚举子集,所以总复杂度为$O(n3^n)$。

做法二: 还是状压dp。记录$sum[mask]$代表点集为$mask$的合法有根树方案数,$sub[mask]$代表点集为mask的合法森林方案数,$dp[mask][j]$代表点集为mask且以$j$为根的有根树方案数。 $dp[mask][j] = sub[mask - {j}] (L_j <= |mask| <= R_j)$ $sum[mask] = \sum_{j=0}^{n-1}dp[mask][j]$ $sub[mask]$的求法和做法一相同。

由于求森林的时候不需要枚举根,所以求sub的复杂度为$O(3^n)$,求$dp$ 和$sum$的时候不需要枚举子集,时间复杂度为$O(n2^n)$ ,总复杂度为$O(3^n)$。

吐槽:原本想吐槽的太多,现在已经懒得吐了。