ZJOI 2015 Day 1题解

题目:http://pan.baidu.com/s/1c0uA9Sc

标程:http://pan.baidu.com/s/1dDCj8bv

数据:http://pan.baidu.com/s/1qWNs1Us

Mst

这个题目是用来送分的,思路和我WC讲过的一个题差不多。看链接中的课件里的mst一题。

首先注意到,答案就是最小瓶颈生成树(最大边最小的生成树)上的最大边的期望。

进一步分析可以注意到,考虑一个x,如果<x的边合起来不能使得图联通,<=x的边合起来能够使得图联通,那么这个图的最小瓶颈生成上的最大边就是x。

那么,用WC讲过的同样的方法,我们可以得到一个多项式P(x),表示<x的边不能使得图联通的概率。

那么注意到,我们只需要对P(x)从0到1求积分就是答案了。为什么呢?因为P(x)也是答案>x的概率,这样相当于一个分部积分。

(这样说可能对于不熟悉微积分的同学来说可能不好理解,不妨考虑离散的情况。比如a有5种取值,0,1,2,3,4,令p[i]为a的取值>i的概率,那么EX[a]=sum p[i]。这里也是一样的道理)

Tree

其实这个题目并不难,题目等价于支持修改点权和寻找整个树的带权重心。

可以考虑使用点分治。注意到如果当前分治点是u,那么显然,我们可以先看看u是不是重心,如果不是,那么重心只可能在u最大的孩子里,这样问题就变成了u的一个子分治的子问题。

当然对于子分治我们还要考虑从u出去整个外面部分的影响,由于树分治最多有logn层,这样的影响也只有logn个,简单的处理就可以了。

Substring

首先题目中有一个关键条件是说叶子的数量不超过20个。

我们不妨对每个叶子都以它为根建一个Trie。

那么注意到整个树的任何一个子串,都是某个Trie上从一个点到它的一个子孙的路径。

那么,我们可以把这20个Trie合并成一个大Trie,然后求这个大Trie的子串数量就可以了(Trie的子串指的是从Trie中一个点到它的一个子孙)。

这可以使用比较经典的后缀自动机或者后缀数组实现。

My favorite problems in 2014

突然想发这样一个帖子讲一讲自己在2014年里见到的比较喜欢的算法竞赛题目,也算是对于我的算法题的偏好的一个总结吧。

就先从我自己出的题目开始吧。

  • biconnected and sconnect 这两个题目其实也说不上特别喜欢,不过感觉想法还是稍微有点意思的。大概的想法都是反着来,计算不满足条件的图的数量,然后注意到双联通分量和强连通分量的划分一点枚举以后可以缩成一个树/DAG,而树和DAG的计数问题都是大家所熟知的。因此就能做了。不过这里有个比较有意思的地方是如果直接用树的n^3的求det的方法,其实不能做到最好。如果使用枚举叶子然后容斥的做法,就也能做到3^n的复杂度。这是我后来才想到的。
  • hero meet devil and square 这两个都是从dp of dp的想法衍生出来的题目。做法其实是很常规的,都是非常经典的:要对满足某个条件的对象计数,考虑判断这个条件是否满足的小dp,对使得小dp满足的输入数量计数,并且通过分析减少状态数量。分析以减少数量这一步在这两个题目中都比较直接。在我的冬令营讲课中有讲的一道Jigsaw的那题,它的奇偶性分析还是挺有趣的。
  • MST(无连接)。我的ppt里有。这题其实还是非常有趣的。有两个方法都能推出正解也都很有趣。都用到了期望的线性性。具体来说就是得出MST的整体值还是比较困难的,但是MST这个问题不是一个非常global的问题的,对于每条边存在一个只需要部分信息的判断它是否在MST中的方法(比它小的边是否将两端点联通)。有了这个以后就能对每个边分别求他们对MST期望大小的贡献。因为现在我们只focus on 一条边,所以自然也就大大减少了需要考虑的对象。从而就能减少我们dp中需要考虑的状态。
  • 紫荆花之恋。我在WC 2014中出的题目,这个题目的核心在于可以意识到替罪羊树这一技巧,能够适用于一切依靠子树大小来维持平衡的结构。那么,它必然也可以被使用于点分治这一结构。那么我们就可以用替罪羊树来维护动态的点分治。当时觉得还挺有意思的,不过现在也已经不怎么研究数据结构了>_>。

