CTSC&APIO2015游记

5.3

这天报道……

下午和@Asm.Def @Chenyao @CJJ 跑去北海公园旅游
本来准备去上机的……结果走到人大门口地图处发现道路阻且长(要从人大的东南部越过山和大海到西北部),不如高卧且加餐……加餐……然后果断转身上地铁,北海公园走你┏ (゜ω゜)=☞
当天风儿非常的喧嚣,被吹了一脸……
看到了传说中的白塔……“四周环绕着绿树红墙”……以及奇怪的北京小学生作文展,还有约一个排的武警拿着透明的防爆盾默默走过……买了联票,然而在白塔处选择了一条逗比的路线结果没看到主建筑群,在团城处发现它关门了……所以等于联票并没有什么用……Orz
北海公园某偏僻角落处有若干长椅,基本每个上都坐着一对情侣,然后我们就去了,然后情侣们就走了……233
最后在北海公园买了一坨庆丰包子带回宾馆作为晚饭……
最终也没有上机……→_→反正笔记本上装的有NOI Linux,晚上学习了新的对拍姿势,不用奇怪的什么[$? -eq 0]了……

5.4

这天是CTSC Day1

第一题:暴力!对了再打个树的情况。非树情况就是floyd的N^3直接搞,树的话就是Tree DP。
第二题:暴力!就是纯暴力。
第三题:暴力!……等等这是提答,就是尺规作图。给出x轴、y轴、原点O(0,0)、N(1,0),要求作出某个点(x,0)。每个点的x都用一个表达式给出,表达式的意思是类似于sqrt(2)+sqrt(3)这样的式子。
尺规作图我小学的时候在科普书上看过……总之大致是,在给定1的情况下,可以完成:加、减、乘、除、开平方这五种操作。并且只有用这五种操作能够表达的数是尺规可做的。(后者的证明貌似十分复杂……)
加减很好办……比如有了A(a,0)和B(b,0),那么过A以|OB|为半径画个圆,这个圆和x轴有两个交点,自然一个是(a+b,0)一个是(a-b,0)。
乘除略难一些。
乘法大致是这样的:

假设N(1,0),NA=a,OB=b,AN⊥OB。作直线BC⊥OB交OA于C,那么BC=a*b。
除法是类似的:假设BC=a,OB=b,ON=1,作AN⊥OB交OC于A,则AN=a/b。
当然这个过程需要若干次“过直线上一点做其垂线”。方法很简单:假设要过B做OB的垂线,那就以B为圆心,1为半径画个圆,交OB于E、F。然后过E、F各以2为半径画个圆,这两个圆有两个交点,把它们连起来,就是B过OB的垂线了。
开根号更复杂一些:

假设A(a,0),然后可以作A1(a+1,0)。设OA1终点为M,过M以OM为半径画圆,过A作OA垂线和圆交于C(C在x轴上方)。
这时CA=sqrt(a)。
为什么呢?在直角三角形OCA1中有CA⊥OA1.根据射影定理,OA*AA1=CA^2.而OA=a,AA1=1,所以CA=sqrt(a)。
然后我就把这几种基本操作给“封装”了一下,写成了函数(支持自动统计指令数,返回新图形的标号)。
然后就可以很轻松地搞出来好几个式子了……虽然!常数巨大(真的是巨大),也就是指令数非常的多(显然上面整个过程都只考虑了‘可作图性’,根本没想怎么尽量减少操作次数……)
然而这是一个常数问题,抱神犇@Asm.Def 大腿应该能大力出奇迹……
印象深刻的几个:①迭代求2^32,完全不知道不用64次操作是怎么实现的……②把大数转化成二进制,用类似快速幂的方法。③两个数同时这么做……④立方倍积问题(出题人你在逗我)……⑤传说中的正十七边形……
至于不会做或者常数太大卡不出来的几个,用0或者1骗一骗就能拿1分了。

