CTSC/APIO2016 游记/滚粗记/题解

2016.05.10 08:05 Tue| 167 visits gossip| Text

游记

4/30 CTSC day-1

在火车上躺了一晚上。半夜三更上面的两个家伙一个在推沙耶之歌,另一个在打神tm二人单机麻将,打完麻将一言不合就开始推妹子——简直没眼看了。

5/1 CTSC day±0

一大早下了火车转地铁转公交从起点坐到终点又走了十多分钟终于到达了昆(hen)泰(tai)酒店★★★★★。妈呀五星级吓傻我,沟里来的孩子真是第一回住啊。然后某熊孩子进去就把人家的浴帘拽掉了,这导致之后的一周内浴帘有几度偏角始终拉不严实……

之后第一次洗澡。

之后到了愉悦的吃午餐的中午,长途跋涉半小时到达学校。感谢北京八十中给了我们这次宝贵的锻炼机会。吃完看时间表,试机的时间段不能再尴尬。拖着沉重的身躯怀着必死的决心滚回酒店,不愧是帝都温度真高啊,感觉自己全身都在蒸发,我看见了…天国!

之后第二次洗澡。

下午颓了半天三国杀,收拾收拾去试机,敲了一个萨菲克斯·阿瑞,感觉自己要完[flag],感受了一下键盘的不好使,之后去办公楼转了一圈。办公楼的某神奇的房间内显示器在桌子下面,那种能让脖子疼一年的位置。看了看试机题,卧槽向量内积,随便搜了搜题解。之后测试鼠标(打天凤)发现没有鼠标垫就是作死。辣鸡linux只能用web版,打了半局单机测试版就狗带啦!

之后回去打三国杀刷浴缸第三次洗澡。北京真有趣。

5/2 CTSC day1

考试。昨天走路太多大腿疼。

上来看题,第一题的 x 和 y 有什么卵用,增加读入难度?敲一个暴力,diff 一下结果吓傻。机智的我想到了 \r,在心里将出题人骂了十遍。

然后敲第二题的暴力,调大样例调半个小时,然后弃疗敲第一题的可持久化线段树。过了一会来人说样例输出 tm 竟然是个错的!连样例都错了这敢信!在心里将出题人骂了二十遍。

第三题提交答案写了一个背包玩玩第二第三个测试点。第一个点大家都说傻然而我竟然没看出来。第四第五个点大家都说傻,可是我也不会。【后来吃饭的时候发现自己sb】后面写矩阵快速幂跑了半天结果过不了样例,只有第六个点得了分。其余输出样例和 0 有一大堆分这也是够呛。

出来之后发现提答标准分 50,还有个不食嗟来之食的 QT。感觉自己药丸。

下午在机房门口百无聊赖地等成绩等成绩,结果发成绩延时了一个小时。25+5+30分滚粗啦,我得到的乱七八糟提答分数竟然加起来是个整十数,好神奇啊。

后来发现有的人第一题不开 long long 爆零,有的人不知为何烤炸。【心累】

晚上会酒店去地下参观了一圈游泳池。

5/3 CTSC day1.5

上午开开心心地打车去家乐福买泳裤买泳镜买泳帽。-¥150。中午在一层吃肉夹馍,芒果汁地狱般难喝。QT一个女孩子选泳衣还真是辛苦啊。之后回酒店开开心心去游泳(泡澡),QT 被发了一个蓝色的衣柜牌还真是有趣呢。泡到一半被宋爷揪出去听《王选的世界》报告会。LLX 的膝盖因摩擦受了一个差点截肢的伤,这也成为了一周间我唯一的一次游泳。

玄儿的小diao好可爱啊。不愧是我看上的男人

一周后,在整个报告会中,我只记住了【日本人下围棋,美国人打桥牌,中国人打麻将】一句很没有道理的话。

5/4 CTSC day2

听说去年 APIO d2 难得要死要死。

上来看题,第一题好厉害啊,给了好厉害的附加文件,然而随便贪一贪心竟然就能有 3 分,然而最后几个点绝对跑不过去。在五个小时中运用了多种数据结构优化然后狗带。

第二题感觉第二种数据可做?然而并不会。

接下来玩第三题,手玩配合网络流得了好多分,感觉自己稳了。

然而出来交流的时候发现是个人提答就比我分多。

发成绩,第一题竟然还能混到一个 10 分点。后来发现一个全排列就是 30 分了……于是 25+5+40 滚粗。听说第三题暴搜还有不少分,可是我拒绝不优雅的拿分方式。

听讲题,第一题就不知不觉讲完了,我还一脸懵逼。

5/5 APIO day0

去密室逃脱打币子吃必胜客,感觉自己已变穷。

5/6 APIO day1

上午听讲课,听某女老师说【别来抢饭吃,中午完下课半小时。下午开家长会,你们滚粗】。

某清华前辈将提答,介绍了一堆算法然而无卵用,最后来了一句“几年前的提答都是这套路,然而现在的提答都奇怪起来了”。HP-1。

