Day1

扯淡

来自全国各地的大佬齐聚长郡,作为蒟蒻我鏼鏼发抖
首先播了长郡中学 2014 年制作的宣传片 (你没有看错,就是 2014 年的宣传片)
然后各种老师专家做开幕式发言,最后北大老师来扯计算机的发展史,我就只能在下面各种%%%
特别强调北大的男女比例为 1:1???
世界上第一个程序员是女的???

数学考试

考试在计算机上进行
我深知作为一个数学渣渣不使用电脑上的计算器是会爆零的,于是就在大佬们疯狂打草稿的时候我就直接在电脑上输入式子,直接计算
旁边的大佬被吓得直接向老师反映
用计算器算完计算题之后考试就差不多结束了
什么,还有几何题,你知道什么叫做选择题 $\frac{1}{5}$的概率大题目直接舍弃吗
所以我解答题的答题纸基本上是空的

上机考试

IOI 赛制好评

problem 1

给出一棵有 $N$ 个节点树,叶子节点上有一个权值 $w$ ,非叶子节点上有一个概率 $p$ ,表示这个节点有 $p$ 的概率取得两颗子树的最大值, $1-p$ 的概率取得子树最小值
设根节点可以搞到的权值数量为 $m$ ,权值从小到大 $v$ ,概率为 $d$ ,求 $$\sum\limits_{i=1}^mi\times v_i\times d_i^2$$
$1\leq N\leq 100000, p\in(0,1)$,$w$互不相同

显然如果 $v_i$ 是有序的,那么 $i\times v_i$ 也不会影响顺序,所以可以直接把 $v_i\times i$ 合并,然后再把成功的概率直接搞成 $p_i^2$ 失败的概率直接搞成 $1-p_i^2$ ,好像就可以 $O(N)$ 了,然后样例都过不了
此时已经有大部分的人把这个题目 A 了,然后推了一下公式发现好像是一个裸的线段树合并,打完过了样例直接交什么是罚时,能吃吗,发现 RE0,发现一个 BUG,改了再交 RE0,再改交,RE0…5 次 RE0 之后终于发现数组开小了,线段树写挂了,交 WA10,好像有个地方忘记取模了,再交,WA10…4 次之后终于把所有没有取模的地方都取模了,AC100
看榜单,100(9),在所有 100 分的最下面,诶,不是不罚时吗????

problem 2

有 $2N$ 张牌, $N$ 张强化牌, $N$ 张攻击牌,使用一张强化牌 $x$ 之后,所有的攻击牌能造成的伤害会乘以 $x$,九条可怜等概率的随机从这 $2N$ 张牌中选出 $M$ 张牌,然后打出其中的 $K$ 张牌,九条可怜会从所可能的组合中选出能够造成伤害最大的组合并打出,设九条可怜能够造成的伤害的期望为 $a$ ,输出 $a\times \binom{2N}{M}$
$1\leq K\leq M\leq 2N\leq 3000$,强化牌的 $x$ 大于 1

其实就是要输出 $2N$ 张牌中选出 $M$ 张牌能造成的伤害的和
显然如果强化牌足够的话那么就是打出 $K-1$ 张强化牌和 1 张攻击牌,否则就打出所有强化牌和一部分攻击牌
所以强化牌 $A$ 和攻击牌 $B$ 可以分开考虑,现将他们按照从大到小排序
设 $f_{i, j}$ 表示在前 $i$ 张强化牌中选出 $j$ 张强化牌能够翻的倍数,那么
$$f_{i, j}=f_{i-1, j}+[j<k]f_{i-1, j-1}\times A_j+[j\geq k]f_{i-1,j-1}$$
攻击牌也是类似的, $g_{i, j}$ 表示在前 $i$ 张攻击牌中选出 $j$ 张牌能够造成的伤害
$$g_{i, j}=g_{i-1, j}+g_{i-1, j-1}+B_j\times \binom{i-1}{j-1}$$
最后考虑到攻击牌可能不能打完,所以设 $h_i$ 表示打出 $i$ 张攻击牌能造成的伤害
$$h_i = \sum_{j=1}^N(g_{j-1, i-1}+B_j\times \binom{i-1}{j-1})\times \binom{N-j}{M-K}$$
所以答案就是
$$\sum_{i=0}^Nf_{N, i}\times h_{K-i}$$
再加上强化牌超过 $K$张的情况
时间复杂度:$O(N^2)$

