【转】CTSC 2012

想要为你改变却变不了预留的伏线

以为在你身边那也算永远

仿佛还是昨天可是昨天已非常遥远

但闭上我双眼我还看得见

 

Day 0

CTSC之前的分数,似乎是rank 5

在最后进队的4个人中,只有两个是互测+作业前六(ayq和我)

 

Day 1

第一题显然的枚举+容斥,但是这个判断大小太大自然了……写了一点感觉不爽,就交了个错误的判断上去,结果骗了10分。

第二题裸电路题,分压定律直接秒。写完60分发现100分非常简单。然后……感觉NOI以来,每场考试第二题都完跪。因此没敢写 = =

第三题提交答案题,果断最先做。

做出来的:123小点,4SCDP,8构造,9DP

没做出来的:567对每个双联通块DP,10Hamilton路上加很少的边(对于度为2的点缩起来,然后点数就很少了,直接搜就可以了)

搜索方法:每次删最短路上的某个边

提交答案题做得非常开心……

 

分数:

zpl 165

wqs 164

ayq 151

gyz 142

lich 141

stx 11x

clj 68

[以下略]

 

中间断层非常可怕……

算上之前的分数,除了最后两名(姓名略去)之外,其他的都是完全按照一试的分数……大囧。

 

CLJ搞了全场第一题,最后写跪了……momo

 

第二题物理题严重拉分。zpl和wqs是100,ayq, gyz和lich是60,stx是30,clj是20……

于是有人吐槽这是物理国家队 TAT (人家明明是搞ChO的啊喂!)

 

第三题集训队第一~只比非集训队第一低7分。

 

Day 1.5

上午去国家博物馆。集训队只有gyz clj zl lhx(不是教主)去了

下午答辩……惨跪……(不过第二天上午才知道我答辩这么弱居然还没被lich踩)

 

55555人家就是弱嘛!!!

 

晚上taowb请客~

 

Day 2

第一题一看阿米巴就知道是范爷题……裸hash预处理+裸DP(当然,单调队列转移)写得非常舒服,当然,得分也只有80分。但是我感觉常数优化一下是能A的 = =

第二题真的看不出来是will出的 = = 由于第二题必跪定律,果断水30分走人,写了各种程序进行对拍  = =

第三题欢乐的提交答案题。“in文件打不开!” 右键emacs不谢。因为我完全不会任何算法,所以12345用n^2 m^2 log n的暴力+简单常数优化。跑了几十分钟都是能出解的。第四个点没跑完(因为是最后四十分钟才跑第四个点的)。第五个点没跑。67简单递推(我就不告诉你们我完全不会数学),89……我是不会告诉你们我不会做的,10直接n^2 m^2 k暴力,半个小时出解。

 

分数:

xj 210

lich 180

clj 180

gyz 170

[以下略(其实是我记不得了?)]

 

雅礼各种跪……似乎他们字符串比较弱 = =

 

之前猜题的时候,范爷出的题要么是动态树要么是后缀自动机,结果范爷出了后缀自动机。如果是动态树,我现在就没脸在这里写吐槽了……

第三题无数人AC……我只有60分,弱弱弱弱弱弱弱弱弱弱弱弱弱弱弱弱弱弱弱 (不过我只会直接暴力都能过这么多点其实已经非常神奇了?)

 

wqs非常悲惨……第一题后缀自动机写跪,0分。最后他分数120。momo

由于二试过于水,导致CLJ没法翻盘。持续momo

 

clj二试之前rank 7,二试rank 2,最终rank 8……

@D8

(为什么不是延续第四呢……)

 

Final 6: lich gyz zpl ayq wqs stx

 

lich zpl ayq stx面试都各种神……

wqs似乎准备不够充分 = =

我感觉还好,不过跟lich等神比起来还是弱爆了

 

Final 4: lich ayq zpl gyz

可见我由于语死早,变成了第四。

 

 

 

 

 

Last Chapter

显然,前面都是流水帐,以下正文。

 

CLJ曾经说过,现在的OI,就是比谁跪的少。

Indeed. 

 

@CLJ d1p1 & d1p2  @wqs d2p1

 

如果他们没有跪,那现在又是怎么样呢?

 

 

