PKUWC 2019

二零一九一无所有

Posted by Ghastlcon on January 24, 2019
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 PKUWC 2019

$\text{Day 0}$

早上 $7$ 点起床非常舒服。

还记得我吃的是 $3$ 角蛋糕 $\times 2$ 。

到了机房开始颓,莫名其妙地发,天空璋 $\text{Extra Stage Clear}$ 。

捡完宿舍的东西之后直接就溜了,感受纪中那不知道多少倍于石中的面积。

宿舍居然有的是 $4$ 人有的是 $3$ 人。$3$ 人宿舍居然还有 $4$ 套被子。


试机题是 $\text{PKUSC}$ 的。

给定 $n$ 个整数 $v_0,\,v_1,\,\cdots v_{n-1}$,求每个排列的最大前缀和的和。$1\leq n\leq 20,\,0\leq \sum |v|\leq 10^9$

不会做,写了 $3^n$ 就溜了。听 $\text{lovelyboy}$ 说似乎可以 $\text{FWT}$ 加速?


感觉今年应该不能看榜。

晚上不知道为什么又发了,风神录 $\text{Lunatic Mode Clear}$?

我要身败名裂啦。(不对我哪里有名了)

$\text{Day 1}$

仍然是 $7$ 点起床舒服。

开营仪式全程吹逼,感觉比去年详细了很多。

讲话人 $1$:(由于设备原因录音只有部分)

我们北大的东门就是向东南门就是向南不像隔壁东南不分!

讲话人 $2$:

隔壁清华哪有这里好……

合影留念非常的智障,总感觉合影的那个台子随时要倒下来。

中午背板 $\text{FWT}$ 。好虚啊要死了。


进场开题。瞬间看到 $\text{P3}$ 地主斗,直接丢掉 $\text{P3}$。这还真的不能看榜。

$\text{P1}$ 拓扑序计数

给 $n$ 个点 $m$ 条边的有向简单图 $G=(V,\,E)$,求 $\sum_{S\subseteq E}\mathrm F(S)$,其中 $\mathrm F(S)$ 定义为只使用 $S$ 中的边,这 $n$ 个点的合法拓扑序方案数。$1\leq n\leq 20,\,0\leq m\leq n\cdot (n-1)$ 。

打了个 $\mathrm O(2^{m+n})$ 的做法确保看对题意,$22 \%$ 到手。

开始画式子。想到昨天的试机题,需要利用新加入的这个数并不需要考虑前面数的顺序,然后这里似乎也可以按照点动态规划。中途用了很久想怎么转移。打完之后交上去只有 $35\%$ 。

我常数怎么这么大啊。把 $2^k$ 逆元预处理了交上去,$100\%$!

$\text{P2}$ 你和虚树的故事

给 $n$ 个点的无根树 $T$,点有颜色。求 $\mathrm F(1),\,\mathrm F(2),\,\cdots \mathrm F(m)$,其中 $\mathrm F(i)$ 定义为在 $n$ 种颜色里选取 $i$ 种,使得这 $i$ 种颜色构成的虚树交集不为空的方案数。注意虚树的虚边相交也算有交集。$1\leq m\leq n\leq 10^5$ 。

觉得不太可做,求 $\mathrm F$ 的很多值绝对是 $\text{NTT}$ 没跑,但是想不出怎么做。容斥的复杂度显然不对。

然后发现 $42\%$ 可以嵌套数据结构直接做,$\mathrm O(n\log^2 n)$ 。结果虚树板子背的不熟(考前才刚看过……)搞了很久,数据结构部分又搞了很久最终还是没写出来。

$\text{P3}$ 地主斗

$\text A$ 和 $\text B$ 手上分别有 $n$ 张牌和 $m$ 张牌,记为 $X$ 和 $Y$,这 $2$ 人的牌是分别从 $2$ 份正常的牌里取出来的。求有多少对集合 $(P,\,Q)$,满足 $X\subseteq P,\,Y\subseteq Q,\,|P|=|Q|=20$,且 $P$ 和 $Q$ 本质相同。本质相同的意思是对于任意的合法出牌方式 $R$,要么都可以从 $P,\,Q$ 中取出子集(即出牌方式)打在 $R$ 后,要么都不可以。出牌方法类似于传统斗地主,$0\leq n,\,m\leq 20$ 。

我去你妈的九条可怜。


$100+0+0=100$ 真心大众分舒服。

我是智障