problem 3

写完前两题还有 3h,但是发现许多 1h200 分的人成绩都没有动了
然后以后再也不想打斗地主了

总分 200,分数 rank1,算罚时 rank10

day2

上机测试

problem 1

给出一张 $N$ 个点的图,求随机选点得到最大独立集的期望 ???
不会啊,但是好像没 1s 就有一个人通过,那写个暴力爽一爽把
最大独立集的个数乘以 $2^NN$
AC100
人一定要有梦想
人一定要有梦想
人一定要有梦想
人一定要有梦想
人一定要有梦想
人一定要有梦想
人一定要有梦想
人一定要有梦想
人一定要有梦想
人一定要有梦想

problem 3

给出一颗 $N$ 个节点的树,以及固定起点 $s$, $M$ 个询问,每次给出集合 $S$ ,求从 $s$ 出发每次所以找条边走,经过 $S$ 内所有点至少一次的步数期望
$1\leq N\leq 18, 1\leq M\leq 5000$

这不是个裸的高斯消元么
写了一个 $O(2^NN^3 + M)$ 的算法,TLE70,需要 2s
树上的高斯消元是 $O(N)$的啊,白白被卡 30

problem 2

$N$个人,每个人都有一个仇恨度 $w$,每个人都有亡语: 随机击杀另一个人,这里的随机不是等概率的随机,而是设剩下 $j$ 个人 $p_1, p_2..p_j$,那么第 $p_x$ 个人被杀的概率为 $$\frac{w_{p_x}}{\sum_{i=1}^jw_{p_i}}$$
第一个死的人也是按照这个概率
求 1 号人最后一个死的概率

不会啊,RE30

分数 200, rank5

面试

1

Q : 你数学怎么样
A : 130 左右啊
Q : 你数学怎么这么菜啊
A : ..
Q : 说说你数学怎么搞得
A : 我不喜欢计算,特别是圆锥曲线,暴力不优雅,几何法才优雅
Q : ..
Q : (顺手掏出一张纸) 你看一份代码如果要计算 $N^3$ 次,另一份代码需要计算 $N+100$ 次,那么当 $N=3$ 的时候,哪个跑得快
A : 都差不多 $N^3$ 快
Q : 所以啊,暴力不一定不优雅
Q : (看了看表) 最后问你一个问题 : 对数与几何有什么关系
A : 有个毛线关系啊 我不会
Q : 时间到了,下一个

2

Q : 以后你最想要做什么
A : 在美国国家安全局的网站上写上苟利国家生死以 xxx 到此一游
Q : 好,你很有想法,那么你说一下你的竞赛生活吧
A : 我十年竞赛一场空
Q : 那么我想问的问完了,接下来你来问我问题吧
A : 你看我屌吗

3

基本和 2 是一样的

讲题

斗地主还是算了把
第三题 我用 word 直播写 tex 代码

长郡中学里头没有什么好玩的地方

签约

拿了一本赶紧跑

分类: 文章

5 条评论

菜鸡yww · 2018年3月3日 6:44 下午

能不能讲一下 D2T2 怎么做

菜鸡yww · 2018年3月2日 9:29 下午

您去 PKU 了;我回家种田了:我们都有光明的前途。

    Cai · 2018年3月2日 9:38 下午

    您一个 THU 无条件的还在这里装

litble · 2018年2月2日 8:52 下午

STO Cai Orz

konnyakuxzy · 2018年2月2日 8:49 下午

Orz
您签约了
我要退役了
我爱文化课
再见,OI

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注