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中一个点到它的一个子孙)。

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

最近打的几场比赛。。。

上周参加了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。。。。不说啥了。。。>_>。。。。

 

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

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:傻逼题

 

[坑]ACM用模板

大概是个坑。。。我正在填。。。
因为要去HZ赛区打ACM,所以准备一套模板,而且感觉最近太依赖Ctrl C+Ctrl V,很多都不会敲了 :cry:

目前要填的坑有好几个方面,我也打算自己实现并测试一下来复习各个算法。。。

  • 数据结构:splay/treap/LCT/树链剖分/点分治
  • 字符串:suffix array/suffix automaton/最长回文
  • 计算几何:圆交/圆点求切线/圆圆求切线/半平面交/V图/三角剖分/完全动态凸包/3D几何一些初步计算/球面几何/3D凸包/3D半空间交
  • 数值计算:FFT
  • 数论:离散对数
  • 搜索:DLX
  • 图论:sap/dinic/scc/最小费用流/最小树形图/2sat

想到其它的会补充。。。模板就在这里更新。。。。可能会在缩进上做一些调整适合打印用。