感觉自己出的还比较喜欢的题目暂时就这些了,下面列举一些比较有趣的别人出的题目:

  • SRM 641 1000 不得不说我觉得这是一个神题,做法非常巧妙。核心的思想可能跟前面提到的MST一题类似,都是把需要计算的期望值分成许多个小部分,然后每次只计算一个小部分,由于每次只关心这样的一个牵涉面比原先小的问题,因此需要记录的状态数量也大大减少,从而达到降低复杂度的目的。我觉得这是我年度最喜欢的题目。
  • Substrings,见我WC讲课的ppt。不得不说这个题目也十分的巧妙。做法还是比较经典的对于S和T,考虑T的哪些性质在枚举S的时候是有用的,然后将T划分成一些等价类并对等价类计数,最后再计算每个等价类的合法S数量。这样的想法是很直观的,但是令人没有想到的是,这里的等价类即使在n<=50也是很少的!
  • Jigsaw 不得不说这题其实是很多想法的来源,题目见冬令营讲课的链接。这个题目其实是一个非常经典的“dp套dp”的题目。详细的之前也说过了。

先写到这里有空再补吧:)

最近打的几场比赛。。。

上周参加了SRM 613。。。

250和500都很简单。。。但是900感觉可以说是一道还不错的题目。。

题目大意是给你一个n*m的borad,要你在上面放一些棋子,每列最多一个,并且第i行的前L[i]个和后R[i]中都要各有正好一个,并且满足L[i]+R[i]<=m。

当时我不怎么会做。。。第二天灵光一闪反而想明白了:

首先注意到我们可以交换两行的L[i]或R[i]值而不影响结果。

第一眼的想法往往是按L[i]从小到大排序,然后一个个放,那么第一个思路就是L[i] R[i]都从小到大排序然后dp。但是这样的到后面可能会有L[i]+R[i]>m,重叠了就没法做了。

仔细想想我们还有另一个dp方法,把L[i]从大到小排序然后从少的那一列往多的那一列放。这样需要记录还有几个行没有放棋子。

那么考虑整个问题,实际上我们L[i]从小到大,R[i]从大到小排序然后两个dp一起跑,既记录L[i]这边这行还有几个列能用,又记录R[i]那一边有几个行没有放旗子。然后就能解决这个问题了。。。

因为有事情没打CF 238。。。后面补了一下。。。

卧槽。。。这哪是2个2000啊。。。我觉得这题目难度只有500 500 1000 1000 1500好吗。。。

A还有点意思。。。注意到mod 2下只有对角线有意义。

C 直接dfs暴力构造,注意到无向图上dfs树上所有边都是回边的性质是很好做的。。。

D不说啥了>_>。。。。

E。。。。不说啥了。。。>_>。。。。

 

IOI 2013 酱油记

按照传统每场比赛回来似乎都要写酱油记,那就这样吧。

Day -3:

坐飞机前往北京,入住了一个在中科院物理科学院的内部宾馆,不得不说条件差到没有条件可言,啥都是坏的也没热水,网速只有几kb。感人肺腑。我跟xhr住在一个房价,qmd跟wkn住另一个房间。

 

 

 

 

 

Day -2:

 

参加了一下一场ACM形式的所谓练习赛,题目都没啥好说的。网络太垃圾也没事干只好看ipad mini里的俺妹动画。

先看了了几集,就是男主跟黑猫谈恋爱的那几集,最后居然分手真是太**了,妈呀,为啥三次元没有黑猫这么萌的妹子,混蛋啊,京介为什么如此现充?

Day -1:

开了动员会,感受了一下。hwd教练给我带了那个CTSC用的红轴键盘,于是我们就开心的出发了。飞机上各种睡不着觉。

于是就看完了俺妹,绫濑小天使好萌啊,京介你个混蛋!嘛,虽然我是妹控更加喜欢妹妹啦。么么哒。又看了言叶之庭,由于当时太困加上我比较煞笔,现在回味一下只记得足控足控足控足控。

Day 1:

开心的到了澳大利亚,本以为可以上网了,发现宿舍里没有网,只能搬电脑到外面忍着感人的寒风上网。下午补了一觉,感觉还行。

晚上心情比较不错,看了一下平坂读的小说《幽灵恋人》,第一卷还挺正常,讲的是“男主”过着愉快的现充生活,然后青梅竹马的妹子向他表白,然后立刻被车撞死了,然后变成了幽灵(该书的世界观里死掉的10%的人会变成幽灵,幽灵无实体但可以跟他人交流)。然后男主又碰巧把了一个学妹,装了装B然后过上了快乐的现充生活。然后顺便解决了一下恐怖团体的活动。