Day1的结果是:T1暴力出奇迹拿了45分(最后一个点不知道怎么就卡过了),T2暴力跪了Orz,T3拿30分,总分75.

听讲题的时候发现大家都A了第一题,Orz……
第一题题解本质就四个字:“动态规划”,其余都是吐槽题目的内容,据说暴力95分?(然而我并没有写出来)
第二题正解是可持久化平衡树套可持久化平衡树(出题人你在逗我→_→),据说乱搞能A?
第三题……总之卡卡卡,卡常数,不卡还是人。

5.5

集训队员讲论文+欢脱的社会活动

上午听15位集训队员讲论文……他们的论文内容是:SAM,SAM和SAM(后缀自动机Suffix Automaton)。
话说SAM这个名字总让人想起下面这种SAM……

那个美国的U-2,比你们高到不知道哪里去了,我和它谈笑风生!
好吧,其实除了SAM,其他人讲的我基本都听不懂……全程“啥啥啥这是啥”和“啥啥啥这又是啥”
策爷讲了个生成函数……在清华学堂的组合数学课上看过一点,说有序排列要用e^x这样的函数啥的。
某人讲了OI中的物理题……杜子德表示十分资瓷,表示还要搞一搞生物啦,化学啦……
那就先Orz物理神犇@Asm.Def
还有“给输入输出猜题目”的题答题,王宏:“然而你这个对于考察算法和数据结构并没有什么用……”

社会活动是去国家博物馆。
@Asm.Def 表示他要睡觉,@CJJ 表示他要在宾馆浮躁,于是我和@Chenyao 跟着去了……
然而大巴被堵在了路上,从大巴停车的地点到国博又走了很久,将近三点钟才到国博……果断请假,延长参观时间自行坐地铁回酒店。
在国博看了传说中的“复兴之路”展览……(没错,就是新闻里报道的那个),有若干历史书上图片的高清版……还有一些类似“南极科考队首次到达冰穹A点时携带的笔记本电脑”这样较现代的展品……同时吐槽了一番某东方大国的武器涂装为!什!么!这!么!土!鳖!
然后去天安门……从天安门北边地下道进入,南边地下道离开。全程对旗杆熟视无睹也是醉了……许多路灯柱上缠满了摄像头,颇有一番赛博朋克风味……
发现毛主席纪念堂只有上午很短一段时间开门……其门口密集地堆放了若干排伸缩门(是叫这个名字吧?),可以推测极限状况下参观的人是有多多……
然后去旁边的李先生牛肉面吃了晚饭(居然是点餐而非到吧台取餐,感人肺腑)

5.6

这天是CTSC Day2

第一题:容我三思……
第二题:暴力!暴暴暴,不暴还是人
第三题:这是啥……
看半天看懂第三题题意后看了一下数据,发现这根本不可做嘛……然后就写了个(错误的)第1个点,发现有问题后果断弃疗直接搞第一题。
第一题的大致思路是:每一层之间的联系仅仅是那K<=4头牛。于是,①枚举(int)10ln(A+1),②枚举每一层K头主链牛的性别,然后对于“给定(int)10ln(A+1),和第t层的主链牛性别,要求最大化该层收益”这个问题应该就是一个最小割模型了(因为要将所有其他牛的性别选为雌/雄之一)。 这个最小割模型一共要运行大致500*2^K次,其中500差不多是10ln(A+1)的最大值。
求出来这500*2^K个值后,可以DP:f[i][j][s]表示:当前DP到第i层,亲缘链上相邻的异性牛有j对,这一层主链牛的性别状态是s。状态数是O( N^2 * K * 2^K ),转移O(2^K)。
于是先打个Dinic再说。
打完发现SB了,搞不出来模型……所以去把T2的暴力给敲了,然后改了一下T3的第一个点,真正拿了1分(没错,就是1分……虽然当时不知道)。大致就是一个完全二叉树,然后每次遍历路径,强行给节点赋值。
然后发现搞不出来了……先上个厕所压压惊,遇到了@Chenyao 神犇,Orz之。
Orz回来突然发现搞出来T1模型辣!某个点在S集表示它没有改变性别,在T集表示改变了性别。假如(x,y)产生了繁衍关系,那大致是S->x的边,x->T的边,x->y和y->x的边都各有一个容量,几种情况列一列式子就能发现具体怎么设了。
然后T1就码出来了。
然后剩一个小时,就是在不断的调T3……结果最后还是1分_(:з」∠)_

