作者存档：edward_mj

随笔

  1. 很无聊地骑着自行车在校园里逛了一圈，看着穿着求是服 || 军服的学弟学妹不禁感叹，哎呀，大一就这么过去了呢。看着校园里忙碌的身影，心里突然冒出这么一句话：努力不是为了向别人表现什么，只是不想让别人在我面前展示赤裸裸的真实。
  2. 说说集训吧
    组队集训已经打了有11场左右了，总的来说集训成绩还是很不错的，似乎不怎么比上一年的1队弱吧。队友都挺给力，基本上现场有2个队过的题目，我们至少都是有靠谱想法的。但是手速是个大问题，我的手速算是比较快的，prowindy比较正常，而zYc就比较慢…这样的节奏导致我们基本上每次可做题都没做完，比赛就结束了。这种情况我也不知道要怎么办，毕竟手速不是一朝一夕的事情。本来今年不想在1队混,但是在prowindy的诱拐以及各种各样奇怪的因素下，还是做了1队队长 :Weary:实际上我是个缺乏领导力的人，看到数据机构题、图论题什么的就很不怕死地跑上去搞，所以我们队的任务分工主要还是由经验老道的prowindy同学执行。既然不这样都这样了，就只能用力搞了吧。吐槽：发现自己真是个心软的人啊，只要不是太坑爹的情况，就挡不住别人的请求…
  3. 昨天和猛犸等去吃饭，讨论起当时组队的事情。发现原来想去final的人有很多，如果我不在1队的话，组队反而就好办得多，但是当时又跑去了VK CUP，大家都以为我很想去final，于是乎就成了现在这个状况了。仔细数数真是坑了不少人…席间又说到今年的情况，我说了一句，我们队应该还是能和别人家的2队刚的吧。然后被猛犸呸了一脸。 :Sad: 确实啊，这点自信都没有，真是搞毛线…
  4. 关于我们奇葩的队名
    来历是prowindy觉得取A开头的字典序比较小，于是我答复了一个Arcadia，然后prowindy又要求凑一个大写的C，凑出AC来。于是翻了翻字典，-.-，Convent出现在我的眼前。于是乎两个拼接在一起，就成了似乎具有里番色彩的ArcadiaConvent了。大概这要成为ZJU 1队史上最奇葩队名了吧 :Beer:
  5. 昨天是七夕吧，又想起了一些事情。不管怎么样，都过去了。吃一堑长一智，感谢你让我变得成熟。但也就这样吧。

新blog落成

建这个Blog有这个几个原因：

1、百度的那个换新版了以后简直不能用啊！

2、很久没有写blog了，最近集训有些想写的东西。

3、以前对网络的各种东西完全是一无所知，但是上学期上了无线网络与应用，对一些网络概念有了最圡的认识。现在想实践了一下…

于是乎，昨天跑去ucvps租了个vps，配置了一下，装上了ubuntu11.04，然后今天去万网注册了这个域名。按部就班地配lnmp，ftp，mysql，php，wordpress，在犯了无数不能忍的错误之后，终于配好了…不容易啊T_T，于是纪念一下。

【转】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个空格的大小就好