然后尼玛到结尾,男主突然说自己是个妹子!然后学妹就被吓跑了,我也被吓呆了。

Day 2:

试机赛的时候,我看了一下题目感觉都很傻逼于是打算写一下,结果我计算机几何题把x和y打错,数据结构题又把线段树写错,深刻的感觉到自己要CU滚粗了,感人肺腑。

赛中接受采访,随口造了个大新闻,采访的人问我对中国队的表现有什么期望,我说当然是大家都金牌。记者表示很感动。

下午举行了感人的开幕式,顺便吐槽一下,澳洲的伙食真是感人肺腑,尤其是那天我吃了一种奇怪的饼,直接把我感动的。。。。不能多说。。。

晚上心情不错,看了一下《幽灵恋人》的第二卷,感觉剧情越来越有(shen)趣(zhankai)了。男主现在是女主了,很多男的女的向女主表白,女主却不以为然,有些话我觉得挺赞的。

Day 3:

比赛的第一天,由于出题人太逗逼,服务器感人的挂了,IOI->NOI,我非常不爽,光顾着骂出题人,没能够调节好自己的心理状态。然后更加糟糕的是我的artclass采用了非常白痴的判别方法,但当时我还觉得非常可以AC,真是不能多说,结果第一场考完#5,中国队其他人分别是#1和#2和#6。

考完我非常的愤怒,对傻逼出题人和judge维护人员的智商感到非常感动。

非常神奇的是除了中国人没人过wombats,而我感觉wombats是非常傻逼和传统的题目,只能说贵国OI太NB了。

晚上心情有点忧伤,看了一下《幽灵恋人》的第三卷,我怎么感觉我在看《戏言》???这女主活脱脱一个戏言里的男主的德行嘛,字里行间也感觉平坂读这货是在模仿洗胃吗?还是说他们本质上是一样的?很多场景还是挺感人肺腑的,不能多说。我非常的奇怪的是这跟友少根本一点关系都没有嘛,这货看起来是明白装逼洗胃没啥用,讨好读者才是王道,反正写一大堆自我满足的东西也没人看,还不如写废萌骗钱是吧。

Day 4:

去海滩玩,没有游成泳,有点忧伤。还看了海豹表演,感觉有点逗比。

然后也没啥好说的感觉,稀里糊涂就回去了。

晚上心情还行。想想明天要考试,就早点睡了。不过也没睡着,就听了点歌。把jin爹的炎阳project的歌都听了一下,感觉有点厉害,听说炎阳project要动画化了真是感人肺腑,有时间去补下小说好了。

顺便也听了一下kemu的人生系列歌,各种不明觉厉啊。。。有人知道具体的剧情么,不过reincarnation真心赞啊。。。。跟着学了一下怎么唱。

Day 5:

看完了题目,感受了一下,觉得只能#5滚粗了,有点感动,于是很开心的把cave和robots两个傻逼题给A了。然后看了一下,觉得game大概可以线段树套平衡树艹过去,不过我有点忧伤,因为反正要#5滚粗了,时间都还有4小时,还不如写个重量平衡树爽爽,于是很开心的写啊写啊,1个小时写完了,结果发现我傻逼的看错了题目,有点感动的改完了之后就AC了。然后也没啥事情干,骂了一下day 1的傻逼system。想想感觉#5也还凑合,就感动的睡了一会儿。

考完出来发现前面的人都那啥了,结果我神奇的#1了。

神运气真是感人肺腑不能多说眼泪要都流出来了。

晚上把幽灵恋人看完了,感觉还是非常赞的,对上电波了可能就会很喜欢,对不上估计就呵呵。话说这算是百合小说吧喂,嘛,总而言之不错啦。

在回来的路上我有点感动,发表了一下我对文学和艺术的看法。对现在轻小说的发展提出了一些从小说史角度来看的观点。我觉得,以满足读者为目标写作的轻小说,正是文学的末路的最好的写照,但是感觉也不坏嘛。没有文学,没有艺术,没有音乐的时代也没有那么可怕嘛。米兰昆德拉说过文学就是要探索存在没有被探索过的部分,那么现在的轻小说你看一下就知道他会讲点啥,都是些喜闻乐见的桥段。这就好比说虽然天天去找没吃过的美食爽是挺有趣,但是闲在家里每天吃点自己喜欢吃的东西才是人生嘛。

