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 代码

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

签约

拿了一本赶紧跑