作者存档：edward_mj

参考文档:

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

 

 

好久没有更新这个地方了。

这段时间嘛，开学之流，发生了很多事。下面乱序随便记记。

//

首先是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字的军训文交上去。这还不算什么，关键是那天根本就还没有开始军训，只是开了个动员会而已…

就这样吧。

看到AClist里面有dzy就知道是网络流 最后还是没想出来 只好找题解了Orz

基础知识

本题题解 其中那个y[i]前面应该是负号 作者打错了

 判无解的时候是不满流 要用流量判 不要用费用判！！！！

膜拜此题Orz

#include

using namespace std;

const int maxn=2000 + 10, maxm=maxn*maxn*2;

 

const int maxl=999999999;

inline int Min(int a,int b){return a

inline int Max(int a,int b){return a>b?a:b;}

struct st

{

         int y,d;

         int ne;

         int bro;

         int f;

} e[maxm];

int ee;

int st[maxn];

int n,m;

void addedge(int x,int y,int d,int f)

{//给顶点x和y间添加一条费用d,流量f的边

         e[ee].y=y;e[ee].d=d;e[ee].ne=st[x];e[ee].f=f;st[x]=ee++;

         e[ee].y=x;e[ee].d=-1*d;e[ee].ne=st[y];e[ee].f=0;st[y]=ee++;

         e[ee-2].bro=ee-1;e[ee-1].bro=ee-2;

}

int d[maxn],p[maxn];

//spfa所用到起点的最短距离(这里距离相当于cost)和路径记录之前的一个节点

int c[maxn];//spfa所用数组:是否在队列中

int que[maxn],head,tail;//spfa专用队列

int flow=0;

int spfa(int sx,int ex,int n)//求sx到ex的一次费用增广

{//如果没有增广路就返回maxl否则返回费用

         int i,j,k;

         for (i=0;i

         memset(c,0,sizeof(c));//初始化都没进

         d[sx]=0;

         que[head=0]=sx;tail=1;

         c[sx]=1;

         while (head!=tail)//spfa开始

         {

                   k=que[head++];head%=maxn;

                   c[k]=0;

                   for (i=st[k];i!=-1;i=e[i].ne) if (e[i].f)

                            if (d[k]+e[i].d

                            {

                                     d[e[i].y]=d[k]+e[i].d;

                                     p[e[i].y]=i;

                                     if (c[e[i].y]==0)

                                     {

                                               c[e[i].y]=1;

                                               if (e[i].d<0){head=(head-1+maxn)%maxn;que[head]=e[i].y;}

                                               else

                                               {que[tail++]=e[i].y;tail%=maxn;}

                                     }

                            }

         }

         if (d[ex]==maxl) return maxl;//如果无法到达终点返回maxl

         k=maxl;

         for (i=ex;i!=sx;i=e[e[p[i]].bro].y)       k=Min(k,e[p[i]].f);//计算流

         for (i=ex;i!=sx;i=e[e[p[i]].bro].y)//增加反向边

         {

                   e[p[i]].f-=k;

                   e[e[p[i]].bro].f+=k;

         }

         flow+=k;

         return d[ex]*k;//返回费用为流大小*路径长度(cost累加)

}

int w[200],sumw[200];

int fa[200];

int ui[maxn],vi[maxn],li[maxn],ci[maxn];

int toto=0;

void init()

{

         int i,j,k;

         scanf("%d",&n);

 

         for (i=1;i

         {

                   scanf("%d%d",&j,&k);

                   fa[j]=k;

                   scanf("%d",w+j);

         }

 

         memset(st,-1,sizeof(st));

         ee=0;

         toto=0;

         scanf("%d",&m);

         for (i=1;i<=m;i++)

                   scanf("%d%d%d%d",ui+i,vi+i,li+i,ci+i);

 

 

         for (j=1;j<=m;j++)

                   addedge(ui[j],vi[j],ci[j],li[j]);

         for (i=2;i<=n;i++)

                   addedge(fa[i],i,0,maxl);

 

         memset(sumw,0,sizeof(sumw));

         for (i=2;i<=n;i++)

                   sumw[fa[i]]+=w[i];

         w[1]=0;

         for (i=1;i<=n;i++)

                   if (sumw[i]

                   {

                            addedge(0,i,0,w[i]-sumw[i]);

                            toto+=w[i]-sumw[i];

                   }

                   else

                            if (sumw[i]>w[i])

                                     addedge(i,n+1,0,sumw[i]-w[i]);

}

int main()

{

         int cass,cas=0;

         for (scanf("%d",&cass);cass–;)

         {

                   cas++;

                   init();

                   printf("Case #%d: ",cas);

                   int cost=0;

                   flow=0;

                   while (1)

                   {

                            int k=spfa(0,n+1,n+2);

                            if (k

                                     cost+=k;

                            else

                                     break;

                   }

                   if (flow

                            puts("-1");

                   else

                            printf("%dn",cost);

         }

         return 0;

}