Day 6:

今天去zoo玩,感受了一下资本主义国家的动物都如此的懒散,真是令人感动,还看那帮人用生命逗鳄鱼,真是感人肺腑。

晚上心情有点不错,于是就开心的看了一下经典废萌小说,感受了一下文化快餐的乐趣。

Day 7:

颁了下奖领了个杯子,顺便跟一群国家的人合了很多影。感觉OI生涯真的是结束了,不过倒也没什么,大概很久以前就失去了结束这个概念了吧。任何东西没有开始过也就不会结束了。

晚上跟美国队切磋了一下乒乓球技术,很感动的被0:4艹翻了。

Day 8:

滚回家了。路上心情不错花了1k澳元shopping了一下。

 

最后还是只能说,It was a huge luck.

CTSC 2013 酱油记

么么哒,又来CTSC打酱油了。由于前几天在TX参加马拉松,所以现在才开始写酱油记。

一晃2年真是光阴似箭,大概去年也没料到今年会这样吧。

感觉也没啥好说的,随便扯扯吧。

Day -1:

比较早就来了,炫教 @梁黄炫 请了我一顿金钱豹,感觉也没什么好吃的,然后就答应他#1了就BG金钱豹(破产FLAG)。不过东西还是挺丰富的,就吃啊吃啊。然后也没啥好干的,就去睡了。

 

Day 0:

很迟才起来,然后跟qmd @乔明达ACMonster 一间房,qmd满满的进队爷气质,令人跪舔不已。看了一下我在CC上出的那题,被一坨人乱搞水过,非常不爽,但是也只能凑合着过了。乱搞哥真是令人跪服啊。

 

晚上去试机,发现键盘令人呵呵,正好zrp @朱睿 过来跪舔我,我就驱使他一起去买了个CHERRY MX 2.0的红轴键盘,感觉中关村不是挺厚道?不是很坑的感觉啊<_<。

 

晚上还是很迟睡,反正早上喝点咖啡就能战5小时,早睡没啥意义,还扰乱生物钟。

 

OK,接下来就是我表现逗逼不已的两次比赛了。

Day 1:

首先,题目是这样的:

我看了题目,感觉第三题煞笔爆搜,第一题的可做性不好说,第二题应该能搞点分。

结果第三题水过之后,想推推第二题的方差,根本推不出,有点不爽搞个30分了事算了。

第一题想了会儿也只会煞笔爆搜,然后就呵呵了。第二个点都构造错,真是不能逗逼更多。

 

成绩出来果然逗逼了,满分的一半都没有,不能多说。

Day 1.5:

颓成狗的感觉,早起去答辩,鉴于我CTSC之前都在沉溺CTB,答辩稿是来之前2天赶的,压力有点大。

不过感觉内容还凑合,结果居然答辩最高分,怀疑评委根据选手长相打分<_<。说实话我感觉还是去年讲的好的说。

下午说要去睡觉补充精神,结果一路玩ipad到5点,不能逗逼更多。也没补到觉。

 

晚上3点睡,没啥压力。

 

Day 2:

这场的表现更加逗逼了,首先看了下第三题,扫了一眼题目发现这不就是Functional Language里的Curring么,那么之前的所有东西都可以看成一个有t个变量的大函数,x如果当参数那么t = t-1,不然t = t-1+x-1,然后就转化成煞笔贪心模型了,一边吐槽为啥出CF A题一边A掉了。

 

尼玛学Haskell也是有用的?听说很多人一看题就觉得太长不看放一边了,感觉不能多说。有时间玩玩Clojure 吧。

 

看了下第一题,感觉50分很好写,就先写了下。

 

然后看了下第二题,由于我数学水平相当逗逼,不会求导做,随便写了个骗了40分了事,很想吐槽出题人的是搞这么复杂格式你自己出不也麻烦么,不能大家都轻松直接输出?抠鼻后来dyh跟我说这个做法只要敢开大可以AC,太感动了。不能多说。

 

结果我更加逗逼的想去搞搞第二题的后面2个点,高精写不出来,逗逼了1个多小时一分都没有搞到。防流感

 

不过最后还有点时间,我又看了一遍第一题,发现跟我去年的color有点像啊。成功推出正解搞到100分了,有点感动。

 

面试的英语表现不能更逗逼,我自己听了都哭了。话说我不知道回答问题是可以用中文的啊,尼玛还show我那煞笔到爆的英语,我都要落泪了好么。

 

