分类存档：默认分类

准备出发去帝都了。发个帖攒RP。

go！go！go！

参考文档:

• 20.1. HTMLParser — Simple HTML and XHTML parser
• 20.2. sgmllib — Simple SGML parser
• 20.3. htmllib — A parser for HTML documents
• 21.5. urllib — Open arbitrary resources by URL
• 21.6. urllib2 — extensible library for opening URLs
• 21.7. httplib — HTTP protocol client

• 21.21. cookielib — Cookie handling for HTTP clients
• 21.22. Cookie — HTTP state management

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

http://obmem.info/?p=476

貌似这博客好久好久没有更新了……为了填这个月解题报告，于是就更新一下吧：

顺便说一句，百度空间的格式控制真是烂到不能忍啊，连表格功能都没有

 

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 条线段暴力做个相交，求出长度即可。另外稍微注意一下，在中心部分可能拆不出那么多线段。