PKUWC2019 凉凉记

请配合 BGM 食用。

菜就是菜,说什么都是借口。

Day 0

前一天先到纪中报道,高铁上打了一会单机膈膜,然后又打了一遍 \(FFT\) 板子,就到了中山。

到了后,发现气温骤然升高,马上 换裤子,舒服了一点。然后就被纪中的车直接接到了纪中。

一开始到宿舍。。发现连被子都没有,只有个木板。。。我们戏称比军训还恐怖的住宿环境。

还好后来屈哥联系了一波让老师送过来了qwq

晚上翻看原来写的博客,然后打了几个字符串的板子,就早早睡觉了。

Day 1

上午是喜闻乐见的开幕式,吹了一波纪中是全国最美的学校。(话说纪中是真的超级大)

然后 PKU 信科的几个教授来发言,实力吹了一波后就结束了。

中午回寝室,由于下午是第一场,还是好好躺着休息了一下。

\(12:30\) 就去考场,结果等到 \(12:50\) 老师才来开机房门放人进去,我就只能打简陋版的配置咯。

开场,先开 \(T1\) 。

给你 \(n\) 个点 \(m\) 条边的有向图(无重边自环),定义一个边集 \(E\) 的贡献为所有可能的拓扑序数量。最后问所有边集的贡献之和。

\(n \le 20, m \le \frac{n(n - 1)}{2}\)

看了一下,woc,又是状压,怎么 PKU 这么喜欢状压啊。

首先写了个 \(O(n!)\) 的暴力,枚举拓扑序排列 \(P\) ,然后看有多少条边满足这个拓扑序,假设有 \(k\) 条,那么贡献其实就是 \(2^k​\) ,交一发,暴力分拿到。

随意想了一想,好像可以优化,一个个填数到拓扑序最前面来,然后考虑这个点向后面的集合连的边条数,就可以做完啦。

复杂度是 \(O(n \times 2^n)​\) ,很好写,交一发直接过了。终于签到啦!

然后看了看 \(T2\) ,woc题面好难读。

给你一颗 \(n\) 个点的树,每个点有个颜色。对于每个 \(k \in [1, m]\) ,回答有多少个大小为 \(k\) 的颜色集合,满足它们的虚树交不为空,注意此处的虚树定义为这种颜色的点对所有路径上点构成的联通块。

\(m \le n \le 10^5\)

想了想,第一档是 \(n \le 100\) 。。。不留暴力分活路,先弃疗,看看 \(T3\) 。

两个人初始分别有 \(n, m\) 张牌,都补到 \(20\) 张牌。问有多少种方案满足两副牌等价。等价定义为对于所有的牌型(斗地主),两个人要么都出得起要么都出不起。

woc 地主斗。。。弃疗弃疗

回头 \(T2\) ,怎么能不算重呢?不太会。。。算了先写个暴力,管他有没有分。直接枚举颜色集合,然后直接 std :: bitset 优化下判断复杂度,但还是很不靠谱,是 \(\displaystyle O(ans \times \frac{n}{\omega})\) 的。。

欸,竟然过了第一个 \(\text{subtask}\) ,数据真水。

然后想了想 \(m=2\) 的 \(\text{41 pts}\) ,YY 了一个虚树加链加链查的做法。

写了写,调了好久,似乎拍上了。一交,直接 \(WA\) ,一连好多发一直 \(WA\) ,心态崩了。

以为是各种数组小了,没开 long long ,一直都过不去。

后来观察一波 gen ,发现我 TM 造的全是链。

看了一波表只有 \(15min​\) 了,瘫倒在座位上不知所措。

尝试调了调,发现大脑一顿浆糊,根本看不懂变量是什么意思。

最后还是没有调出来,顿时心情灰暗。

考场一出来,听到别人都是啥 \(100+100+38\) ,我只有 \(100+12+0\) 的时候,就知道自己凉凉了。

晚上水群,然后谈笑风生,别人都会 \(T2\) ,就我啥都不知道。

Day 2

上午考数学,由于是上机,早点进场随便打了下配置。

随便看了下题,心中一阵吐槽,这不是提答题吗。。

还是简单罗列一下题目吧。。

\(T1:\) 求有多少个有 \(8\) 个点的带标号无根树,满足 \(2\) 个顶点度数为 \(3\) ,\(2\) 个度数为 \(2\) ,其他度数都是 \(1\) 。