晚上BG了一大波人,烧了3k3,我的钱包有点感动。得去工地搬砖了。

 

总结

两试都是逗逼一样的考试策略和表现,我终归还是不怎么会打OI比赛,主要还是太逗逼,没法看出什么好搞什么不好搞,就这样国内OI生涯就结束了真是悲伤。还有些话就不多说了。

HNOI 2013 题解

题目在这http://pan.baidu.com/share/link?shareid=483357&uk=3104636224

 

简单题解:

一试:

T1:CQOI原题 BZOJ 1306。大概就是简单的搜索,每次搜索一个队伍跟其它所有队伍的战斗情况。然后注意到如果得分为1,2,3的答案跟1,3,2是一样的,这里可以排个序记忆化。然后可以在搜索顺序上加一些优化。

T2:这题目真是。。。首先我们注意到如果选了一个x*y*z的区域,并且x最小,那么y和z显然应该是N。也就是x*N*N的区域,这就等价于选了x个1*N*N的区域,也就是说我们只需要整行整列整层的选就可以了。
但是还是不好做,注意到a*b*c<=5000,那么令a<=b<=c,可以发现a<=17,我们枚举2^17的所有选择,然后就变成了经典的二分图问题,当然复杂度还是很高,不过可以发现可以利用一些字问题的重合来降低复杂度。仔细算算的话可以发现复杂度是可以接受的。

T3:S表示和,可以发现答案就是d=|S|/m取上整。那么字典序也就能处理了,令S[i]=第i天之后的和(不包括第i天),那么第一个位置i要求|S-S[i]|<=d |S[i]|/(m-1)<=d。找出往后满足这个条件的最小i即可。然后一个个找过去。

二试:

T1:比如有4天,x1,x2,x3,x4,令ai=xi+1-xi,
那么答案=Sum_{1<=a1,a2,a3 <=k}(N-a1-a2-a3)。
这个很好计算。
T2:令x_i=i点期望经过了几次,列方程算出。
那么可以根据这个算出每条边期望经过了几次,那么排个序就行。
T3:考虑网络流,
我们构造一个P*Q*(R+1)的点阵,用(i,j,k)表示一个点
那么(i,j,k) -> (i,j,k+1) 的流量为原图中(i,j,k)的不和谐值。
S向所有底层连无穷边,所有顶层向T连无穷边。
那么(i,j,k) -> (i,j,k+1)被割表示f(i,j)=k。。。
同时我们让(i,j,k) -> (i’,j’,k-D)连一条无穷边,就能保证相邻两个不超过D了。

WC酱油记