祝大家都能进队。。其实只要不要有遗憾就好了呢。。。

 

 

倒在WC的nzk clj

跪在NOI的zxk, dyf

省选5人限制的雅礼群犇 (雾)

 

一年前的qq

两年前的wyn

三年前的bjin

 

谁能没有遗憾呢

 

 

 

可惜不是你

陪我到最后

曾一起走却走失那路口

感谢那时你

牵过我的手

还能感受那温柔

 

 

P. S. 

本届CTSC最令人感动的,当属liangd。

他是这么说的:“我想在OI生涯的最后一场比赛中,很帅气地做出来一道很难的计算几何题”

他在考场上写出来了梯形剖分。(虽然实际上不需要)

得了30分。暴力分。

[ZOJ Monthly, February 2012 Problem J Gao the Variable][ZOJ 3579] Solution

=.=鉴于昨天ZOJ月赛我的题坑了不少神牛,于是发发solution。

【题目大意】

给定n个变量,m个约束关系,p个得分规则,问在满足约束关系的前提下最多能得多少分。

n个变量的值只能为0或1

m个约束关系有a or b = x , a and b = x , a xor b = x三种类型

p个得分规则的形式为:(i,x,j,y,w),分别表示第i个变量值为x,第j个变量值为y,则可以得到w的分数。最终得分为所有得分之和。

1<=n,m<=100 1<=p<=5000

 

【标程解法】

只关注n个变量和m个约束关系,那么显然是一个2-sat的模型,但是加入得分规则以后,瞬间就变成了NPC。

于是就搜它…T_T

