2019 CCPC Final

Replay

Xiejiadong:

• 周五太浪，周六讲座，赛前无练习，然后就丢脸了
• 周六热身赛就丢了个大脸
• 正赛一个半小时就没题做了，菜的真实
• 是不是周五中了个旷世的鼠标垫，用光了比赛需要的 RP 。

Kilo_5723:

• 没得彻底。
• 发现一个妙的不行的结论，以为 E 做出来了，原来又双叒叕只解决了第一部分。

Weaver_zhu:

Problem A

Solved by Xiejiadong. 00:20:45 (+1)

自定义排序签到。

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved. (-13)

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Solved by Kilo_5723. 01:37:08 (+)

题意：有 $n$ 个颜色的方块，每两个颜色（可以相同）可以组成一个大块，总共有 $\frac{n \cdot (n+1)}{2}$ 种不同的大块，现在每种大块取一个，要求构造一个三维放置方案，使得每个颜色的小块互相连通。大块只能放置在整点上。

题解：构造如下：

第一层：

1 1 1 1 1 1
  2 2 2 2 2
    3 3 3 3
      4 4 4
        5 5
          6

第二层：

1 2 3 4 5 6
  2 3 4 5 6
    3 4 5 6
      4 5 6
        5 6
          6

其中第一层和第二层对应位置上的方块构成一个大块。

Problem J

Unsolved. (-2)

Problem K

Solved by Xiejiadong. 00:55:06 (+)

题意：求每一个子树里面所有的节点编号构成了多少个联通块。

题解：每一个子树用 set 维护节点编号。

暴力插入编号以后判断左右联通性，求出联通块数量。

直接启发式合并，就过去了。

Problem L

Solved by Kilo_5723. 00:36:34 (+1)

题意：从矩阵的任意点出发，每次前进只能向右拐至多一次，问有多少种不同的路线能经过每个格子恰好一次。

题解：由于路线的性质，要么从外面一圈一圈绕到里面，要么从里面一圈一圈绕到外面，要么由两个绕成圈的路线在边界上组合。

特判了长条的情况后，发现前两种情况可以合并到第三种，答案是 $2n+2m-4$。