姆Q >w<,又去WC打酱油了。 Day 0 一大早去机场坐飞机去成都,结果尼玛飞机延误了,好吧我觉得我出门就没碰上飞机不延误过,于是中饭也没吃好不容易上了飞机,坐在我旁边的是个阿拉伯大汉啊!他不但把行李扔在过道上跟空姐争吵,飞到一半的时候他还把鞋子袜子脱了把脚驾到架子上啊尼玛。。。受不了啊233。。。 于是到了成都已经很迟了,晚饭也没吃就坐车去学校,直接就参加开幕式了,尼玛啥奖都没有抽到。回到宾馆中饭晚饭都没吃直接就玩玩电脑睡了。 跟我住在一起的是GY大神,每天都上SC2虐菜,我被吓傻了。职业级玩家太屌了。 Day 1 早上醒过来,那叫一个饿,本来想去听课的结果饿晕过去了,到12点才爬起来吃了点东西去听下午的课了。 已经不想吐槽WC历年的这种讲了就考的神级出题方式了,不过梯形剖分真心不好写,可能理清楚了代码长度也不长,但是一个不熟悉的东西容易出错的地方太多了,计算几何本来又就是这种0 or 100的玩命游戏。我其实在去年ZJOI省选讲课的时候就说过有一个可持久化平衡树的扫描线做法,那个做法虽然空间复杂度是nlogn的,但其实是可以优化到O(n)的。。用当时我也讲到了的一个技巧,不过好久没研究现在已经忘光了233。 晚上是讨论讲题,主席讲了一下合并可持久化线段树,这个idea还是非常有用的,其实这个为什么能优化复杂度?本质上我觉得是利用了更多的信息,线段树的结构相同这点就比平衡树好很多。但是好像大家的注意力都被秀物理的hym大神吸引过去了233。 hym讲了一下如何实现一个2D的物理引擎,炫酷值爆表啊!!!无法直视。 然后又有2个人讲了如何破解某OJ的密码,某人真是,只能呵呵了。 还有人讲斐波那契堆,其实我很想吐槽这不是傻叉数据结构么,代码量都没到3k。 Day 2 然后是第二天早上去听cqx的课,我觉得题目还是很有意思的,不过妈蛋我举了6次手一次都没鸟我是搞毛啊啊啊啊啊,我今年一点印象分都没有刷到好么???要落泪了啊。网络流建模我一直也不是很擅长,所以我也打算在代数化建模上下一点功夫了,不过说到这个我觉得TC以前JZP全场唯一AC的题目的建模就非常帅,贾教的网络流功力确实是屌逼出翔啊。 下午听陈许旻讲浮点误差和误差复杂度,我觉得帅爆了,我基本是完全不会分析误差只能靠感觉乱搞的,科学的分析误差确实很重要啊。 晚上继续是讨论,lyp讲了一下python简介,WC正好出现了可以用python的题目啊,真是太那啥了,dyh成功把花一天才能看懂的东西在0.5h内讲完了,我只听懂了第一个小问题的矩阵加速的解法,然后就瞎了好么! 尼玛在dyh之后讲压力大翻了啊,我瞬间就感觉尼玛我完全是骗0.5分的好么,不过讲完之后主席跟我说这个是可以做到每次操作O(log n)的,我看了一下发现真是炫酷爆了,简单的说就是通过一种标记方法来做的,比如说数据随机的话我们给每个节点一个double的标号,每次让一个新节点的标号为(前面的标号+后面的标号)/2,那么在数据随机的情况下只要比较标号就能确定了,在数据不随机的情况我们可以使用一个很大的标号集合(N^2),在适当的时候进行一些重标号就能做到均摊O(1)的询问两个位置的大小。真是炫酷。 Day 3 早上听lrj讲课,各种神题啊被虐爆了,几何实在太可怕了,感觉以后得找个专修计算机图形学的队友。。。 下午听ayq讲IPSC趣题讨论,还是挺有意思的。 晚上跟超哥打osu。。。笔记本键盘加垃圾鼠标,真是感觉到了残疾人的快感。 Day 4 明天就要考试了,正好是好基友的课就翘光了。宾馆里补觉加颓废。晚上去试了一下机感觉也就这样。 然后就早睡了,好吧根本没有早睡,不知不觉就混到一点了不过没关系反正打比赛只要有咖啡就够了。 EXAM 我感觉我这场比赛的打法真是炫酷啊,我先看了一下题目,觉得前2题都很好做,第三题的数据看了一下感觉高斯消元+CRT可以拿很多分的样子。 我思考了一下觉得第一题不好写,第二题至少70分是很随意的,于是我脑子进翔先写第一题了,写着写着感觉压力好大,不过3h的时候终于过了样例,感觉如果再造数据+拍暴力就没时间了,于是豁出去了,肉眼检查了几遍改了几个错误就放一边了。 然后又写+拍了第二题的70分,只剩下30分钟不到了,用python写了个CRT把所有点都当n=1的做了居然能骗47分。。。尼玛这给分太松了吧。。。 尼玛最后居然AC了第一题太炫酷了,稀里糊涂就217了(为什么不是213)。 闭幕式 闭幕式在一个酒店里举办,我去的太迟只能坐在一个很角落的位置了T_T。 吓傻了本来他们要我反串我赶紧翘掉了。 湖南众上台跳江南Style,尼玛炫酷出翔啊!!!!!lyx跳的叫那一个风骚啊。感觉是专业级的不得不服。 在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起!在一起! 哎。。。我为了骗0.5分去跟学军众唱法海你不懂爱。。。感觉脸都丢光了。。。哭瞎。。。 大家好,我是来自MIT的GYZ。 吐槽: 1.第三题什么都不交都有3分吓傻了,这样都有人故意交错的得0分。。。。我觉得这是一种,对出题人施舍的拒绝!多么高尚的情操啊! 2.压根就没去过食堂,天天去那个广场吃各种各样的好吃的,几天下来花了1k5。。。尼玛屌丝血泪啊。。。我的钱包。。。 3.暴力分给这么多真的大丈夫?虽然听说是因为要发3等奖所以要保证至少有100多个人有分。。。不过至少这本质上是国家队选拔赛的一环应该以选拔活动为主吧,其它人也只是来体验比赛的吧,有种本末倒置的感觉,去年的WC也是这样,虽然去年那样让我这种2B进队了。。。 4.因为爱情!!!!!尼玛帅爆了。。。你们在一起了吗? 5.所以说。。。有妹子挂OI?好吧也不多说了,年度最悲情人物LHM,我依稀还记得上次THU集训的时候你跟妹子打电话show恩爱啊。hym大神秀物理晒基友加了1分最后比LHM高了0.02分第12进队了。 6.标准分这种算法其实也挺坑爹的,很多人进不进队还得看最高分的人考多少。 7.我发现考OI比赛就2点啊!考前喝咖啡和考试的时候写注释卖萌!心态好出翔好么? 8.带了几个人去玩四川的(哗~~),事后大家感觉都很不错啊,真是太赞了。 9.某天晚上拉了个妹子来房间打牌,某屌丝拍了下妹子然后在某群上发照片说在外面跟妹子开房。。。。是有多屌丝???? 10.大学军大南外怒进2个,跪烂了,南外进的都是高二的。。。太可怕了,深刻的感觉到自己已经老出翔了。 11.最后一天晚上大家出去喝酒,我这什么酒量啊妈蛋。。。。。被灌出**了。。。 12.四川的菜也没那么辣嘛,我觉得还凑合啊。 PS:我的WC考场程序>.< 没有做过任何改动,原汁原味的考场程序 >w<。 感谢7k+帮我拷出来 卖萌的注释可以无视>_<。 打了一天游戏,WC酱油记今天补。 第三题由于是提交答案题就呵呵了。。反正就是一个骗分向的python 地址:http://wjmzbmr.com/wp-content/uploads/2013/02/wc-code.zip 百度盘分流:http://pan.baidu.com/share/link?shareid=266353&uk=3104636224