结果是:第一题100分,第二题暴力跪了Orz(原因是set中erase(end)会跪掉),只有5分,第三题1分(!!!),总分106
整个CTSC总分75+106=181.

第一题的正解就是这个(这个题居然没什么人A……’丽洁没有判断题目难度的能力‘)。
第二题是结论题,正解是奇怪的线段树
第三题……貌似就没什么人得分,正解不是最优解,和乱搞差不多→_→

然后听总分前6口试,就是英语一番饶舌。还是中国人说的英文我能听懂啊!→_→You’re good at 演小品!

晚上颁奖,是总分第13名(精准卡在了金牌第二页的最后一名),领奖的时候我自动地站在了边上……

晚餐(整个河南队)和新疆神犇@prey 在燕山大酒店旁边某饭店吃了一发烤鱼
@prey 表示新疆本地并没有什么切糕23333333,还表示新疆高考少数民族加50分……不行我需要静静(别问我静静是谁)

5.7

这天是CTSC和APIO之间的浮躁日

在宾馆浮躁一上午,中午跟爹妈去吃了鼎泰丰(*^__^*) 
然后duang!作死神兽@zlx 闪亮登场!

我们的套房只有四个人,所以@zlx 同志睡在了沙发上……

下午去颐和园浮躁
从北宫门进去,一开始先非常逗比的爬到了山上……爬了很久才找对地方到昆明湖边,一行人对着一条挖掘船看了半天……然后走到东门,租了个讲解器(讲解自动机!)
然后又沿着长廊所在直线(即昆明湖的北岸)从东走到西,再从西走到中,再从长廊正中向北上佛香阁,出北门。(前面半天山白爬了……)
一路上给小伙伴们转述讲解内容……被科普了一波“台湾今已归日本,颐和园又搭天棚”里的那个“天棚”。有个中国联通赞助的“清代皇家电话局展览”……
昆明湖风景非常好。景区内见到最多的是两种人:①各式夕阳红旅行团,②老外。大多数建筑的介绍牌上都有“被英法联军烧毁后重建”……这牌子还有英文的,不知道旅游的英法人民怎么看?→_→
晚餐必胜客。

5.8

这天APIO第一次培训

上午两场讲课,第一场是讲概率……(貌似就是大学的概率论课程科普,贝叶斯公式出现频率不低),讲到了蒲丰投针试验。
第二场是哈希函数和A*算法(中的股价函数)。Byvoid友情出现(推荐的SDBM和BKDR两种字符串hash函数)。
中午试机没去,因为头一天在酒店注册过了。
下午黑神wxd讲面向对象……课件写得很萌,全程皮卡丘,皮卡丘和皮卡丘。对了还有兔狲。讲了下如何用面向对象思维设计智能体大赛的比赛平台。今年智能体大赛是Lota:LOL+Dota……
表示终于看懂“继承”了,感人肺腑。
中午讲课快结束的时候本来准备提前跑,结果王宏过来了:“后面的同学不要走……”
然后王宏讲了一些APIO的注意事项,拖了一段时间
他讲完之后众人狂奔向食堂!我途中手机还掉地上一回
晚上外套丢了Orz(后来证明就是中午狂奔的时候忘带了),同时吃了一波DQ冰激凌

5.9

APIO考试日

