Codeforces #564 Div.2 小结

比赛链接:Codeforces #564 Div.2 [A, B, C, D]

A: Nauuo and Votes

思路一:数据量很小,枚举所有情况。

思路二:考虑极端情况。

B: Nauuo and Chess

把棋盘看成是一个坐标原点在左上角的$ m\times m$的正方形,当第$i$个棋子排在直线$r + c – 1 = i$上的时候满足$ |r_i – r_j| + |c_i – c_j| = |i – j|$。我们可以确定$m \leq n$,我们让棋子排成一个L形,满足L的两边的长度差尽量小就行了。

L形只是一种情况,假设这些棋子散落在L形内,其实只要满足第$i$个棋子排在直线$r + c – 1 = i$上,并且L的两边的长度差尽量小就行了。假设$i$向$r + c – 1 < i$,会破坏$i$和$i$前面的点的性质,向后移动则破坏后面点的性质。

C: Nauuo and Cards

这是一个比较难想的思维题。

官方的题解是这样的:

首先尝试不打空白牌能否直接完成。如果能就是最优解,否则最优解一定是先打若干空白牌然后再也不打空白牌。计 $p_i$ 为 $i$ 在牌堆的初始位置(初始在手上为 $0$),那么答案为$\max_{i = 1}^{n} \{ p_i + 1 + n – i \}$(每张牌最早在第 $p_i+1$ 张被打出,还要打 $n-i$ 张)。

这里做一些补充。

如何判断不打空牌能否直接完成。这个的前提是存在一个面值为$[1,x]$的连续区间$(x\geq 1)$,在桌子上,并且$x$是最后一张,这个时候我们需要把$[x+1,n]$这个区间里的牌依此放到桌上。考虑到出这些牌之前牌必须在手上,分两种情况——打某张牌之前,已经从牌堆里取出了这个牌,对应代码中的p[now] <= now - last;或者这张牌本来就在手上,那么p[now] <= now - last显然也成立。注意这里的大前提是$1$一定在桌上。

 

D: Nauuo and Circle

这是一个计数问题,首先要转化题目中“没有交点”的条件。这个条件意味着以$u$为根的子树上的点(包括$u$)在圆上都是连续的,否则就会出现这样的情况:


思路一:

那么考虑$f(u)$表示以$u$为根的子树的方案数,$u$不为root时,

$$f(u) = {\rm size}(u) ! \times \prod_{v \in {\rm son}(u)}f(v)$$

即先对$u$和$u$的所有子树全排列,再内部方案计数,使用两次乘法原理。

对于root 点,不一定只能放在儿子中间,而是可以放在任何一个位置,则

$$ f({\rm root}) = n \times ( {\rm size(root)} -1) ! \times \prod_{v \in {\rm son(root)}} f(v)  $$

思路二:

从点的度数考虑。当$u$不是root的时候,儿子的方案有$(d_u – 1) !$个,$u$可以排在儿子之间的任意一个位置,则总答案$d_u \times (d_u – 1) ! = d_u !$,$u$是root的时候$u$有$n$个位置可以放,答案是$n \times d_u! $。综上所述,总答案为

$$n \prod_{i = 1}^{n} d_i$$

 

 

说点什么

avatar
50
  Subscribe  
提醒