THUSC酱油记

嘛。。。打完了酱油滚粗回家了。。。。。。

总觉得这里气候太干燥根本没法睡。。。每天睡眠时间<=4h。。。基本靠咖啡吊着命尴尬。。。

首先我来的时候。。。我宾馆房间的网线是坏的,厕所门是坏的,马桶是没法冲的,地板是吱吱作响被吓死的。。。宾馆的网速也真是跪出翔。。。是有人在下片么。。。要片问我拷啊sad。。。别这样。。。

Day -1

跟我一起住的是LHM。。。LHM各种gfs。。每天都跟妹子打电话到很晚show恩爱。。。擦。。屌丝一口血喷出来了。。。。。

第一天晚上我为了攒RP。。。就找了点人BG了一顿。。吃的是网易大楼里面的火锅店?钦爷找的地方,他跟我说人均一百,结果尼玛花了8百,钱没带够,还让超哥和炫教gfs垫了200尴尬。。。穷屌丝的钱包瞬间清空了。。。一口血喷出来。。。

超哥GFS越来越帅了。。。听说最近护了很多妹子。。。。

钦爷就更不用说了。。。

zrp嘛就呵呵。。。。你们会懂的,为什么我叫他过来?你们愿意跟四个GFS一起吃饭被D吗??我也不愿意.

炫教听说在被3个妹子倒贴?

然后就开始打酱油了。。。

Day 0

跟LHM住一间房,然后这天的凌晨就开始扯淡,鉴于好久没用嘴巴跟人类说话了,于是扯啊扯啊扯到3点多了。给有妹子的LHM大神跪烂了!

然后这天晚上有DIY群里的人在中科院旁边BG夜宵,来了好多人,于是吃的好爽>_<。白神讲解了如何通过微信之类的把妹。笔记中.

Day 1

由于晚上貌似没开暖气冷的要死…第一天感觉状态挺差的。。

看了题目之后感觉有2题是送分的,于是慢慢写+对拍搞掉了,另外不是很能理解很多人一行的题目都能看错囧-窘迫.比赛时间有4小时啊,又不是比速读,不用那么急吧.

然后看到第一题,感觉是动态凸包(白痴FLAG).然后就脑子进水完全不会直接滚粗了晕.不过数据好像很弱很多人都骗分骗过去了,不过这题数据是挺难搞的.

Day2

第二天喝了点咖啡。。。感觉还行。。。看第三题发现忘了咋反演就乱搞了。。。然后第二题我好像写过建对偶图。。。但是不知为啥写挂了(后来xpd发现数据里有边重合/相交…噗)。。。第一题花了半天做了下结果还被卡时间卡T了(据通过的人说他开了读入优化!吐血了)。。。噗。。。