晚上神灵庙 $\text{Hard Mode 9961}$ 真心舒服。不会 $\text C$ 啊。

$\text{Day 2}$

起床时间照常,听到了跟噪音差不多的起床铃。

看数学题,今年直接变成 $10$ 个提答?不出所料 $\text{OI}$ 赛制,密码条上还特别印着加粗的“可以使用计算机中的 $\text{Python}$ 和 $\text{Java}$”。

$\text{P1},\,9\%$

求共有 $8$ 个点的,$2$ 个点度数为 $3$,$2$ 个点度数为 $2$,$4$ 个点度数为 $1$ 的树数。结点带标号。

看完 $\text{P1}$ 就意识到了这场是搜索大战。

考虑到 $8$ 个点最多只可能有 $\frac{8\cdot (8-1)}{2}=28$ 条边,直接枚举在其中选 $7$ 条即可。

$\text{P2},\,9\%$

在单位立方体上,从 $(0,\,0,\,0)$ 走到 $(1,\,1,\,1)$,可以沿着边或者面的对角线走,路线不能自交(在点相交也算),求最长距离。若答案为 $p+\sqrt q$,输出 $p+q$ 。

手玩玩出了 $4$ 个 $5+2\sqrt 2$ 的走法,深信这就是答案(听说有 $5+4\sqrt 2$?)

$\text{P3},\,9\%$

有梯形 $ABCD$,其中 $AB\parallel CD$,有半径为 $49$ 的圆 $O$ 圆心在 $AB$ 上,与 $CD,\,AD,\,BC$ 均相切,已知 $AB=200,\,CD=50$,求 $AD\cdot BC$ 。

知道了 $AB$ 和 $CD$ 间距离为 $49$,所以可以得到 $\sqrt{AD^2-49^2}+CD+\sqrt{BC^2-49^2}=AD$,暴力枚举 $AD$ 和 $BC$ 。

$\text{P4},\,10\%$

定义 $\mathrm F(n)$ 为 $\text{Fibonacci}$ 数列的第 $n$ 项($\mathrm F(1)=\mathrm F(2)=1$),求 $\prod_{i=1}^{20192019}\mathrm F(i)$ 的以 $2$ 为底的幂次。$x$ 以 $k$ 为底时,$a$ 是 $x$ 的幂次当且仅当 $x=k^a\cdot (k^b+1)$,其中 $a,\,b$ 均为非负整数。易证这样的 $a$ 有且只有 $1$ 个。

这个题就很有意思了。设 $\prod_{i=1}^n\mathrm F(i)$ 的幂次为 $\mathrm G(n)$,然后 $\text{Python}$ 高精暴力跑出 $\mathrm G$ 的前 $2000$ 项(用时约 $15\texttt{min}$),再对 $\mathrm G(n)$ 差分即可看出大体是以 $16$ 个作为循环节,但是每个循环节的第 $16$ 个又会变化,形式参照格雷码。得到规律之后直接递推。

$\text{P5},\,10\%$

在 $15\cdot 15$ 的棋盘上放置 $15$ 个互不攻击的车(攻击的定义是在同行或同列),放置方案 $P$ 的权值定义为 $\forall i\in[1,\,15],\,\min(x_i\cdot y_i)$,其中 $(x_i,\,y_i)$ 为第 $i$ 个车的坐标(均从 $1$ 开始)。求随机合法放置方案的权值期望。若期望为 $\frac{p}{q},\,p\perp q$,输出 $p+q$ 。

搜索或者状态压缩动态规划均可,反正我是没做。

$\text{P6},\,10\%$

在 $20182018\cdot 20182018$ 的棋盘上中间挖洞。具体来说,对于第 $i$ 列(从 $1$ 开始),若 $i\leq 10091009$,则从中间开始往外挖 $2\cdot (i-1)$ 个格子,否则从中间开始往外挖 $2\cdot (20182018-i)$ 个格子。挖完之后求在上面最多能放多少个 $1\cdot 2$ 的骨牌。骨牌之间不能重叠,不能放到被挖的格子上。

手玩发现对于 $n\cdot n$ 的棋盘($n$ 是偶数),若 $n\leq 8$ 都可以铺满,否则不能铺的格子为 $4\cdot \lfloor\frac{n-6}{4}\rfloor$ 。根据规律直接计算即可,注意最后不要忘记除以 $2$ 。(其实输出答案后缀应该要带个 $\texttt{LL}$ 才能防止爆 $\texttt{int}$?)