先对2-sat那个图(不知道怎么搞的看这里http://hi.baidu.com/edwardmj/blog/item/13faf30338fb2a057bec2c81.html)求个传递闭包。

然后顺手按强连通缩下点。强调一下2-sat那个图里一条边(x,y)的意思是如果选了x,那么一定要选y。

题目保证有解,那么我们只考虑有解的情况。

定义:我们称两个缩后的点A,B间有冲突,当且仅当存在var_i∈A,且var_i’∈B

先来证明一个东西:如果这个2-sat存在解,那么只要保证选择的每一步不会构成矛盾(就是说每次新选进一个缩后的点,此点均不和任何已选的点有冲突),并且选到不能选为止,则最终选出的缩后点集里,一定包含n个缩前的点,且这些点间互不冲突。

也就是说,只要每次都不矛盾,一定能选满所有变量从而得出一组解。

证明如下:

会造成选不满的情形只可能是var_i和var_i’都和已选的点冲突了。也就是说像这样(图中把已经放入已选集合的点标为红色):

我们回忆一下2-sat里面一条边的意义:(x,y) -> 选了x,那么一定要选y。因为我先作了传递闭包,所以根据图中的逻辑关系,可以想象必然存在对应的这两条红色的边。

不要忘记2-sat这个意义下边的传递性,于是再补两条边。

围观上面的两组点,因为2-sat里边的意义,所以左边的两个蓝点也要选。。。

于是得出结论,如果出现两个都不能选,那么一定是已选集合里已经出现了矛盾,而我们选的时候保证不出现矛盾,那么就一定能选满。。。所以就证完了。

于是乎,我就按变量的编号顺序搜索,如果这个点已经被选择了一个值,自然就不选另外一个值,否则就两个值都选选看…

至于剪枝什么的,就设一个贪心的估价函数,具体方法是在还不能被确定值的变量里面,当成两个都可以同时取,算算可以拿到多少分。由于这个值一定比实际值优,所以最优化剪枝的时候如果当前得分加上这个贪心的得分还超不过目前的最优值,那肯定没意义了。

还有就是在搜到两个都可以选的时候,先搜贪心出的解比较大的一个。

【吐槽】

本来想出个用最小割解的,然后纠结到后来发现实在不会了,v老师就提供了好多个奇葩的代码给我,然后全被我cha掉了。那些代码大部分上都是最小割求的较优解…

看完以后离deadline只剩8小时了T_T,于是死马当活马医出成了搜索题,胡乱加了两个剪枝以后随机了几十个数据发现100都妥妥的,于是就脑抽把范围打成100了…

如果是刻意卡的话,我觉得这个其实跑40都有问题,毕竟大致复杂度是O(2^n)的。

总之这不是一道好题,在此向各位被坑的童鞋表示歉意。。。

【代码】

http://ideone.com/UnUkI

PS.缩进可能看起来略疼…把tab换成4个空格的大小就好

记MSRA副院长郭百宁教授的讲座

– -圡人一只,就记记流水账,吐槽什么的就免了。

首先是他认为研究的4个层次。

1、编程实现、实验之流 

2、唯像理论                     

3、理论架构

4、数学

目测是这个东西:http://baike.baidu.com/view/566568.htm

//吃青春饭的程序员被划分到第一层…=.=

然后是MS里面程序猿的career paths(- -我没太听得清楚是不是这个词,根据上下文这个词较为靠谱).

据称搞研究的因为只占1%,他就一带而过了。

接下来大致是:

tester(据说比较boring…测bug的 MS 1/3的人在干这个)

软件架构师(好像主要包括对project分模块的,还有具体分配哪些人干什么活这两类)

还有就是对一些别人的库接口很熟悉的,封装好给自己人用的(忘了叫神马= =b) , 反正是强调技术与沟通能力的。

然后貌似又强调了创造力和快速获得知识的能力。

有个比较囧的point是知识都在图书馆里,有什么必要把脑袋装得满满的呢,只要用得时候能快速的从库里获取就好了。

(= =b   想起  CF  unknown  language 被屠一脸    btw shi哥真是太可怕了)

恩,当然比较基础的东西还是必须学好。

接下来介绍了场、势、图像的一个三角形,然后表示这些能够互相推导什么的- -。5555,完全没听懂。

然后就说了周昆老师和鲍虎军老师和他有合作做那个动画的(- -||| 然后就想起u博和飞博)。

接着展示了一些他们那个算法对比传统的有什么优越性- -。

映像比较深的是那个把太阳放到另外一幅图像上的过程。

一开始是直接无技术裁剪粘贴。。。看起来极度不和谐。

然后他表示利用新图中对应位置外围一圈的轮廓,加上原图像中太阳部分的势,利用拉普拉斯方程(http://zh.wikipedia.org/wiki/%E6%8B%89%E6%99%AE%E6%8B%89%E6%96%AF%E6%96%B9%E7%A8%8B)就能算下来每个点的颜色,于是乎看着就非常和谐了。

– -,接下来还展示了将某PPMM和北极熊放在同一水池和谐相处的过程。

利用这个以拉普拉斯方程为基础的算法,还能做出利用2维的线控制三维对象的效果,然后就能轻松搞出比如怪兽跳芭蕾舞什么的东西。动画的制作就比较方便了。

好多东西不记得了,记一下,不然以后忘光了就等于白听了。

btw

最后结束以后一位疑似MSTC的学长喊住我,对我说:你也来听这个吗?然后我发现我貌似认不得这位学长,于是恩了一下。然后他说进去听吧,我就没反应过来,结束了还听什么…不确认有没有听错就没回话。感觉非常囧= =|||.

5555,不怎么擅长和不熟的人搭话=.=,于是学长见怪莫怪。

Regional 2011后记

很难过吧。两个银牌。特别是第二场,银牌第三什么的…

回顾这两场regional比较怨念的东西。

第一场是被for (int i=n-s1;i<=n;i++)      被n=INT_MAX卡了半场。然后题也没看清就开始敲F。

第二场是E一直TLE到死。然后戴神赛后告诉我,答案是对的,时间也在比较靠谱的范围内,不是超得很多,顿时就泪流满面了。

实际上造成悲剧的因素还有很多很多…

还是怪自己不够扎实吧。之前斯坦纳树的题一直都过得比较勉强,跑得挺慢的。自己也没太在意,过了就OK。没想到这次,就被这常数屠了。实际上那个写法确实就是比较挫。

两场都最后都是手握两题比较靠谱的代码,都是1个没过。

弱死了弱死了。

于是,

接下来CF尽量保持Colonel吧。General太遥远了。。。TC也用力练红

然后,=.=希望省赛能把杯夺回来。

恩,其实也不该把结果看得太重。

来两场Regional,在学长们身上学到了好多东西(特别是vout),也见到了很多神牛和传说中的师父,还是比较愉快的。

Anyway, enjoy it~