Day3
早上的时候hym表示要留在北京卖切糕,吓出**了

由于早饭太呵呵了,第三天早起去吃麦当劳…先做了下第一题结果发现要T。。常数优化半天毫无效果。。结果他标程也跑不出来数据里说Q=5w实际上只有1w。。。一口血。。。然后又做出了第三题。。。然后没啥时间了。。。就写了个第二题暴力。。。其实当时脑子进水了。。。感觉正解跟暴力写起来也差不多。。。

似乎很多人看到第三题的题目那么长就直接太长不看了?其实这题本来是要出到NOIP的啊囧-窘迫

晚上xpd高富帅bg大家吃麦当劳,xpd自称带了16w!吓傻了,我们问他如何弄那么多钱,他说是通过卖切糕!尼玛糕富帅真多.

Day4

第四天第一天挺原的。。。我就做掉了。。。然后第二题随便写了个自己感觉很不靠谱的随机骗分。。。第三题脑子进水了不会做就随便骗了点分。。。出题人说随机选点取最优能60但我只有40。。。一口血。。。。哪里写傻了吧。。

晚上跟JZP和QMD一起去玩嫩。。。哦不是是去吃麦当劳。。。。JZP自称能吃掉一个麦乐鸡桶。。。结果最后吃的还没QMD多!!!尼玛自称2个全家桶的战斗力呢????

然后我们又去玩北极。。。哦不是是回宾馆了。。。

然后就滚回去了囧-窘迫。。。给留在北京卖切糕的糕富帅hym跪烂了!

(尼玛飞机要起飞了。。。先这样细节等下再补吧。。。。)//噗。。。似乎延误了。。。

吐槽

1.虽然我弱的跟什么一样为什么还能勉强混的不错呢?我感觉还是比赛经验啊,混了这么多年对OI比赛的坑爹性也是有很大的了解了,所以就比较在意如何在坑爹的OI比赛中保持发挥的稳定性.这方面还是有一些经验的走你.什么先写暴力再写正解啊,感觉发虚就用暴力去跑小分啊,至少得看3遍题目别看错啊balabala.

2.贾教第二天和第三天都没来赛场去玩嫩,哦没啥,事后他对我介绍的嫩,额呵呵还是很满意的嘛.
3.在北京这几天带了1w块过来了,北京的嫩(-哗-),女(-哗-),北极(-哗-)都挺不错的嘛.钱都花光了.

4.上面一条显然是口胡.
5.感觉题目上来说,比去年要难一些的样子,不过也没差多少.
6.其实我是很有节操的,像我这样清廉正直有节操的三好青年满大街都找不到一两个, 我每时每刻都在思考,如何成为一个有操守有修养的好青年为祖国的文化建设作出自己的一份贡献style
7.今年集训队居然有3个妹子.貌似有一个是钦爷的学妹?@王钦石.
8.分数似乎拉的不是很开,跟去年一样的状态的样子,第4跟第22最后就差了10分吧,毕竟WC一场占50分后面还是挺难说的.其实我很想吐槽WC的题目又不怎么靠谱(@各种玩游戏成功得60),分值还这么大.尴尬
9.噗,王教授最后解释了一下为什么不采用IOI赛制,说是因为北航的人担心网络安全的问题,说什么开放网络的话学生之间就可能交流balabala了,你们不是专业的搞出了GFW嘛抠鼻,能和谐国外网站这点小问题都解决不了?

Southern Subregional Programming Contest 2012 hints

做了一下SGU最近的那场比赛,就发个hints骗访问。。。。看了还是不会做也别问我(都说了是骗访问了XD)。。。

  • A:最后x位时要借位的一定是最后x位最小的那些,状态有限就可以dp了。
  • B:傻逼题
  • C:   我们将所有人排序,那么可以dp算出赢了k场的方案数(是赢了k场不是只赢了k场),然后可以用这个反过来推出只赢了k场的方案数。
  • D:我感觉就是一个模拟,需要考虑很多恶心情况。。。暂时没过。。。
  • E: 傻逼题
  • F: 由于王和后之间不能有相领点,所以必然存在一个点删掉之后王和后在不同的连通分量里,然后解决子问题就行了。
  • G:傻逼题
  • H:傻逼题
  • I:使用splay维护子树的dfs序并维护些信息就行了。
  • J:傻逼题
  • K:傻逼题
  • L:傻逼题

 

-->
Page 1 of 5612345...102030...Last »