有去年APIO的前车之鉴(题非常简单),所以准备想想分数高一点的做法,别直接第一档暴力弃疗……
T1:从高到低枚举每一位,看能不能为0.“看能不能为0”的方法是:先计算出一个数组f[i][j]代表i~j能否分成一组。然后DP:dp[i][j]代表前i个能否在f的限制下分成j组。这个做法是70分的。一开始写错了(以为是每一组个数在[A,B]内,而实际上是组数在[A,B]),然后突然发现这个算法是O(N^3logS)的,理论上过不了……怎么办呢?机智地把dp数组的j那一维用bitset表示,用位运算转移。然后交了一发,就AC了!bitset大法好!大力出奇迹!
T2:好难不会写……先打个暴力再说。把楼当做节点,进行SPFA,在松弛时枚举楼上所有doge(doge火遍全球……)以及它们的所有跳跃方案。这个理论上是70分的。交了一发,结果直接AC!我也是醉了
T3:真难……先写K=1,K=2的情况想了半天。最终搞出来的结果是:随着i从左向右移动,最优的j一定也逐步向右移动。所以i逐渐向右扫,j也逐渐向右扫,在它们每一步移动的时候维护答案。怎么维护呢?显然一个人是走i还是走j取决于家和办公室的中点,所以按照中点排序,单调扫描即可。实现非常麻烦,有成吨的细节需要注意。
最终12:40,也就是用时3小时40分钟面板AK。感觉非常虚,如果加强一下数据八成要GG……
然后就跑回房间了……试图看一发毛子阅兵,发现是下午三点钟开始,看不成了。
两点钟回人大等队友……在明德楼外和wwx神犇谈笑风生了一会,得知延长半个小时,亏我不到两点就来了……
然后就又等了半个小时,中午徒步到1.4km外吃汉堡王

下午讲题。
T1正解是:后面2000的数据保证A=1,所以只需要设dp[i]代表1~i至少划分成几组。
T2是妹子讲的!正解是:sqrt(N)以上的跳跃直接建边,以下的每个点拆成sqrt(N)个点。然后BFS。貌似直接Dijkstra也能大力出奇迹过掉。
T3正解貌似是什么“分两段的中位数”

晚餐@prey 拉着我们去吃了一发人大内的西餐,比较壕……奶油烤大虾十分好吃。烤小牛肉串(毛子的烤串!你们怕不怕!)一般,早知道应该点闷罐牛肉了。

晚上讲课是KD-Tree和V图和优势点树啥的,@prey 表示讲的没有《计算几何》那本书好,于是直接看起了《计算几何》。

奇葩的是,下午到报告厅时发现外套被完好无损地放在了后排座椅上,等于是给APIO涨了一波RP,然后就找回来了……

5.10

APIO第二次培训

据说上午一堆人去了北大ACM?
上午讲了讲“游戏题”啥的
下午讲真实感图像渲染,好在我之前写过光线追踪,可以谈笑风生一番……
讲了photon mapping光子映射渲染技术,就是从光源不断地发射光子,然后追踪这些射出的光子,看它们最终到了哪里,组成一张“光子图”,用它(大致类似于把这些光子作为点光源)去计算ray tracing到的每个点的光照。这个(在算法上)解决了一系列问题,例如:对于普通的光线追踪反正我是没想出来“某个凸透镜聚光照亮某一漫反射表面”这种情况怎么解决。
第二节课是一大波O(1)空间的面试题……非常的脑筋急转弯

晚上颁奖。我又自动地站在了边上……

物理的亚太竞赛APhO也是这几天,它的画风一看就非常的高端大气上档次啊!有木有!
有图为证:

高端竞赛是这样的:


某逗比竞赛则是这样的:

(我就是中间那只逗比,我右边是男神@Asm.Def ,大家快来Orz)

然而!某逗比竞赛也可以变得高端起来,像这样:

这位就是@Chenyao 神犇!Orz之

所以我这逗比是没救了……
估计大概是由于照片太挫,学校官网上的新闻预览就直接用了证书……→_→
不行我需要静静……
最后,不要问我静静是谁……

发表回复

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