昨天和刚哥、pyx、rly、vfk、cyb等人一起出去吃朝鲜烤肉。
稍微喝了点酒,回寝室后本来打算继续看看游戏实况的,结果发现居然恰好有场cf,而且似乎不分div1,div2看起来能涨不少的样子。
于是心血来潮熬夜打了codefest16。

cyb:”hhh酒后cf”

鉴于难得写篇post,所以除了题解外,稍微扯扯最近干的事情……

閱讀全文 »

『私は今日も転がります』

由于剩下的final只有计算理论,已半只脚跨入寒假。所以先写一下学期总结吧。
虽然(就算)大部分期末都没有出分。

閱讀全文 »

数学学得太差……
学到现在感觉到现在具体数学的概率期望那一章都没看懂。
作一下笔记。
(其实本篇博文就是cmu 15-859(M)的randomized algorithms的Avrim Blum的01/24/11的notes的翻译。。)
反正就是翻译notes+wiki之类的。。。

閱讀全文 »

在八月的时候就知道九月有网赛了。
然而在9月12的时候才想到找敝校负责竞赛的老师报名。
老师表示已经没有账号了,只能参加后面三场了。
敝校是选择四场里成绩最好的三场取校内排名给晋级现场赛资格的。
“如果你们足够强的话,不打一场完全没问题”。

于是本来打算放弃的。但是晚上的时候突然传来了好消息——因为未知原因多了一个账号,我们可以参赛了。
于是相当于头一天晚上接到参赛通知,第二天就滚过去参赛了。

好久不配vim,完全忘记当时pkusc怎么解决的了。。
然后非常蛋疼地用vim写代码,然后dev c++编译调试。
不谈。

最后三人总共做出来十题。罚时感人,#30,感觉出线无望了。

1001 (contribute by zyh -6)
签到题,拿set模拟就行,但是zyh因为迷之原因wa了6发。

1002(contribute by zyh)
好像暴力bfs就行了。

1003(contribute by zyh)
迷之数学题,非常想让人查oeis,反正我不会,zyh想出来的。

1004
考场上根本没看,不会做。

1005(contribute by foreseeable -3)
标准sb题,语文题,几乎就是做mst,但是我sb,wa了三发。

1006(contribute by fancycoder -9)
卡常数过的,1s时限跑了900ms。
明显是先找出顺时针的最小表示法,再找出逆时针的,然后比较字典序。
rly找的方法是后缀数组,常数比较大。
核心原因还是我忘记那个两个指针扫一扫的线性做法怎么做了。。
卡常数所以-9了。

1007(contribute by foreseeable)
签到题

1008(contribute by foreseeable)
语文题,首先你得读懂题,然后发现这是个二叉排序树的前序遍历,然后还原出这棵树就行了。

1009(contribute by fancycoder -2)
并没有仔细看题,好像是某种背包。

1010(contribute by fancycoder)
裸的lucas+CRT,一开始没仔细看题,以为要高精度。。

1011
没看题,好像要大数分解乱搞。
总之没模板,没做。

1012(contribute by foreseeable)
直接算边(有向)i->j出现在多边形边界的情况对答案的贡献(叉积)。
枚举i,j就是暴力了,优化的话,很容易推出来大概算一下$x_i\times 2^i,x_i/2^i,y_i\times 2^i,y_i/2^i$这四个东西,就能线性时间算了。
虽然是1a,但是我做的速度还是太慢,罚时挺多的。

1013
并没有a掉,这道题是给我做的。
主要是我想错方向了,以及sb地以为暴力能过,结果调了好久的暴力。
然后按我想的方向,想要a掉还得写个点分治。。(不多说)

最后半小时就弃疗了。
实际上这题靠谱点的思考方向,还是能在半小时内写出来的。

靠谱的方向大概就是算F(u,v)=u到v的期望步数(u,v相邻)。
然后对于一个询问,就加上路径上所有涉及的边的F值就行了。
问题在于怎么算F(u,v)。稍微推一下还是很好算的。

(某个结论,f(v)=f(p(v))+2s(v)-1,s(v)是子树大小,f(u)是到根期望步数,不会证明)

总体来说,除了04和11之外,其他题都是很可做的。然而最后我们只出了10题,还是10题垫底。#30感觉出线无望啊。

智商不够,退算法圈保平安了。

许久不打cf,被jbr拉着做了一场。
虽然当天零点半到两点半是cf,而我早上七点半要爬起来参加敝校的开学典礼(虽然个人感觉并没有什么卵用)
但是jbr表示开学之后就要断电了就没机会了。
于是就滚去自习室熬夜了。

閱讀全文 »