$\text{P7},\,10\%$

定义 $\mathrm F(S,\,k)$ 为集合中第 $k$ 小的元素,如果 $|S|<k$ 则为 $0$ 。现有集合 $S=[1,\,2019]$,求 $\mathrm F(B,\,\mathrm F(B,\,1))$ 的期望,其中 $B\subseteq S,\,|B|=1643$ 。若期望为 $\frac{p}{q},\,p\perp q$,输出 $p+q$ 。

考虑枚举 $\mathrm F(B,\,1)$,再枚举 $\mathrm F(B,\,\mathrm F(B,\,1))$,直接组合数相乘计算方案。总方案数显然为 $\mathrm C_{2019}^{1643}$ 。注意中间结果很大,需使用 $\text{Python}$ 高精。

$\text{P8},\,11\%$:

定义好数为正整数 $k$,满足对于所有正整数 $n$ 可以表示成 $n$ 的 $k$ 个约数平方之和,那么 $n$ 必然可以表示成 $n$ 的 $k$ 个约数之和。求所有好数之和,若和为无穷大输出 $-1$ 。

果断输出 $-1$ 。

$\text{P9},\,11\%$

圆周上有 $2019$ 个等分点,每次可以选择 $2$ 个不同的点并在它们之间连 $1$ 条线段,满足这条线段和最多 $1$ 条已经连的线段相交,求最多可连多少条线段。

果断输出 $2333$ 。

$\text{P10},\,11\%$

定义好数为正整数 $k$,满足对于集合 $S=[1,\,k]$,可以对集合内数黑白染色,并且恰有 $2019$ 种方法在其中选出 $3$ 个可重数 $x,\,y,\,z$,满足 $x,\,y,\,z$ 颜色相同,并且 $n\;|\;x+y+z$ 。求所有好数之和。

开始时我还以为 $2019$ 不是 $3$ 的倍数搞得我怎么想都认为答案应该是 $0$ ……

然而最后还是只输出了 $0$ 。


进场开题。看来今年真的又是 $6$ 个数数题。直接丢掉计算几何。

$\text{P1}$ 递增序列

给 $3\cdot n$ 个非负整数 $a_0,\,a_1,\,\cdots ,\,a_{n-1},\;l_0,\,l_1,\,\cdots ,\,l_{n-1},\;r_0,\,r_1,\,\cdots ,\,r_{n-1}$,求有多少个长度为 $n$ 的单调递增序列 $b$ 满足 $a_i\operatorname{and}b_i=a_i,\,l_i\leq b_i\leq r_i$ 。$1\leq n\leq 100,\,0\leq \max(a),\,\max(l),\,\max(r)<2^{60}$ 。

我怎么觉得这个题应该很简单的样子啊。

我们只需要记 $f(i,\,j)$ 为使用 $\leq i$ 的数,填前 $j$ 个格子的方案数。转移只需要考虑 $i$ 是否满足格子 $j$ 的要求。

然后会发现这个转移虽然不常系数,但是可以直接单点改转移矩阵变成常系数。这样就得到了优秀的 $\mathrm O(n^4\log v)$ 做法。

你只需要学会卡常就可以得到 $100\%$ 。然而我是不会卡常的。

$\text{P2}$ 环图

给 $n$ 个点 $m$ 条边的有向图,将图内每个简单环都看成 $1$ 个点,求这些简单环代表的点构成的连通块数量。简单环代表的点之间有边(无向)当且仅当有至少 $1$ 条边共用。$1\leq n\leq 10^5,\,1\leq m\leq 2\cdot 10^5$ 。

我选择了 $21\%$ 暴力。然后强上 $46\%$ 发现死活 $\text{TLE}$ 根本跑不过。

$\text{P3}$ 防御塔

给平面直角坐标系内的 $n$ 个点 $(x_i,\,y_i)$,有 $m$ 个询问,每次询问给出点 $(p,\,q)$,对这 $n$ 个点 $(x_i,\,y_i)$ 都以自身为圆心,$\sqrt{(x_i-p)^2+(y_i-q)^2}$ 为半径作圆,求有多少个圆被其它圆的并集覆盖。$1\leq n,\,m\leq 10^5$,保证所有 $x$ 坐标和 $y$ 坐标均互不相同。

我去你妈的九条可怜。


$22+21+0=43$ 还是真心大众分舒服。

晚上无事可做,没有玩的乐趣。

$\text{Day 3}$