$T2: $ 给你一个单位正立方体 \(ABCD-A'B'C'D'\) ,可以沿着边、面对角线走,不能经过重复点,问从 \(A\) 走到 \(C'\) 的最长路是多长。

\(T3:\) 已知四边形 \(ABCD\) 是梯形,\(AB \parallel CD\) ,一个半径为 \(r\) 的圆,圆心在线段 \(AB\) 上,与线段 \(BC, CD, DA\) 相切。如果 \(CD = 50, AB = 200, r = 49\) ,求 \(AD \cdot BC\) 。

\(T4:\) \(\{F_n\}\) 为斐波那契数列,求 \(\prod_{i = 1}^{20192019} F_i\) 中 \(2​\) 的幂次。

\(T5:\) \(15 \times 15\) 的棋盘上要放 \(15\) 个车,任意两个车不在同行或者同列,定义一个方案的权值是 \(\min\{x_i, y_i\}\) ,就是行号和列号的较小值(从 \(1\) 开始编号)问所有放置方案的权值之和。

\(T6:\) 有一个 \(20182018 \times 20182018\) 的网格,行列从 \(1\) 还是编号。对于 \(1 \le i \le 10091009\) 去掉第 \(i\) 列中间 \(2(i - 1)\) 个格子,\(i \ge 10091010\) 的去掉第 \(i\) 列中间 \(2(20182018 - i)\) 个格子。问最多能不重叠地覆盖多少张 \(1 \times 2\) 和 \(2 \times 1\) 的骨牌。

\(T7:\) 对于 \(\{1, 2, 3, \dots, 2019\}\) 的一个非空子集 \(A\) ,定义 \(a(A) = \min_{x \in A} x\) ,第 \(a(A)\) 小的数为 \(b(A)\) ,不存在时 \(b(A) = 0\) ,那么当 \(A\) 在所有 \(1643\) 元子集等概率随机选取时,求 \(b(A)\) 的期望。

\(T8:\) 称正整数 \(k\) 是 好的 ,对于每一个正整数 \(n\) ,如果 \(n\) 可以表示成它的 \(k\) 个约数(允许相同)的平方和,那么 \(n\) 可以表示它的 \(k\) 个约数的和(允许相同),求 好的 正整数个数。

\(T9:\) 圆周上有 \(2019\) 个等分点,每次操作可以选择两个点用线段连接起来,如果每次增加的线段和至多一条已画的线段在内部相交,则最多能画多少条线段。

\(T10:\) 称正整数 \(n\) 是 好的 ,如果:\(A = \{1, 2, \dots, n\}\) 中的每个数可以被染成红蓝两色,满足恰有 \(2019\) 个有序组 \((x, y, z) \in A * A * A\) 使得 \(x, y, z\) 同色且 \(n~|~x+ y + z\) ,求所有好的正整数 \(n\) 的和。

\(T1\) 是个思博 \(\text{prufer}\) 序题,上场随便写了个暴力跑了一下。

\(T2\) 随便模拟了一下,后来发现答案错了。。

\(T3\) 一开始 \(ABCD\) 序号一直弄反了,一直以为没有解。讲题的时候才发现编号有问题。

\(T4\) 用 python 写了个暴力找了找规律,美滋滋~

\(T5\) 简单状压 \(dp\) 直接过

\(T6\) 最后随意观察了一波图形,随便构造了一下。。。都不知道是否正确。。。

\(T7\) 一开始以为 \(kth~\mathrm{min-max}\) 反演,后来发现 \(sb\) 了,直接枚举 \(a(A), b(A)\) 算贡献就行了,用 python 跑的,答案一开始很大(有 \(400\) 位),后来随便一波约分发现答案好像没有那么大?

\(T8\) 看错题了。。以为只有 \(k = 1\) 。。sb了

\(T9\) 随便构造了方案。。。似乎错了

\(T10\) 看不太懂题,一开始以为 \(6 \not | ~2019\) 显然为 \(0\) 。。。后来讲题一波生成函数把我弄懵了。


考完后对于数学还是比较有把握的。。。随便休息了一下开始了下午的机试。

一开始以为今天也有道签到题,就先看了下 \(T1\) 。

问有多少个长度为 \(n\) 的序列 \(\{b_i\}\) 满足 \(l_i \le b_i \le r_i\) 且 \(a_i \text{ and } b_i = a_i\) 。

且 \(\forall i \in [1, n)\) 有 \(b_i < b_{i + 1}​\) 。

\(n \le 100, a_i, l_i, r_i < 2^{60}\)

想了好久如何去限制,发现根本不太会。又只能交个 \(O(na_i)\) 的混混暴力分。

想做下 \(a_i = 0\) 特殊点,发现也没啥好想法,然后看了看 \(T2\) 。

给你一个 \(n\) 点 \(m\) 条边的有向图,定义每个简单环为一个点,如果两个简单环共边那么就意味着这两个点有连边,最后问联通块数量。

\(n\le 10^5, m \le 2 \times 10^5\)

一开始写了个搜环的暴力,一直 \(WA\) ,后来瞎改把一个地方看做无向边才能过第一个 \(\text{subtask}\) 。。

然后想了想,以为是强联通分块数量,花时间回忆了一下,直接过了样例,交一发爆 \(0\) 了。。。

又浪费很多时间写暴力 gen 对拍,然后发现它的定义是简单环,不能经过重复点,\(SCC\) 这个地方会存在问题woc

懵逼了一会想 \(fix\) 一下,想了想点双也许可以做做,但有向边咋搞啊 woc 然后就扔了(flag立下)

然后看了看 \(T3\) woc 计算几何。

给你 \(n\) 个圆心 \((x_i, y_i)\) ,\(m\) 次询问,每次给你圆上一个点 \((x', y')\) 。然后问至多有多少个圆可以被去掉使得圆的并不发生改变。

\(1 \le n,m \le 10^5\)

直观的想法是枚举一个圆是否被删除,然后直接 \(Simpson\) 算面积。

写了一下,交一发发现 \(T\) 了,把精度调到很低才能勉强过第一个 \(\text{subtask}\) 。。

想了一会,会第二档了,要求圆的交点,好像不好写,先弃疗。

回头看 \(T1\) ,看看范围,以为是矩阵,\(YY\) 了一个似乎正确的。花了好久时间写完,拍上。

交上去又 \(WA\) 了。历史总是惊人的相似,我 TM gen 又写垃圾了,权值域基本不重合。

又不会 \(fix\) 了,然后又只能坐着等死了。

出来三道暴力 \(22 + 21 + 11 = 54\) ,听说每题都有人 \(A\) 。我那时真的一脸懵逼,意识到自己彻底爆炸的时候有些不可置信。

果然还是菜了。

面试没有准备了,开了一晚上黑消愁。

Day 3

虽然知道自己进面试的可能性很低,还是去看了看名单。

惊了!竟然有我的名字。。。随便想了一会自我介绍,就去教室旁边等了。

竟然有三轮面试。。。

我是 \(8:30\) 第一个进去的,老师先让我做了一下自我介绍,问了问联赛以及文化成绩。回答了很久以前的一次考的好的成绩2333

最后问了问我对计算机什么感兴趣,我想起了当初在 botzone 上玩的游戏,直接说出了人工智能,看起来老师还算满意?(或许第一个有 \(\text{buff}\) 吧)

第二个是 \(9:22\) 进去的,老师先问我这次PKUWC考的咋样。。我实话实说,考的不好。。结果老师就之后基本不问我个人了,跟我讨论了一下湖南的情况以及北大的情况(懵),还祝我稳进省队???然后一脸懵逼后我就出来的。

最后一个是 \(10:24\) ,进去老师先问我你最自豪的一件事是啥。我懵了很久,回答道“参加了信息学竞赛“。然后又问我最喜欢的数据结构和算法。数据结构嘛。。随意答道 \(lct\) 。算法?当然是网络流啦。然后又问我为啥喜欢网络流?emmmm当然是因为它很 玄学 神奇啊,就是看起来根本做不了的题,用网络流可以神奇的解决。然后瞎比比一会就结束啦。

下午参加闭幕式,又随意bb了一会后就开始发约咯。今年好像有点不一样,没有具体内容只有等地。共有四等约,发了几十个人。。。最后果然没我 TAT

Day ∞

总的来说,这次考崩是意料之中的。

高二了,时间不多了,或许有时也会害怕自己没学上。

但我相信这不是我的水平,这不是我应有的实力。

题还是做少了,思维还是太慢。

唉,希望能尽快调整过来吧。

投之亡地而后存,陷之死地然后生。

上一篇:UE4材质特别属生记录


下一篇:Spring JdbcTemplate 的使用与学习(转)