CodeForces
…昨天晚上碰到拿数据结构作E的CF- -,就大涨了一把。
然后今天颓然发现…
rating混进了前100
– -太不容易了额.连续3场靠RP进前50…
首先是那场D作数据结构题的…
然后是过了AB + 3个hack居然能混进前50的…
再接着就是这次E作数据结构题的…
。。。
真心觉得都是运气啊…感觉很快要掉回黄的样子…不截图留念可能今后都达不到了…= =|||
曲线图：
———————————————————————————————————————–
这几场ACM组队训练下来、发现自己不太静得下心来…而且有避开麻烦的心理…特别是队友在搞某些比较烦,或者自己不是非常熟悉的题目的时候.就抱有放给队友搞的心理…然后就不管了…于是往往在后面是各种打酱油,浪费时间.
其实能明显感觉到我们3个的想东西的方向差别很大,有时候一个人各种难搞的时候,另一个人可能推推就出来了。
然后无论是ACM组队还是CF…都能感觉自己有点静不下来…可能和最近的小感冒有点关系>.<
希望接下来做事都可以专注一点，投入一点。。。
今天拿了A题的First Blood.
截止3个小时的时候，依然是1个AC，近300个提交
其实开搞这题的时候是很犹豫的。毕竟瞬间n个提交，0AC…于是果断觉得是坑爹题.
YY了一下，得到了个sqrt(n)*Q*t的算法.算了算复杂度非常有压力.
但是想想块状表的常数小到爆了…于是写了个对应复杂度的3重循环试试会不会TLE.结果返回了WA！！！
于是果断开敲，把程序搞了出来.sample调了下..没过= =
然后颓然发现我统计的是他防守住了多少波。点点点点啊
.但是块状表本身不是很熟.不想去改动它
于是瞬间上了树状数组(反正就几行)统计每一位被攻击了几次,把那个减一下就是答案了…
接着感觉没啥好改的了，就交了…看着100+个提交…0AC.看着都胆寒啊- -….然后…就返回了AC
以上扯淡，下面说说我的解法。
【题目地址】http://acm.hdu.edu.cn/showproblem.php?pid=4031
【题解】
首先是对n个格子均匀分块。设每个块的大小为L。
那么对于攻击的操作，我们考虑对每个块设定标记使得整个块的操作能够不搞到底层就可以维护起来。需要的时候再把标记传下去。
可以围观到0<=t<=50。可以考虑在上面作文章。
我的标记是由以下几个东西组成的：
1、int l,r表示块的起始和终结位置
2、int Time 表示这个块内的元素最后一次被打到的时间是什么时候。
3、int F[55],pre[55] 我们可以将块内元素按照 (Time-最后一次被打的时间) 分成t+1([0,t])类。如果超过这个减出来的值超过t的，就可以变成t，因为超过t的无论接下来什么时间来了攻击，都可以抵挡，和等于t的其实是一样的…。分成这t+1类以后，F[i]表示第i类元素将会承受住多少次攻击(= =就是这地方我搞错了，就套了个树状数组，其实可以维护成第i类元素将会被打中多少次)。pre[i]表示第i类元素上一次被打的时候是什么时间。
这样，在攻击操作来临的时候，我们对于整块的，就去更新一下里面的F[55]和pre[55]，对于不是整块的，就直接暴力…
这一步的时间复杂度是O( (n/L)*t + 2*(L+t) )
、
然后对于询问操作，就简单地把标记推下去，然后统计就好了。
这一步时间复杂度O( L )
、
如果粗略地令L=sqrt(n)。那么复杂度就是O(Q*t*sqrt(n))。
现在我们尝试在其中寻找到平衡点。
令(n/L)*t = L得L=sqrt(n*t)
于是第一步时间复杂度(n*t/sqrt(n*t) + sqrt(n*t) ) 就是O(sqrt(n*t))
第二部同样是O(sqrt(n*t))
最终复杂度是O(Q*sqrt(n*t))
程序在218…写得也比较搓…就不发了。。。
By edward_mj@Evzones
参考文档:
http://www.crummy.com/software/BeautifulSoup/
http://www.crummy.com/software/BeautifulSoup/documentation.zh.html
http://www.diveintopython.org/html_processing/index.html
、
、
python爬虫跑Javascript
http://developer.51cto.com/art/201003/190832.htm
好像说py+v8也可以的样子
、
、
一些示例和skill
貌似这博客好久好久没有更新了……为了填这个月解题报告，于是就更新一下吧：
顺便说一句，百度空间的格式控制真是烂到不能忍啊，连表格功能都没有
ZOJ Monthly, August 2011 解题报告
By 猛犸也钻地 @ FutureGazer
首先这是各个题目及AC情况：
————————————————–
Aya Hello, Gensokyo 16.58% (349/2104)
Cirno Fairy Wars 3.11% (9/289)
Flandre Hide and seek 40.00% (2/5)
Mukyu Bookcase 20.84% (251/1204)
Nitori Crazy Shopping 20.00% (5/25)
Remilia Disappearance 12.82% (15/117)
Suika Weekend Party 5.11% (65/1270)
Suwako Shinryaku! Kero Musume 10.98% (20/182)
Yuuka Parterre 16.19% (108/667)
————————————————–
自从 @watashi 拿了冠军当了教练追到了妹纸后就开始了 [del] 骄奢 [/del] 淫逸的生活，所以本次 Touhou 系列题目没有被 shi 哥摸过，真的都是赤裸裸的简单题（误），共有⑨题。好了废话少说，以下是题解：
Problem Aya : Hello, Gensokyo
类型：签名题、构造
题意：幻想乡里 N 位少女，任意 3 位之间最多有两组百合关系（一条无向边），问这 N 位少女之间最多有多少组百合关系。
这题出完后过了几天就发现和 CodeForces 41E 撞车了，本想换一道题，想来想去想不出什么好的 idea，于是就这样挂出来吧，反正也是给人涨自信的题。做法很简单，想一想就可以想出来了：最优解一定是二分图，左边 n/2 个点，右边 (n+1)/2 个点，左右两两之间的边全都连上，这样任取 3 个点，还是满足条件的，而边已经极大了，也可以从 1 个点开始逐步构造地那样去想。
Problem Cirno : Fairy Wars
类型：悲剧的被各种水过去的题、线段树、树状数组
题意：TH 12.8 都玩过吧？给出 N 个子弹，一开始给出一个大圆，把半径 R 内的子弹先冰冻住，然后每个被冰冻住的子弹都会产生一个 L × L 大小的正方形冰块，被冰块碰到的其他子弹也会形成相同大小的冰块并产生连锁反应，问连锁反应结束后有多少颗子弹被冰冻住。
本来不是那么容易过的题，但数据还是悲剧了，有些 N^2 的算法或是一些其他不靠谱算法没能卡住，整理题目时就这题最难搞，折腾了很久的数据。标准解法是 YY 了一阵才想出来的：
将子弹划分进 (L/2) × (L/2) 的网格中，这样每个网格内部的子弹就能够互相冰冻，而一个网格内的子弹是否会冰冻，也只需要检查与之相邻的 8 个网格就行了。于是做法是这样，首先起始的大圆套住了一些子弹，把那些子弹所在的网格加入队列，从队列中依次取出一个网格，让它与相邻的 8 个网格（只需检查相邻的且未被加入过队列的网格就行了），分别地两两算一下内部子弹的最小距离，如果小于等于 L 则把那个相邻的网格也加入队列。两两算距离只需要对网格内的点排个序，用个线段树或树状数组维护一下并扫一遍就行了。
Problem Flandre : Hide and seek
类型：二小姐、大自然、lca、二分、树链剖分
题意：给出一棵树，边有权值表示两点之间的距离，现在有 M 次询问，每次询问会给出一组 A B L，表示如果在 A 和 B 之间新加入一条长度为 L 的边，那么所有点到 A 缩短的距离之和加上所有点到 B 缩短的距离之和为多少？
超难写的题，虽然先 LCA 然后再在树上二分的想法很容易想到，但是真的超难写的有木有！居然还有人真的在比赛时写出来了，太猛了有木有！仰慕楼教主以及 lch 神牛！
方法嘛，首先记 C = LCA(A,B)，然后对于 A B 及向下的点（叶子）和 C 及向上的点（祖先）都很容易计算出结果，难点就在于 A – C – B 这个路径上的点的距离变化（也别忘了它们还有伸展出去的其他子树）。当然，在那个路径上，会有一组点 Ax 和 Ay，在 Ax – Ay 路径上的点到 A 的距离都是缩短的（图像大概是个单峰函数），同样也会有一组 Bx 和 By，为了找这些点，二分吧，树上做二分的方法也有不少，就不多说了。求和的话可以记个前缀和什么的，方法很灵活，用一个能写得出来的就行了。
一开始写标程时没写出来，后来神牛 @edward_mj 用了树链剖分搞定了，代码有 300 行，比赛时楼教主的 LCA 方法也有 250 多行，算法不难想，但就是难写死了，想要 AC 的同学加油写吧！
Problem Mukyu : Bookcase
类型：简单题、lis
题意：有一个 N 层书架，每层 M 本书，现在要将每层的书按 ASCII 码的顺序排序，每次可以取出一本书，插入到同一层某个位置，问最少的移动次数。
模型有些 old，最长不 XX 子序列，能看出来就行了，没留什么 trick，也没刻意卡时限，也不需要无视大小写的字典序排序，很厚道的题（其实我想说，明明就是出题人太懒了）。
Problem Nitori : Crazy Shopping
类型：背包、dag
题意：给出一个有向无环图，每个点卖一种物品，数量无限，问获得最大价值的情况下消耗的体力最少为多少。
不知为何比赛时很少有人过，或许和那密密麻麻一大堆描述有关系，结果大家都无视了这题。解法：拓扑排序一下，然后按照拓扑排序顺序，先在每个点上做无穷背包，然后再沿着边更新到其他点，就行了。
Problem Remilia : Disappearance
类型：线段树
题意：某个迷之生物诱拐了一群少女，已知被诱拐的少女满足 max(B) – min(B) <= LB，max(W) - min(W) <= LW，max(H) - min(H) <= LH，这三个条件，另外每个少女有一个熵值 S，问那个迷之生物通过诱拐少女，最多能获得多少负熵。
这题槽点很多，对吧？顺便说一下，题目名本来叫 The Disappearance of Hakurei Reimu，后来找图时刚好找到了那张图，于是就换主角了。做法是这样的：先按照 B 排序，扫描 B，依次加入或删除相应的少女到一个以 W 排序的集合，对每种 W 集合，再扫一遍，维护一个线段树。每次加入或删除时，在线段树的 H[i] ~ H[i] + LH 这段上加上或删除 S[i]，某个时刻整棵线段树的最小值就是解。
Problem Suika : Weekend Party
类型：if-else、缩点了再dfs
题意：很多人来到博丽神社参加周末聚会，每个人都有各自的兴趣爱好（但在 ACG 范围内），问一种座位安排方式，使得任意一个人，和她相邻的两个人都有共同话题。
两种做法，可以缩点后搜索，或是用 if-else 判断出各种情况，单个兴趣爱好可以缩成一个，但多个兴趣爱好的至少要保留两个以上才行。标程的做法是 if-else，其实想清楚了也不麻烦。
Problem Suwako : Shinryaku! Kero Musume
类型：章鱼形图、dp
题意：给出 N 个点，N 条有向边，在某个点建造神社会获得一定的信仰，但如果这个点有一个有向边指向另外某个建造了神社的地点，那么那个点会失去一定的信仰。问最多能获得多少信仰值。
标题已经是剧透了（乌贼娘第二季期待中），不考虑边的方向，那么图中的每个连通子图都是一个环带上一堆长在环上的树。于是先搞定那些树的部分，从叶子往根dp。然后把剩下的环拆成链（假定某个点上造或不造神社），继续dp一下即可。
Problem Yuuka : Parterre
类型：简单题、暴力
题意：给出一个 N × M 的花坛，花坛是一圈一圈的，每一圈都是特定的一种花。现在给出 Q 次查询，问一个子矩阵，这个矩阵中有多少种花，哪种花最多，有多少个。
正如预计，过的人还是很多的。把每圈拆成四条线段，然后查询时就对最多 4N 条线段暴力做个相交，求出长度即可。另外稍微注意一下，在中心部分可能拆不出那么多线段。
好久没有更新这个地方了。
这段时间嘛，开学之流，发生了很多事。下面乱序随便记记。
//
首先是CF红了。本来感觉要一辈子红不了了呢。集训带来的收获还是很大的。以前那样懒懒散散地切题…实在是比不上这种形式的集训。也许有一天，TC也能红一把吧。
//
另外我们队经历了6场contest。
>.<踩了1队两次，也是RP成分居多。
我们队，怎么说呢…还是在各种磨合吧。出题效率明显是比不上team1的。首先本身队员的实力上有差距，然后感觉我们3个各自的手速也拼不过team1…再最后是机子还是经常空的。至少像fancy那样先敲模板什么的还是完全没有的。我们合力写同一个程序也比较罕见(尝试过两次，成功了一次…)，基本上coding部分是分离的。感觉我们该多看看别人的程序风格吧。可能我写的指针式邻接表看着比较费力.要么大家以后就统一用vector写邻接表算了…
现在我们队大致分工是数据结构和图论等带比较经典东西的就给我；然后ZYC负责几何和各路蘑菇题；vout切各种数学题、dp、乱搞题，Java只有vout会，所以大数vout也包办了。
我们队练习的时候往往会开很多个坑…于是很容易就出现每个人手上都有可搞题的代码，但是都只能自己debug的情况。这时候机器就会各种不够用…感觉这种状况几乎是个必然吧.好像没什么特别好的方法，找另外的人看也不一定比自己debug快.
//
然后是选课…神马都被刷了- -，大英都被刷了。更坑爹的是推荐课表里就没有英语这种东西….
接着的话是advanced data structure这门课擦着一个名额选上了。=_=，考试不坑爹的话…大概会毫无压力吧。
数学分析和线性代数用力吧。
//
军训各种坑爹啊，0_0。10点钟才回到寝室。然后他让你在明天6:30 am前把2~10篇400字的军训文交上去。这还不算什么，关键是那天根本就还没有开始军训，只是开了个动员会而已…
就这样吧。