RT

RT

RT

(度娘文章过短你妹)

(真是想笑啊,还以为自己很NB,其实就一SB,明年再来吧)

挂了就是挂了,本来想找点什么出毛物理题啊之类的借口,也没什么意思,

嘛,看开了看开了,明年tourist退役了说不定还能混个奖杯什么的(大雾)

我就算了,感觉我很对不起wqs…

xujie纯爷们啊……二试题目太水翻不了盘真是尼玛…

另外cong lich zpl ayq gyz 进队.

话不多说,大家加油.

尽自己最大的努力,不要有遗憾就好了.

http://115.com/file/e77aykwi

这是我hw2的作业.

主要的内容有WC题解,互测自选题题解,两篇自选题解题报告和一个可持久化数据结构的研究报告.

尽管我认真的进行了多次校对,还是可能有错误,请轻D T_T.

LZ先去喝口翔…

(我会说我是骗经验的?)

嘛..集训队互测终于结束了,我就简单的总结一下吧.

首先我感觉现在的OI真心是比谁挂的少,只要做到傻逼题会做,难题骗点分,也不要挂题,就基本能混的很好了.

还有就是心态的问题,我感觉我现在心态非常不错,能进就进,不进打gal去,压力毫无.也许这样的心态才是最重要的吧.

另外就是比赛策略的问题,我感觉我的比赛能力还是不够成熟,还是会发生某题题目耗时过多导致悲剧的情况,一般来说比赛之前都是要计划一下比赛的时候要做些什么的,一开始的时间最好拿来想一下每道题目然后列个能得分的表.

最后就是对拍的问题,我感觉在互测中由于我勤于对拍,所以正确率非常高,对拍的话无论是时间空间正确性都要拍,这个是很关键的.

(本来是想写详细的总结的,残念的是很多比赛的细节给忘光了)

说到稳定性,我统计了大家的标准方差,可以看出gyz的稳定性是最高的,是0.1747,其次是ayq(0.1857),再后面是我(0.1890),最高的是wqs(0.3110)…可以看出wqs的战斗力跟妹子密切相关..

由于详细的写不了了,就换成一些吐槽吧.

1:某校原题团给我送了3个rank1,导致我初期就混的不错,最后那人的比赛最后一题我因为mac和windows下面卡时函数的效果是有差别的!结果一题分数跪光就跪了.

简而言之mac下面CLOCKS_PER_SEC = 100w,但是win下面是1000.

2:似乎流行坑队友,某校大家互相坑的很开心……

3:要自己分高的关键是要么把题目出容易,要么出很高的部分分…

4:某人出神题虐人,由于自己在自己的比赛的分数是平均分/最高分,TA的这项分数就最低了.

5:我总共混了5个rank1,有一场是wqs出糟糕水题赛不算的话,其它4场都是HN的人的比赛…..

有人说我那题的题解过于意识流。。。。

于是我就看了一下。。

发现没有看懂。。。。。

发现没有看懂。。。。。。

于是我来写一个详细的题解。。。

首先，我们倒过来计算空矩形的数量，答案就是 矩形的数量 – 空矩形的数量。

那么，我们按行扫描，每次计算底边在当前行上的空矩形的数量。

那么实际上这个的答案，只跟当前每列，往上能伸展多少有关。

不妨考虑是这样的图形。

让我们考虑如何计算答案。

由于底边已经确定了，那么我们需要选择的就是上边界和左右边界（也就是左上角和右上角）。

继续观察这个图形，划分一下，可以发现它能够看成一个树形结构。

注意到，左上角和右上角，必然都在划分过之后的同一个矩形块中！

设划分出来的矩形宽度为w，高度为h，那么在这个矩形中的答案就是C(w+1,2)*h。

在树的节点中维护它所有子孙的答案和。

由于这个是一个树形结构，我们可以用树来维护，同时因为数据是随机的，故树的高度是logn的，这个可以用随机笛卡尔树高来证明。

接下来我们是在一行行扫描，所以得考虑如何维护。

如果下一行是空的，我们只需要把最下面那个矩形，也就是树的根，的高度+1就行了，同时更新根的答案。

如果下一行中有障碍物。

比如在第c列。

画一下图可以发现，整棵树，被顺着第c列，切成了两部分。

我们只需要在切树的同时，维护树的结构和答案即可。维护的复杂度跟树高是相同的，所以总复杂度就是nlgn。

具体的代码我已发在我的网盘，我自认为写的还是挺可读的。

见我的网盘。。。

没有AK的原因是我的journey的程序写的太暴力。。。。

用了map<pair<int,int> ,int >来构图。。结果给T了。。。。

Problem 1: Ai,Ai+1可以由Ai/2,Ai/2+1推出。递归即可。

Problem 2:我们将所有相邻的3角形间连一条边，容易看出答案是最长链长度+1。

Problem 3:

我们反过来计算所有内部为空的矩形个数。

我们一行行扫描，计算底边在当前行的空矩形个数。

令hc为第c列往上，在碰到障碍或底边之前，有几个空格子。

那么h1,h2,…,hm就决定当前的图。

拿个个图画一下，从最底下往上考虑，可以发现这构成了一个树形结构。

注意到将全体h+1很好实现，将一个h改成0，就意味着把树切成了两部分，由于随机数据，树高是logn的。。

复杂度就是nlogn。

275：

注意到其实只要X,Y能够凑出A和B就行了。。。

那么如果只用X就能凑出A和B，答案显然是-1

否则的话Y的值肯定在1到200之间。。枚举即可。

500：

注意到xor的性质，每一位是独立的，分别计算dp就行了。。。

975：

这个题目是个挺显然的网络流问题。。具体是怎么建图。。

我们讲(a->b)容量c的边，拆成(a->b)容量1，费用正无穷的边，和(a->b)容量c-1，费用1的边。

这样就能保证一条边至少经过一次。

求出这个图的无源汇最大费用流即可。

可以使用消圈算法。

不过要判断一下不连通的情况。。。

A：暴力水题。
B：暴力水题。
A，B具体可参考我CF上的代码。

C：注意到只要两个串长度相等且各个数位的和相等，就可以互相转换，所以简单的dp预处理就能O1询问答案。
D：公式题，http://hi.baidu.com/wjbzbmr/blog/item/5aa2143735bc450391ef3953.html 有证明。

E：我们不妨直接暴力dp，考虑数位d，假设n在d下有len位，那么状态就是(d+1)^len (每位是？或者[0,d-1])，注意到d=2的时候。。状态数非常多，我昨天晚上的想法是固定前几位然后后面再dp，tourist的算法就是这个，我比较弱没写出来。。不过，注意到我们可以一次算很多个素数！比如我们可以计算余2*3*5*7*11的结果。。。。这样再暴力dp。。能卡过。。。

感觉做CF的我和做TC的我不是一个人吧。。。。。。
这战斗力的差别。。。。。。

似乎这是英语阅读能力的胜利？