真的没想到这样子大众分 $\times 2$ 还能进面试,经过计算是 $\text{Rank 89}$ 。可能数学翻盘了?

面试官 $1$

$\text Q$:坐下 $\times 5$ 。
$\text A$:……
$\text Q$:佛山市……石门中学对吧。
$\text A$:是啊。
$\text Q$:那南海那边离这里还挺近的啊。你们那边有什么高考比较优秀的学校啊?
$\text A$:(问高考???)石门中学,南海……中学?
$\text Q$:你们那边是不是还有个佛山一中……
$\text A$:是啊。
$\text Q$:看你 $\text{NOIp}$ 考的不错,你在广东高一排名大概多少?
$\text A$:(我怎么知道???)大概 $\text{Rank 5}$ 的样子?
$\text Q$:那还挺不错的啊,你们学校的未来就靠你了。这轮面试主要是看看你的交流能力是否正常……
$\text A$:(你还把你的目的说出来了???)谢谢。

面试官 $2$(手持 $\text{Surface Pro}$)

$\text Q$:请坐。
$\text A$:你好。
$\text Q$:佛山市石门中学是吧。
$\text A$:是。
$\text Q$:你最自豪的一件事是什么?
$\text A$:(???)只限在 $\text{OI}$ 方面的吗?
$\text Q$:可以说生活方面的。
$\text A$:等我思考一下。(我吹什么比较好啊)我在做某道题的时候自己搞出了一种线性时间复杂度内求整式除法的方法?
$\text Q$:描述一下。
$\text A$:(开始吹逼)
$\text Q$:我理解了。你是怎么接触到 $\text{OI}$ 的?
$\text A$:(???)(从小学吹到初中)
$\text Q$:时间可能不够了,不好意思我们只能够聊到这里了,可以去叫下一个人了。
$\text A$:(我居然吹了这么久?)谢谢。

面试官 $3$

$\text Q$:请坐。
$\text A$:你好。
$\text Q$:先自我介绍。
$\text A$:(我准备的东西终于能用上了?)来自佛山市南海区石门中学。跟大多数人相同,接触 $\text{OI}$ 是在初中的时候。不过在小学的时候我就喜欢在机器上搞点乱七八糟的东西了,当然现在也相同,有时候还是会写些乱七八糟的小玩意。接触 $\text{OI}$ 的几年以来,深深地感到了智商不够用。同样的跟大多数人相同,没有什么非常特别的兴趣爱好。选择 $\text{PKU}$ 的原因是个人认为这里的学术氛围比较好。
$\text Q$:你机试怎么样?
$\text A$:(你不知道的吗还问得这么直接?)$100+43$,有几个题没写完但是到底还是自己菜。
$\text Q$:数学怎么样?
$\text A$:(???)我都不知道分数……期望大概做对 $6$ 题左右吧。
$\text Q$:文化课成绩如何?
$\text A$:(问什么不好问这个???)级排 $100$ 多,共 $1000$ 人。
$\text Q$:有没有什么非常特别的计算机无关兴趣爱好?
$\text A$:(我有时间搞这个我为什么不去搞 $\text{OI}$?)基本没有,大部分的兴趣都是计算机相关,喜欢搞乱七八糟的小东西。
$\text Q$:$\text{NOIp}$ 分数如何?能否参加 $\text{NOIWC}$?
$\text A$:(总算问了个正常点的)没有得到应有的分数,只有 $509$,但是还是有 $\text{WC}$ 参赛资格。
$\text Q$:好的可以了,祝你在接下来的比赛中顺利。
$\text A$:谢谢。

非常的愉快。


闭营仪式的时候宋新波吹水。

敦老师口胡解法。

$\text{PKU}$ 某领导说“由于教育局的规定,今年我们不发正常的约,而是用奖代替。各位放心这个奖也肯定是会生效的,虽然具体会变成怎样的优惠我们现在不敢肯定,但是隔壁清华的优惠肯定跟我们相同”。

发约然后发现并没有自己。大概只发了 $70$ 人的样子?

去年还有安慰约的来着今年就什么都没有了?教育局的规定真的是非常有趣,听说“减少降分名额”?

$\text{THU}$ 还有 $\text{THUSC}$ 参赛资格的安慰约,现在全世界就我什么都没有了。

$\text{Day 4}$

捡东西然后去 $\text{NOIWC}$ 冬眠。

没什么的了就这样吧,来年再战。

你们觉得这是早上还是下午