下午听了一节历史课。晚上订外卖,土豆+土豆+土豆+玉米的排骨饭真 tm 难吃。

三国杀中被闪电劈得好惨。

5/7 APIO day2

颓了大半个小时 t1,完全没有思路,暴力都不会写。

之后颓 t2,发现只会写暴力,交了一个中位数和一个树形 dp,感觉药丸。

听说去年金牌线 200+,然而我今年只会 26 怎么办……

之后接着颓 t1,与卷子相顾无言。难道是求出每一段的表达式然后积分?妈呀这想法太可怕!咦?好像组合数能搞?瞎写一发三次方 dp 交上去竟然 AC 了。

看一眼 t3,简单到要命的 30 分,交上去还 WA 了一发,原因是 1e18+1=1e18。

然后再随随便便写一个 nlogn 的二分好了,46.81分 get。眼看着左面的小哥不停交第三题,分数在 41 到 46.16 之间摇摆摇摆。

接着颓 t2,心里想着只要 t2 再拿点分就可以上 200 了,事实证明我后来两个小时的一切努力都是徒劳的。好不容易写了一个差分网络流,还没看到分考试就结束了。后来的事实证明,一分也未曾多得。

jkxing的第一题也卡常失败,Au 强行退化成了 Ag。

听说有人最后四分钟调出来代码开开心心交一发交错程序狗带,简直是一桩天大惨案。

5/8 APIO day3

上午的物理引擎好无聊啊。听说我混了一块金牌,难以置信。晚上看一群人排队饭票换饮料。闭幕式上天凤打出了一个三倍满东一飞人真是爽。

然后面基撸串子,坐对面的小哥全程「ギリギリ愛ギリギリ舞」,后来开始直播开车放重口味捆绑 GV,简直要死要死。

5/9 归家

看了一天无头。快到长春的时候四麻打出了一个立直一发自摸混全两杯口。很厉害,很厉害!

感想:打麻将/三国杀真开心啊!

题解

APIO Boats

很显然,给出的区间需要离散化。在此基础上直接 DP 难以处理几个学校派出划艇数量在同一个区间内的情况,考虑另一种方式。

首先,若学校派出的划艇可选数量都是相同的,那么派出船队的方案数可以简单地利用组合数计算。对于离散化出来的区间,分别预处理出有 i 所学校派船的方案数,时间复杂度 O(N^3)。

下面就可以 DP 啦!枚举派出划艇队的学校,枚举这所学校派出划艇数量所在区间,枚举第一所派出划艇数量在此区间中的学校,更新答案。当枚举结束一所学校之后,扫一遍更新二维 DP 数组的前缀和。时间复杂度还是 O(N^3)。

复杂度好高啊,然而不知道为什么跑得飞快。

APIO Fireworks

中位数 + 树形DP = 26分。

观察性质,对于一棵树,修改的花费关于根节点到叶子结点的距离是一个下凸函数,其中函数的最小值就是我们想要的答案。

假设凸包的最小值在 L~R 处取到。考虑在树的根上方又长出了一条边,那么我们应该尽可能地调整这条边来更新答案,即当根到叶子的距离较大时,函数值至多仅有斜率依次为 -1、0、1 的三段。至于当一些挂在一条边下的子树合并时,直接将函数相加即可。

观察上述函数,发现性质:函数图像的斜率单调不减且均为整数,且拐点的横坐标均为整数。这就意味着,只需要得到所有拐点的横坐标和函数在 y 轴上的截距,就可以得到整个函数。每一次更新函数时,我们需要弹出一些横坐标较大的拐点,新增两个拐点,并且还需要支持拐点的合并。这可以用可并堆来解决,时间复杂度 O((N+M)*log(N+M))。

废话好多,代码相当短。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;

#define N 300005

int n, m, p[N], s[N];
long long c[N], b[N];
__gnu_pbds::priority_queue<long long> q[N];

int main()
{
    cin >> n >> m;
    for (int i = 2; i <= n + m; ++i)
        cin >> p[i] >> c[i], ++s[p[i]];
    for (int i = n + m; i >= 2; --i)
    {
        long long l = 0, r = 0;
        if (s[i])
        {
            for (int j = 1; j < s[i]; ++j) q[i].pop();
            r = q[i].top(), q[i].pop();
            l = q[i].top(), q[i].pop();
        }
        q[i].push(l + c[i]), q[i].push(r + c[i]);
        q[p[i]].join(q[i]), b[p[i]] += b[i] + c[i];
    }
    for (int i = 1; i <= s[1]; ++i) q[1].pop();
    while (!q[1].empty()) b[1] -= q[1].top(), q[1].pop();
    cout << b[1] << endl;
    return 0;
}

APIO Gap

交互题。前 30 分的子课题一十分简单。

对于第二种类型的数据,首先用 N+1 的代价找到最小值和最大值。很显然,答案不小于这两个值的差除以 N-1。这样,将区间分段并询问每一段中的最大值和最小值。很显然,没被询问到的元素都是没用的。这样,就可以用 3N-1 次询问解决问题啦!