并查集专题

第09段 冒出之生态圈

1、poj 2236 Wireless Network

本章继续说生物圈二声泪俱下,在封闭运作的第二年吃,8员科学家一直高居忙碌中,不仅要应付杂草、虫害,还要应针对空气成分的浮动。他们几从不吃了饱饭,其中的同个更从二百零八磅骤减至一百五十六称。这致使了成千上万质问的音响,但出于独立的正确顾问委员会递交的告诉肯定了这项试验的意思,起码在封体系的海洋生物地球化学循环和于封闭的生态系统中维系人类生存与生态平衡的知和阅历少面做出了显著贡献。

  题意:一张图上遍布着n台坏了底计算机,并懂得她的坐标。两高修好的微机如果去<=d就好联网,也可以由此其他修好的计算机间接相连。给闹操作“O
x”表示修好x,给来操作“S x y”,请而判断x和y在这儿发生没来连接上。

通过测定,生物圈二号受大量受到氧气的含量由21下挫到了15,相当给处于类似西藏之大海拔地区,为什么氧会消失,消失的氧气去啊了,始终是个未解的谜。但是困扰类似太空舱环境中之微量气体累积问题,在生物圈二如泣如诉受连无存,这片荒原的公共呼吸使中的气氛纯净的飞。

  思路:简单并查集。

生物圈二声泪俱下里的海洋生物就不曾这么幸运了,昆虫几乎灭绝,作为主要粮食的作物也泯灭了5种植,如果没人类的干预,生物圈二哀号颇有或会见如林恩。马基莉斯所言,成为市野草(指生存在人类栖息地附近的动植物)的乐园。想使保持一个种的生存,不仅需要适当的条件,还需大自然的狂野,如惊涛骇浪,如野火燎原,生命需要失控。

5588葡京线路 15588葡京线路 2

“冒出”是依靠一个初鱼缸在涉起初的混杂后,突然稳定下来的光景。生物圈二声泪俱下内的上千种植生物,想如果达标相同种平衡,需要长期的时间,几年或几十年,说不定哪天突然就“冒出”了。而如果一个扑朔迷离的生态系统“冒出”了,就没什么能够为那又倒退返,如同其让这种复杂所引发,人类社会为是这样,而机械而给足够的复杂和灵活性,也产生或同会“冒出”。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<memory.h>
 4 #include<cmath>
 5 using namespace std;
 6 int n, d;
 7 const int maxn = 1200;
 8 int pre[maxn];
 9 struct node
10 {
11     int x;
12     int y;
13 }cpt[maxn];
14 int Find(int x)
15 {
16     int r = x;
17     while (r != pre[r])
18     {
19         r = pre[r];
20     }
21     int i = x, j;
22     while (pre[i] != r)
23     {
24         j = pre[i];
25         pre[i] = r;
26         i = j;
27     }
28     return r;
29 }
30 void Join(int x, int y)
31 {
32     int px = Find(x), py = Find(y);
33     if (px != py) pre[px] = py;
34 }
35 int main()
36 {
37     while (~scanf("%d%d", &n, &d))
38     {
39         for (int i = 1; i <= n; i++) scanf("%d%d", &cpt[i].x, &cpt[i].y);
40         memset(pre, 0, sizeof(pre));
41         char op[3];
42         while (~scanf("%s", op))
43         {
44             if (op[0] == 'O')
45             {
46                 int p;
47                 scanf("%d", &p);
48                 pre[p] = p;
49                 for (int i = 1; i <= n; i++)
50                 {
51                     if (i == p)continue;
52                     double dis = sqrt(1.0*(cpt[i].x - cpt[p].x)*(cpt[i].x - cpt[p].x) + (cpt[i].y - cpt[p].y)*(cpt[i].y - cpt[p].y));
53                     if (dis <= d&&pre[i]!=0)
54                     {
55                         Join(i, p);
56                     }
57                 }
58             }
59             else
60             {
61                 int p, q;
62                 scanf("%d%d", &p, &q);
63                 if (Find(p) != Find(q))printf("FAIL\n");
64                 else printf("SUCCESS\n");
65             }
66         }
67     }
68     return 0;
69 }

生物圈二哀号是生态及技巧的联姻,生机盎然的潜,是轰隆作响的机械及无处不在的控制体系,从中我们可学学如何通过科技去影响和操纵环境,以及生活于里的海洋生物。虽然机器技术通过不断改进和学习,终极会有生命特征,但是也无非是身技术之一个少替代品,生命技术才以凡终端技术。

View Code

生物圈二声泪俱下对科学领域做出了简单单明显的贡献:1、让我们询问封闭体系的海洋生物地球化学循环。2、让我们取得了于封的生态系统中保障人类在和生态平衡的学问和更。重要的得是骚扰对生态的显要!生物圈二如泣如诉丁之一切都是受控的,但是大自然用狂野,需要或多或少零乱。因此,生物圈二声泪俱下丁之人类就变成了骚扰的上帝、混乱的代表。本章第二节介绍了边缘物种,乌鸦、鸽子、老鼠和杂草,它们于世界各地的城市边缘随处可见。而现的世界在吃分裂成一个个底小斑块,因此这些边缘物种得以生存得十分好。它们有时也是花内生态系统一同提高之显要元素。第三节中,作者提到了关乎地球生态的几乎单为主指标:二氧化碳、氧气、碳、氮。这是现行球稳态的主导参考指数。凯文凯利以尾,首不行提出了“冒出”这个词。一个网的平衡态的假冒出,意味着她上了一个稳定期,而无见面随随便便地趋向倒退,仿佛这系统给新的复杂性带来的凝聚力所掀起。因此,一个网是否冒出底一个要害元素,看来就是生足够的扑朔迷离!第四节,凯文凯利引出了技能圈和生物圈的涉及与融合问题,提出了“失控生物学”的概念。

2、poj 1611 The Suspects

生物圈二声泪俱下帮助我们作证了:生命即使是技术,是终点技术。机器技术只不过是身技术之即替代品而已。随着我们针对机器的改善,它们会转换得重新有机,更生物化,更类似生命,因为身是生物之嵩技术。

  题意:有一个该校,有N个学生,编号为0-N-1,现在0如泣如诉学生感染了非典,凡是和0在一个社团的人头就会染上,并且这些人口如果还与了别的社团,他所在的社团照样全部染,求感染的总人口。

第10章节 工业生态学

  思路:并查集,合并的时顺便统计人数。

本章凯文凯利介绍了关联智能建筑、智能家居、物联网等概念。未来,智能传感器以及智能线路或会遍布于室的每个角落,无论是电话、电脑、门铃、烫斗,聪明的房间会自动识别每一个初进来者,包括主人。每当你走上前一个间,这个屋子会明白凡是你,它会将您带来至一个安康的地方,并调光线到合理的档次,它会感知外界的天气,从而自动打开百霜叶窗到适合的菱形。如果您是侵略者,则它会咬你。

5588葡京线路 35588葡京线路 4

若果说,虚拟现实的观点是拿团结在于电脑世界,则未来,你以于电脑的灵气所包围。当这些嵌入式智能的数据特别至自然数量的时刻,它们就机关会形成一个生态系统。你会相信有一个前景的建筑群,会是一个机的联手发展生态系统为?若一切建筑群都能够按照环境而进展适应性变化,那会是什么神奇,既然作为一个“生态系统”来设想,那些“机械生态系统”自然就见面抓住凯文凯利的思量。它们是否如有机生态环境(如:细胞内大量物质在非生长期间开展内循环)那样,内部发生的兼具垃圾都能够循环使用?以缓解工业本身排放污染的题材。由此引出了本章的题目工业生态。这个术语自二十世纪七十年代开始即既使,当时用来考量工作场合的例行和环境问题。工业生态要发展呢网络化的即时生产体系,动态的抵物质流量,使本地多余或短少之素可以持续配送,进而最小化应变库存。

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 30010;
 4 int pre[maxn];
 5 int Cnt[maxn];
 6 int Find(int x)
 7 {
 8     int r = x;
 9     while (r != pre[r])
10     {
11         r = pre[r];
12     }
13     int i = x, j;
14     while (pre[i] != r)
15     {
16         j = pre[i];
17         pre[i] = r;
18         i = j;
19     }
20     return r;
21 }
22 void Join(int x, int y)
23 {
24     int fx = Find(x), fy = Find(y);
25     if (fx != fy) pre[fx] = fy,Cnt[fy]+=Cnt[fx];
26 }
27 int main()
28 {
29     int n, m;
30     while (~scanf("%d%d", &n, &m))
31     {
32         for (int i = 0; i <= n; i++) pre[i] = i,Cnt[i]=1;
33         if (n == 0 && m == 0)break;
34         for (int i = 0; i < m; i++)
35         {
36             int k;
37             scanf("%d", &k);
38             int pre, now;
39             for (int i = 0; i < k; i++)
40             {
41                 int x;
42                 scanf("%d", &x);
43                 if (i == 0) pre = now = x;
44                 else
45                 {
46                     now = x;
47                     Join(now, pre);
48                     pre = now;
49                 }
50             }
51         }
52         //int cnt = 0;
53         //for (int i = 0; i < n; i++)
54         //{
55         //    if (Find(i) == Find(0)) cnt++;
56         //}
57         printf("%d\n", Cnt[Find(0)]);
58     }
59     return 0;
60 }

对接下是凯文凯利自己观点的阐发,工业生态既是讨论什么“更不过持续性发展”,那么,遍布人身周的适应技术,如:分布式智能、弹性时计算、生态位经济,以及教导式进化,都会引起机器中的有机性。这里的有机性,就是副自然生物之集团的道。它的前提是,事物组成的错综复杂已经达标了生物级别。凯文凯利写及:“自然是掌控复杂性的大师傅,在处理杂乱、反直观的网方面吃我们坐无价的带。”

View Code

在本章最后,认为生一个年代的特点是新生物学而无是仿生学,因为他觉得生物学终会胜出。凯文凯利说“生物学之所以总是凌驾,是为有机并无意味着神圣。它不用生命体通过某种神秘方式传承下来的崇高状态。生物学是一个势必,近于数学之早晚,所有复杂归向的大势所趋。它是一个欧米茄点。在自发和人工缓慢的杂过程遭到,有机是平等种植显性性状,而机械是隐性性状。最终,获胜的总是生物逻辑。”至此,凯文凯利将当之道以助长到了一个初的可观。

3、hdu 1213 How Many Tables

第11章 网络经济学

  题意:两独人口如互相认识,则为在相同张桌子上。问需有些张桌子。

凯文凯利以本章开头就引入了虚拟现实、赛博空间的概念。难以想象,早以达标世纪80年代,他即使发了如此超前的想象力,凯文凯利的首先大计算机是苹果电脑,他这么描述:“我管其联结到电话线上,从此得到了一样种宗教般的感受。”他当场意识及,计算机的未来休以数字,而介于统一!他说他生了千篇一律种醍醐灌顶般的顿悟,是的,有了统一,才出信息。如果说,信息的熵和物理学的熵是何其相似,那么为统一而发出的音爆炸,对斯世界之含义是匪夷所思的。

  思路:并查集,合并的时更新剩余连通块。

凯文凯利是一个可怜出预见性的口,在描绘这仍之年代,互联网才提高快,他就开描述一个“纯网络化”的小卖部之特征,并以为当下是鹏程之来头。分布式,公司运作不在凡于单纯地点运行。最合理的化解方案是整合成八到十二单人口之集团,放在同样地方展开。他们可为看做一个柜之细胞,每个细胞都是因为同样于丁构成。去中心化,如果仅仅发十个人,怎样才能完成一个周边的计划?凯文凯利的结论:一个百分百网络化的公司,只待一个办公室就能够包容下该颇具的专业人士,通过网技术同其他的独立团队相统一。凯文凯利这里谈话的便是“外包”和“众包”的定义。协作性,将其中工作网络化具有重大的经济意义。“公司这概念,会起那种紧耦合、被严格自律之有机体,变成一种植松散耦合、松散约束之生态系统。”适应性,这里凯文凯利已经好起远见卓识的相,从成品到劳动之变换是无可避免的!因为复制的老本越来越低。而信息以及学识密集型的足在。“要想在初的一代挣到钱,你得从信息的流。”

5588葡京线路 55588葡京线路 6

一个网就是一个音讯的加工厂。当一个出品之价值就中所蕴含的学识之加而滋长时,产生这些知识之网络其价吧跟着大增。凯文凯利提到了网络化企业之“容错性”问题。在一个至上复杂的系网里,如何自发的树类似人体“免疫系统”的其中容错、纠错机制!凯文凯利看,网络式经济的前程,在于设计出可靠的流水线,而无是牢靠的制品。而网络经济的真相意味着这种流程是不可能太优化的。只有时时刻刻地趋近于满意,而且这种满意吗只好维持好紧缺的瞬间。

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 1010;
 4 int pre[maxn];
 5 int cnt;
 6 int Find(int x)
 7 {
 8     int r = x;
 9     while (r != pre[r])
10     {
11         r = pre[r];
12     }
13     int i = x, j;
14     while (pre[i] != r)
15     {
16         j = pre[i];
17         pre[i] = r;
18         i = j;
19     }
20     return r;
21 }
22 void Join(int x, int y)
23 {
24     int fx = Find(x), fy = Find(y);
25     if (fx != fy) pre[fx] = fy, cnt--;
26 }
27 int main()
28 {
29     int t;
30     scanf("%d", &t);
31     while (t--)
32     {
33         int n, m;
34         scanf("%d%d", &n, &m);
35         cnt = n;
36         for (int i = 1; i <= n; i++) pre[i] = i;
37         for (int i = 0; i < m; i++)
38         {
39             int x, y;
40             scanf("%d%d", &x, &y);
41             Join(x, y);
42         }
43         printf("%d\n", cnt);
44     }
45     return 0;
46 }

在末一略节,凯文凯利做了一部分有关网络经济的下结论。有几乎接触端都涉嫌了,这里他增加了瞬间几个:1、拥有者得的,先到吧得之;2、公司及买主,最终“共同前进”;3、以知识为根基。最终,他干了关于网络知识中会涌现出同种植“全球意识”的可能。“我们人类将不能得知这种全球意识在思念啊。因为发现本身就是不容许该部分会懂整体。”

View Code

第12章 电子货币

4、hdu 3038 How Many Answers Are
Wrong

立马同章节凯文凯利进一步分析了网络的简单单场景,数字加密和虚拟现实。一方面是政府,他们要求得有的数额,要求全面的公开化;另一方面试要隐私权和公民自由。而倾向似乎是“加密永胜”,就如印刷术削弱了负世纪行会的权,改变了社会权力结构,这是凯文凯利援引了蒂姆梅的说教。在一个坐分布式方式有的物,没有控制中心,也几乎没清晰的分界,如何护?民间自发的密码朋克组织,1992年的秋起出现,那个时刻,这样的小组还就当座谈在线买卖的声体系问题,简直是不可思议。凯文凯利看,加密技术实际上是经济学!因为加密有该急需,但出本。

  题意:给您M个区间和,问您来几个凡是跟前矛盾的。

传真机效应,也就是说这个世界上各国多同贵传真机,每个人手里的传真机就越是有价。这即是网世界杰出的进项递增定律。多会带动双重多,网络经济奖励那些比多吧,而未是那些比较少啊,凯文凯利这里其实说了网络世界“免费”、“开放”的真面目,这跟爱心没有涉及

  思路:带权并查集,利用并查集形成集合树,利用sum数组记录集合树中即节点i到根本中的界限的权值和,如果手上少只节点不在平棵集合树中,那么通过简单单集聚树合并,调整权值,使能够确保合法的,所以仅待联合,将一律蔸树的根变为其他一样株树之一干二净的子节点,然后建边,因为f[i]<i,i<j,f[j]<j,所以s=sum[j]+sum[f[j]]-sum[i]因目前j的彻底是f[j],所以一旦抬高新加之边权,那么新的边权既可以经这个方程求取即可。

正确,在联网的信世界,信息要之便是随便的流动与为复制,没有加锁和约束。在一个由去中心化的节点组成的纱世界面临,成功属于那些符合信息复制和流动主张的人头。

5588葡京线路 75588葡京线路 8

以12.5,凯文凯利总结了几触及数字货币对网络经济的蜂群思维的重点影响:加快的商品流通速度,如同paypal,支付宝这样的老三着电子支付,包括网上银行的模式,大大加快了本交易的效用与运作。

 1 //利用并查集形成集合树,利用sum数组记录集合树中当前节点i到根之间的边的权值和,如果当前两个节点不在同一棵集合树中,那么通过两个集合树合并,调整权值,使能够保证合法的,所以只需要合并,将一棵树的根变为另一棵树的根的子节点,然后建边,因为f[i]<i,i<j,f[j]<j,所以s=sum[j]+sum[f[j]]-sum[i]因为当前j的根是f[j],所以要加上新加的边权,那么新的边权既可以通过这个方程求取即可
 2 #include<stdio.h>
 3 #define MAXN 200010
 4 int f[MAXN], r[MAXN];
 5 int find(int x)
 6 {
 7     if (x == f[x])
 8         return f[x];
 9     int t = find(f[x]);
10     r[x] = r[x] + r[f[x]];//这里首先要对这个递归的过程很了解,当递归到某一层时,x还未接到根节点上,所以r[x]表示的是x到f[x]的距离,经上一步操作,f[x]已经接到根节点上了,所以r[f[x]]表示的是父节点到根节点的距离所以x到根节点的距离就直接等于r[x]+r[f[x]]
11     f[x] = t;
12     return f[x];
13 }
14 int fun(int x, int y)
15 {
16     if (x>y)
17         return x - y;
18     else y - x;
19 }
20 int Union(int x, int y, int sum)
21 {//传进来时x<y
22     int a = find(x);
23     int b = find(y);
24     if (a == b)
25     {
26         if (fun(r[x], r[y]) == sum)
27             return 0;
28         else return 1;
29     }
30     else
31     {
32         f[a] = b;
33         r[a] = r[y] + sum - r[x];//r[y]表示y到b的距离,r[x]表示x到a的距离,sum表示x到y的距离,现在要将a接到b后面,那么r[a]很表示a到b的距离,很明显就是这个式子了   
34         return 0;
35     }
36 }
37 int main()
38 {
39     int n, m, i, ans, a, b, s;
40     while (scanf("%d %d", &n, &m) != EOF)
41     {
42         ans = 0;
43         for (i = 0; i <= n; i++)
44         {
45             f[i] = i;
46             r[i] = 0;
47         }
48         for (i = 1; i <= m; i++)
49         {
50             scanf("%d %d %d", &a, &b, &s);
51             a--;//左区间减一,方便处理
52             if (Union(a, b, s))
53                 ans++;
54         }
55         printf("%d\n", ans);
56     }
57     return 0;
58 }

连续性,电子货币成为连年流。

View Code

绝互换性,脱离了实体,使得交易的对象变得离奇。

5、poj 1182 食物链

可达性,当经济进入数字一代,按分钟截止利息都成可能。

  题意:有  3  种动物,互相吃与受吃,现在报你  m  句话,其中有真有假,叫你认清假的个数  (  如果前方没有跟时讲话冲突之,即认为那为心声  )。每句话开始还发出三独数 D A B,当D = 1常,表示A 和B是同类,当D = 2时表示A 吃 B。

大势,电子货币的方便性,让它成为个人货币的出色候选!

  思路:带权并查集。

当真,电子货币是出这么的可能性,但是本人认为可能不生,毕竟哈耶克的写《货币的非国家化》只是市面派经济学家的一模一样种植想象,或者说想实验。12段结尾,凯文凯以很优质的中原阴阳来写这种涉及:“网络是阳,密码分子就是是晴到多云,一种植微小隐蔽的力量,能够驯服去中心、分布式的体系掀起的爆炸性的互联结。”

5588葡京线路 95588葡京线路 10

第13节 上帝之戏

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 50010;
 4 int n,k;
 5 int pre[maxn], r[maxn];
 6 //根据“x与p[x]能否确定两者之间的关系”来划分,若能确定x与p[x]的关系,则它们同属一个集合。
 7 //p[x]表示x的根结点。r[x]表示p[x]与x的关系。r[x] == 0 表示p[x]与x同类;1表示p[x]吃x;2表示x吃p[x]。
 8 void Init()
 9 {
10     for (int i = 0; i <= n; i++)
11     {
12         pre[i] = i;
13         r[i] = 0;
14     }
15 }
16 
17 //每次通过儿子对父亲的关系,父亲对爷爷的关系,得到儿子对爷爷的关系
18 int Find(int x)
19 {
20     if (pre[x] == x) return x;
21     else
22     {
23         int fa = pre[x];
24         pre[x] = Find(fa);
25         r[x] = (r[x] + r[fa]) % 3;
26         return pre[x];
27     }
28 }
29 
30 bool Union(int x, int y, int d)
31 {//d=1:x和y是同类;d=2,x吃y
32     int rx = Find(x), ry = Find(y);
33     if (rx == ry)return true;
34     else
35     {
36         pre[ry] = rx;
37         r[ry] = (r[x] - r[y] + 2 + d) % 3;
38         //r[ry]=(3-r[y]+(d-1)+r[x])%3(可推)
39         return false;
40     }
41 }
42 
43 int main()
44 {
45     scanf("%d%d", &n, &k);
46     Init();
47     int cnt = 0;
48     while (k--)
49     {
50         int d, x, y;
51         scanf("%d%d%d", &d, &x, &y);
52         if (x > n || y > n) cnt++;
53         else
54         {
55             bool same = Union(x, y, d);
56             if (same)
57             {
58                 if (d == 1)
59                 {
60                     //D == 1 表示X与Y为同类,而从r[X] != r[Y]可以推出 X 与 Y 不同类。矛盾。
61                     if (r[x] != r[y])
62                     {
63                         cnt++;
64                     }
65                 }
66                 else
67                 {
68                     if ((r[y] + 3 - r[x]) % 3 != 1)
69                     {//(X 与Y为同类)或者 r[X] == ( r[Y] + 1 ) % 3 (Y吃X )则此话为假。
70                         cnt++;
71                     }
72                 }
73             }
74         }
75     }
76     printf("%d\n", cnt);
77     return 0;
78 }

13章节,凯文凯利带我们上了他大时代之玩耍。如《铁路大亨》、《文明》、《模拟城市》等。确实,20世纪末,当个人电脑刚开头流行时,电脑游戏是得让您带来“灵魂诱惑”般的抓住。凯文凯利所说:它创造了一个属我们团结一心之社会风气。它被你沉浸在角色扮演中,越是好的嬉戏,内部的算法越是繁复和逼真,就像《模拟城市》竟然利用了都会动力学模型。有时候,不得不怀念,编一个游戏,某种程度就是在开创一个社会风气。而强尼.威尔逊就是人云亦云系列游戏之创作者。

View Code

13.4节里,凯文凯利提到了MIT的传媒实验室Media
Lab,这是当年虚拟现实的先锋。在凯文凯利写是开前,他就是看了红的媒体实验室主管尼古拉斯尼格洛庞帝,它事关了他们十分时候研究之一个术,就是视频压缩,现在无论是DVD,还是蓝光,还是数字摄像机、IPTV等,都用到了视频压缩算法。凯文凯利写电脑游戏,写电脑游戏的创造者,写电脑仿真,其实是有深意的,他提的一个题目是,如何使于电脑游戏本身,具有创造性?的确,自由意志与创造性,带来一个怒放要不论是界定的社会风气。就比如咱人类,可以计划一个团结下。

6、poj 1417 True Liars(并查集+DP)

凯文凯利在本章最后之那句很美:“绝对的决定也就算是绝对的无趣。要想生有新的、出乎意料的、真正不同之事物,也就是真给祥和惊讶之东西,你就算必须放弃自己说了算一切的王位,让位于那些底层的全员”

  题意:给出p1+p2个人,其中p1单凡是好人,p2只是禽兽。然后出一对关联
,a说b是老实人(坏人).其中没有矛盾的,判断是否有唯一破判断哪些人是老实人,哪些人是坏人。其中于重要之凡,好人总说真话,坏人总说假话。

第14段 在样式之图书馆中

  思路:

本章接续及等同段的终极:想只要赢,先放手!的话题。也是于立无异节开,凯文凯利开始上及“生命”这个主题,进行再深入一些之探索。开篇第一微节,凯文凯利引入了有名的阿根廷著名诗人作家,博尔赫斯所管理之图书馆。以博尔赫斯的巴别塔图书馆为原型。凯文凯利将什么当一个庞然大物的图书馆里寻相同本书的点子,引申出一个比方。什么是方式?凯文凯利说,方法就是是咱就一切是怎么样吃创造出的。若图书馆是“书”的或空间,那么是世界还有巨旁的“可能空间”。这里的主导问题是,如何被电脑体系协调能积极去追究这些恐怕空间里之不为人知形态?需要怎么样的算法和当之志?

  ①一个丁说其他一个总人口是好人,那么要是人是老实人,说明
对方真的是老实人,如果这是坏人,说明及时词话是假的,对方吗是禽兽。

第二节,凯文凯利说到让SUN收购(SUN现已为ORACLE收购),创办于1982年,1994年砸的思机器公司。这家企业诞生之挺年代,是人造智能技术飞速腾飞的一世。它们当1993年不过光辉灿烂的随时,建造了红的连接机5,它的创建人是卡尔
西姆斯。凯文凯利说到,“方法,也就是提高,可以让当作是繁殖,而无是旅行。”这里,第一糟糕开始波及一个要之天地,人工进化!

  ②假如一个丁说其他一个总人口是禽兽,那么要此人口是老实人,说明对方是坏人,如果这个是禽兽,说明
对方是好人。

人造进化从有意义及,就是统筹相同种植计算机的自读自进化的算法,让它和谐繁殖自己!至于繁殖的目标,可以是鸽子,也可是图像!这是全人类在追近乎自然的平栽方式!当卡尔.西姆斯看CM5上用灰色的杂点繁育成生机勃勃的植物生命时,感叹“进化之创造力是无穷的。它能够超越人类自身之统筹能力。”是的,当电脑的先后,通过自己的这些算法,创造出奇异的“生物形象”、“艺术图像”时,令这之浩大设计者崩溃!那个时段的次很多或用BASIC语言编写的。

为就算是使条件是yes说明及时半独凡是同一集合的,否则是少单不同之聚众。用r[i]意味着i结点与根结点的涉,0吗平集合,1呢不同集合。

有些艺术家,用基因决定的理念跟发育规则,扩展出了相同仿基因工程学,来规划现代法图案,那些图案超乎艺术家想象!由此可见,基因在系提高、人工生命里之显要位置!这个世界,尤其在纺织业的图画设计里,获得了尽量的展示!目前,很多当代艺术家,利用人工进化技术涉及的著述,也处于法律之真空带。

由此并查集,可以以享有人数分为多只聚众,其中对于各一个聚集,又分为两单聚众(好人和歹徒,但是不了解怎么样是好人,哪些是禽兽,我们惟有相对关系)

利用计算机探索未知形态库,会创有部分神奇的初东西。也许我们人类曾经习惯了咱所在的大自然环境,其实,作为生物的多样性相,是用不完的!凯文凯利在第5节里,提到:“自然之美就有让物种进化之历程里,存在于形式必须结束完全都地契合生物的志这样一个重中之重事实中。”第5节省KK还留一个疑团,复杂性究竟凭借的凡啊?

用dp[i][j]意味着前i个集聚中好人为j的种数,如果dp[cnt][p1]!=1说明方案免唯,或者无解。belong[i][0]代表i属于哪个好类,belong[i][1]表示i属于该大类的啦一个小类,choose[i]相反推找来选择的大集合i的个别像样中是啊一样近似,然后升序输出好人之号码。

第6节里,凯文凯利介绍了人工生命类游戏的先辈。编写俄罗斯四方游戏出名的作者,开发之一个“电子鱼”作品,由同充分批判俄罗斯数学系的人编写。每条鱼都蕴含几十只基因,八百独参数,让游戏用户等去拉、交配、繁殖,还足以经过网络交换鱼卵!

5588葡京线路 115588葡京线路 12

本章最后一省,KK说到一个大重要的一个观点:“当找空间足够大时,有效之寻流程便是与真正的创建并无二致了。”所以,思维是大脑内设法的升华为?是否具备创造物都是发展出来的?写一本书,一篇稿子,后面的各个一个单词,都是同差大脑的搜索。所以,某种意义上,写一本书,就是进化来一致本书也?

  1 #include<iostream>
  2 using namespace std;
  3 int n, p1, p2;
  4 const int maxn = 1100;
  5 int pre[maxn];//i的父亲
  6 int r[maxn];//i和pre[i]的关系
  7 //0:同类;1:不同类
  8 
  9 bool vis[maxn];
 10 
 11 int cntnum[maxn][2];//cntnum[i][j]表示把第i个集合分成两个部分的人数
 12 
 13 int dp[maxn][310];//dp[i][j]表示前i个集合中好人为j的种数
 14 
 15 int belong[maxn][2];//belong[i][0]表示i属于哪个大类,belong[i][1]表示i属于该大类的哪一个小类(对应cntnum)
 16 int id[maxn];
 17 //根据孩子与父亲,父亲与祖父之间的关系可以推出孩子与祖父的关系
 18 int Find(int x)
 19 {
 20     if (pre[x] == x) return x;
 21     else
 22     {
 23         int fa = pre[x];
 24         pre[x] = Find(fa);
 25         r[x] = r[x] ^ r[fa];
 26         return pre[x];
 27     }
 28 }
 29 
 30 void Union(int x, int y, int k)
 31 {
 32     int rx = Find(x), ry = Find(y);
 33     if (rx != ry)
 34     {
 35         pre[rx] = ry;
 36         r[rx] = (r[x] - r[y] + 2 + k) % 2;
 37     }
 38 }
 39 
 40 void Init()
 41 {
 42     for (int i = 0; i <= p1 + p2; i++)
 43     {
 44         pre[i] = i;
 45         r[i] = 0;
 46     }
 47 }
 48 int main()
 49 {
 50     while (~scanf("%d%d%d", &n, &p1, &p2))
 51     {
 52         if (n == 0 && p1 == 0 && p2 == 0) break;
 53         Init();
 54         char s[5];
 55         int a, b, k;
 56         for (int i = 0; i < n; i++)
 57         {
 58             scanf("%d%d%s", &a, &b, s);
 59             if (s[0] == 'y') k = 0;
 60             else k = 1;
 61             Union(a, b, k);
 62         }
 63         //处理完后,得到若干个集合,每个集合中两两同类或不同类
 64         //2:找到有多少个大集合,每个大集合中同类及不同类的个数
 65         memset(vis, 0, sizeof(vis));
 66         memset(cntnum, 0, sizeof(cntnum));
 67         memset(belong, 0, sizeof(belong));
 68 
 69         int cnt = 0;
 70         for (int i = 1; i <= p1 + p2; i++)
 71         {
 72             if (!vis[i])
 73             {
 74                 cnt++;
 75                 int f = Find(i);
 76                 id[f] = cnt;//对每个大集合的根进行分类
 77                 for (int j = i; j <= p1 + p2; j++)
 78                 {
 79                     if (Find(j) == f)
 80                     {
 81                         vis[j] = true;
 82                         cntnum[cnt][r[j]]++;
 83                         belong[j][0] = cnt;
 84                         belong[j][1] = r[j];
 85                     }
 86                 }
 87             }
 88         }
 89         //DP
 90         memset(dp, 0, sizeof(dp));
 91         dp[0][0] = 1;
 92         for (int i = 1; i <= cnt; i++)
 93         {
 94             for (int j = p1; j >= 0; j--)
 95             {
 96                 if (j - cntnum[i][0] >= 0 && dp[i - 1][j - cntnum[i][0]] > 0)
 97                 {
 98                     dp[i][j] += dp[i - 1][j - cntnum[i][0]];
 99                 }
100                 if (j - cntnum[i][1] >= 0 && dp[i - 1][j - cntnum[i][1]] > 0)
101                 {
102                     dp[i][j] += dp[i - 1][j - cntnum[i][1]];
103                 }
104             }
105         }
106 
107         //输出
108         if (dp[cnt][p1] != 1) printf("no\n");
109         else
110         {
111             int choose[maxn];//倒推找出选择的大集合的两类中是哪一类
112             int totalpeople = p1;
113             for (int i = cnt; i >= 1; --i)
114             {
115                 if (dp[i][totalpeople] == dp[i - 1][totalpeople - cntnum[i][0]])
116                 {
117                     choose[i] = 0;
118                     totalpeople -= cntnum[i][0];
119                 }
120                 else if (dp[i][totalpeople] == dp[i - 1][totalpeople - cntnum[i][1]])
121                 {
122                     choose[i] = 1;
123                     totalpeople -= cntnum[i][1];
124                 }
125             }
126 
127             for (int i = 1; i <= p1 + p2; i++)
128             {
129                 int fa = Find(i);
130                 int set_id = id[fa];
131                 if (belong[i][0] == set_id&&belong[i][1] == choose[set_id])
132                 {
133                     printf("%d\n", i);
134                 }
135             }
136             printf("end\n");
137         }
138     }
139     return 0;
140 }

第15章人工进化

View Code

持续上章,本章开始确实的上探索关于“进化”的神秘之地。似乎多的生命科学家都是于相大自然的体悟着,获得灵感。第一节约的主要人物是汤姆雷,一员生态学家,他在观察蚂蚁、鸟、蝴蝶彼此关系之进程遭到,被如此理所当然形成的错综复杂系统所伏,他写道:“那是当哥斯达黎加的热带雨林。行军蚁们吞噬着该提高道路及的具有动物,把同丛飞虫赶得慌不择路。一栽鸟类逐渐形成了跟随这掠食大军的惯,愉快的分享那些以空中四散奔逃的虫儿。而这些飞鸟的身后,蝴蝶而接踵而至。她们享用着这些鸟类的便‘大用’-那是产所欲的氮的自。”后来外编了名叫也Tierra的微机人工生命模型如果走红。

7、poj 1456 Supermarket

当雷还是哈弗本科生时,他的先生就是是美国显赫一时的昆虫和生物学家艾德华威尔森。他着重研究对象就是是蚂蚁,尤其是蚂蚁通过弗洛蒙开展报道的编制。他吃1975年勾勒的《社会生物学:新的归纳》是社会生物学这同样世界的重要著作。

  题意:有N件商品,分别叫闹商品之价跟行销的末尾期限,只要以终极日期前销售处,就会取相应的赢利,并且销售该商品需要1龙时间。问销售的最为老利润。

彼基本就是当,社会表现是提高之结果,并对准斯开展研究暨认证。从任何一个角度看,任何一样种复杂气象,都是有那变异的轨迹,而未是轻而易举。汤姆雷的Tierra系统里,还发现一个场面,进化的进程中,寄生虫不可避免!这不啻是人命之大属性!在一个扑朔迷离世界里,希望不劳而获的个人,会自衍生出来,而且永无止境。

  思路:先管所有成品以利润由老及稍微排序,假要一个出品a占用了一个日期后,那么只要下次又发出一个产品b和产品a的收日期是如出一辙的,但是充分日期为给占用了,所以将为前面挪动1天,那么即使可为此连查集进行标记,在a占用了异常日期后,把a的扫尾日期指向前一个日子,这样的话,可以一直找到他如占有到啦一个时刻。

次省,凯文凯利继续介绍雷的Tierra系统的有的神奇之处。例如:如何当一个几万叫作患儿的临床记录档案库里,找来一个超人患者的症状。此时,进化者软件会针对极端可怜多数病人的无限普遍的病史进行优化。它尝试为出同样称呼杰出患者的骨干描述,然后检查来些许患者可当下卖描述,再指向病历进行多维度改进,看看是否生重多患者跟的可,然后修改、选择、再修改,直至最充分数目之患儿可这卖描述。

5588葡京线路 135588葡京线路 14

其三节里,凯文凯利引出了遗传算法之大约翰霍兰德,他是扑朔迷离理论与非线性科学的前驱。与汤姆.雷的算法不同,霍兰德的遗传算法从性入手,让到配起重点意图,而陡变成了幕后策划者。通过以交配和突变了合在一起,系统转换得活且大。霍兰德在算法中,还大方之施用了彼此机制,这成为绕了随机变异所固有之笨和盲目的重要途径。每个智者,无论后来凡何等巨大,在外年轻时犹见面发启蒙者的存在。可能是一个人口,或是一本书。对霍兰德影响最为充分之同本书,是1953年,他张底费希尔为1929年写的《自然选择的遗传理论》凯文凯利写到:“达尔文带领了打对海洋生物之私有研究及种群研究之转发,而将种群思维转变吗定量科学的是费希尔。”霍兰德从费希尔的题,开始察觉及数学运算可以对生命进化进行有含义的模仿,也领会到了费希尔关于提高是一样栽概率的洞见。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int n;
 5 const int maxn = 10010;
 6 const int maxt = 10010;
 7 struct node
 8 {
 9     int pi;
10     int di;
11 }goods[maxn];
12 
13 int pre[maxt];
14 int Find(int x)
15 {
16     int r = x;
17     while (r != pre[r])
18     {
19         r = pre[r];
20     }
21     int i = x, j;
22     while (pre[i] != r)
23     {
24         j = pre[i];
25         pre[i] = r;
26         i = j;
27     }
28     return r;
29 }
30 
31 void Union(int x, int y)
32 {
33     int fx = Find(x), fy = Find(y);
34     if (fx != fy)
35     {
36         if (fx < fy) pre[fy] = fx;
37         else pre[fx] = fy;
38     }
39 }
40 
41 
42 void Init()
43 {
44     for (int i = 0; i <maxt; i++)
45     {
46         pre[i] = i;
47     }
48 }
49 bool Cmp(const node&a, const node&b)
50 {
51     if (a.pi == b.pi)return a.di > b.di;
52     else return a.pi > b.pi;
53 }
54 int main()
55 {
56     while (~scanf("%d", &n))
57     {
58         Init();
59         for (int i = 0; i < n; i++)
60         {
61             scanf("%d%d", &goods[i].pi, &goods[i].di);
62         }
63         sort(goods, goods + n, Cmp);
64 
65         int sum = 0;
66         
67         for (int i = 0; i < n; i++)
68         {
69             int tt = goods[i].di;
70             int ff = Find(tt);
71             if (ff > 0)
72             {
73                 Union(ff, ff - 1);
74                 sum += goods[i].pi;
75             }
76         }
77         printf("%d\n", sum);
78     }
79     return 0;
80 }

第四节,凯文凯利说到了人工智能进化过程被之连接主义。即:希望经过海量连接着涌现出秩序。从彼此连接的笨节点受到孕育出集团,而凯文凯利的题材是,这样的纱中究竟发生了呀?这是人造进化者们还当摸着连接主义的梦想。他们感叹,并行计算机纵使再强,也无法同天地之彼此速度比。

View Code

凯文凯利坚信,如此“野”的进化,是好吃开的!是一律种能够给随机转发为电脑代码的自然而然的技巧,他说:“在富兰克林之后二百年,人工转的而是开和可度量的闪电通过电线被导入建筑物与工具,成为社会更是数字社会面临极其紧要的团伙能力。在二百年晚,可开和可度量的人为适应吧将给导入各种机械设备,成为我们社会之严重性组织能力。”

8、poj 1703 Parity game

凯文凯利随后举例了最主要用于新药研发的定向分子进化,列举了一些企业,比如达尔文分子公司,没悟出该专利具有人是其余一样员复杂性研究之前沿人物,斯图尔特.考夫曼。

  题意:有一个尺寸就知晓的01失误,给出[l,r]这个距离中之1凡奇数独还是突发性数个,给出同文山会海语句子提问前几独凡是无可非议的。

定向进化与当发展之一个最老不同是,选择压力是出于丁来控制的,而未是自然。从某种意义上说,定向进化是任何一样种植监督式学习,选择由培育者引导。

  思路:将[l,r]以此区间变成(l-1,r],那么1的个数就可以象征也sum[r]-sum[l-1],也尽管规定了奇偶性,我们好用r[]数组表示这端点到她的干净节点的1底奇偶(这个区间就是(i,root(i)](0代表偶,1意味诧异)
 对于每个输入的距离,我们寻找它们的到底节点是否同样。

第7省开场,就事关了鼎鼎大名的原贝尔实验室,它有着的1800大抵个专利是震慑总体人类的!艾克利是所里神经网络和遗传算法的研究员。艾克利有感想很风趣:“对个体而言最好的,对物种而言也休必然。”这是同样词古老的生态学格言。“我们折腾不亮堂从长远看到底什么才是极致好的,这点吃人口甚麻烦接受,但是自己思,嘿,这虽是身!”什么时是对准生吧,“最愚蠢、最孤陋寡闻的师资”,艾克利说,答案就是是“死亡”。

         
①要是同,证明这区间的奇偶性在前面就查出,那么直接判断即可

死是前进中唯一的导师。所以,一个小卖部里,员工一直未创新,就用去发展的动力!下面是本章比较关键的一个论点:“在富有可能的盘算和学习的上空被,自然选择占据了一个奇异的职位,它是一个顶,在这点达,信息传送给顶小化。它成了习与智能的低基线:基线之下不会见生学产生,基线至上则会有更智能、更加复杂的念。”这个看法,让我本着本来选择的于生命本身,突然有了崭新的理念!

         
②使差,那么即便是u-1与v此时未以跟一个成团中,则统一时更新r[].

进步和读书之不二法门有过多栽,但任哪种政策,如齐一致章所说,都是于开展查找。看到这里,脑袋里猝然闪过,每一样次于软件或者网站的本子升级,是否就是是体现了扳平栽“进化”?凯文凯利在这同节约末段提到了微机程序的迈入和本发展之分。也不怕:拉马克进化得于电脑世界里存在,因为电脑代码兼任了基因和躯体两单角色;但当发展受困于化学物质,受困于一致长条严格的数学定律:求多单质数的积容易,但分解质因素则好困难。补充解释一下拉马克进化,它的骨干理念是:获得性遗传和用上废退,认为生物在诞生后,为适应环境的扭转或许来变异,而且这种变异可以遗传给后人。

5588葡京线路 155588葡京线路 16

第8节省,凯文凯利提到了蚂蚁算法。一个蚂蚁军团,智愚而不知测量,视短而不跟展望,却会迅速找到过崎岖路面的太短路径。的确,蚁群就是一个并行处理机!生态的相互作用就是相互的卓绝优化技术。多细胞生物本质上便是在自然界5588葡京线路极上运行大规模的相代码。进化能够想发出我们到底尽一生为无从想掌握的互动编程,进化是无与伦比当的编程方式。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int n, m;
 5 const int maxn = 5050;
 6 int pre[maxn];
 7 int val[maxn];
 8 struct node
 9 {
10     int ll;
11     int rr;
12     int d;
13 }qry[maxn];
14 int Map[maxn * 2];
15 int Find(int x)
16 {
17     if (x == pre[x]) return x;
18     else
19     {
20         int fa = pre[x];
21         pre[x] = Find(fa);
22         val[x] = (val[x] + val[fa]) % 2;
23         return pre[x];
24     }
25 }
26 bool Union(int x, int y, int v)
27 {//x<y
28     int rx = Find(x), ry = Find(y);
29     if (rx == ry) return true;
30     else
31     {
32         if (rx < ry)
33         {
34             pre[ry] = rx;
35             val[ry] = (val[x] + v - val[y] + 2) % 2;
36         }
37         else
38         {
39             pre[rx] = ry;
40             val[rx] = (val[y] - v - val[x] + 2) % 2;
41         }
42         return false;
43     }
44 }
45 int main()
46 {
47     while (~scanf("%d", &n))
48     {
49         scanf("%d", &m);
50         int l, r, v;
51         char s[6];
52         int cnt = 0;
53         for (int i = 0; i < m; i++)
54         {
55             scanf("%d%d%s", &l, &r, s);
56             l = l - 1;
57             if (s[0] == 'e') v = 0;
58             else v = 1;
59             qry[i].ll = l, qry[i].rr = r, qry[i].d = v;
60             Map[cnt++] = l;
61             Map[cnt++] = r;
62         }
63         //离散化
64         sort(Map, Map + cnt);
65         cnt = unique(Map, Map + cnt) - Map;
66         for (int i = 0; i <= cnt; i++)
67         {
68             pre[i] = i;
69             val[i] = 0;
70         }
71         int ans = 0;
72         for (int i = 0; i < m; i++)
73         {
74             l = lower_bound(Map, Map + cnt, qry[i].ll) - Map;
75             r = lower_bound(Map, Map + cnt, qry[i].rr) - Map;
76             v = qry[i].d;
77             if (Union(l, r, v))
78             {
79                 if ((val[r] - val[l] + 2) % 2 != v)
80                 {
81                     break;
82                 }
83 
84             }
85             ans++;
86         }
87         printf("%d\n", ans);
88     }
89     return 0;
90 }

全章最后一省,凯文凯利提到了软件生物学和活力计算的课题。只有不断的剖析自己之情景,修正自己的代码以适应新的需要,净化自己,不断的破除异常情况,并保障适应和进步,程序才会生活。而人工进化是唯一会使软件保持生机和生命力的不二法门。

View Code

若是发展的代价就是是失控。“生存在是世界里,需要或多或少歪曲、松弛、更多适应力和再次少精确度的姿态。”
“这即是发展之贸易。我们放弃控制而赢得力量。对咱们这些实践着被决定的兵来说,这同样于魔鬼的市。”

9、poj 1984 Navigation Nightmare

第16回决定的勃兴

  题意:图及产生有庄,村庄里为此只能借助于东南西北的来头的道路连接,村庄只能放在道路的两岸。询问了至第I个曾经了解条件时某片只村子内的曼哈顿距离。

本章,凯文凯利带我们进来电影动画人物的社会风气。为什么会及控制的前景有关呢?因为,当今的动画电影人物,已经上了数字时代,里面的全3D动画角色,并无是依靠手画的,所有的动作,都是由于计算机完成。这里产生涉嫌到角色智能的操纵问题!所以,控制的前途,也是人为智能的前景。

  思路:先根据道路设出每个点之坐标,然后要某已掌握条件现已知晓,则统一。询问时判断两只村庄是否以与一个连通块即可。

先是节省,凯文凯利就引出了有名的工业魔光公司,由《星球大战》著名导演,乔治卢卡斯给1975年创建。变形金刚3、钢铁侠、加勒比海盗,都应用了她的特技制作!你无法想像,这样的同贱电影特效设计企业,里面用了汪洋的生物学的数学模型。里面的设计师发现,用微机仿造一个活物的极品艺术是种植它。就是统筹一个数字种子,然后被它起发育。这是于生物学中提炼出来的生长法则。

5588葡京线路 175588葡京线路 18

乔布斯1986年,用1千万美元购回了工业魔光公司的微机动画部门,成立了名牌的皮克斯公司。2006年,被迪斯尼以七十四亿美元收购。皮克斯最著名的平等仍《玩具总动员》,相信大家都看罢,3000万美元的动画片制作费,票房也越三亿五千万美元。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<vector>
  4 using namespace std;
  5 int n, m,k;
  6 const int maxn = 40050;
  7 const int maxm = 40050;
  8 const int maxk = 10050;
  9 struct qry
 10 {
 11     int t;
 12     int f1;
 13     int f2;
 14     int id;
 15 }qrys[maxk];
 16 int ans[maxk];
 17 
 18 struct stp
 19 {
 20     int f1;
 21     int f2;
 22     stp(int ff1 = 0, int ff2 = 0) :f1(ff1), f2(ff2)
 23     {
 24     }
 25 };
 26 vector<stp>stps;
 27 struct pt
 28 {
 29     int x;
 30     int y;
 31 }points[maxn];
 32 bool Cmp1(const qry&a, const qry&b)
 33 {
 34     return a.t < b.t;
 35 }
 36 
 37 int pre[maxn];
 38 int Find(int x)
 39 {
 40     if (pre[x] == x) return x;
 41     else
 42     {
 43         int fa = pre[x];
 44         pre[x] = Find(fa);
 45         return pre[x];
 46     }
 47 }
 48 bool Union(int x, int y)
 49 {
 50     int fx = Find(x), fy = Find(y);
 51     if (fx == fy) return true;
 52     else
 53     {
 54         pre[fx] = fy;
 55         return false;
 56     }
 57 }
 58 struct node
 59 {
 60     int to;
 61     char dir;
 62     int len;
 63     node(int tt=0,char c=0,int ll=0):to(tt),dir(c),len(ll){ }
 64 };
 65 vector<node>mp[maxn];
 66 bool vis[maxn];
 67 void DFS(int r)
 68 {
 69 
 70     int sz = mp[r].size();
 71     for (int i = 0; i < sz; i++)
 72     {
 73         int tx = points[r].x, ty = points[r].y;
 74         int v = mp[r][i].to, length = mp[r][i].len;
 75         if (vis[v])continue;
 76         switch (mp[r][i].dir)
 77         {
 78         case 'N':tx -= length;
 79             break;
 80         case 'E': ty += length;
 81             break;
 82         case 'S':tx += length;
 83             break;
 84         case 'W':ty -= length;
 85             break;
 86         }
 87         points[v].x = tx, points[v].y = ty;
 88         vis[v] = true;
 89         DFS(v);
 90     }
 91 }
 92 
 93 int main()
 94 {
 95     while (~scanf("%d%d", &n, &m))
 96     {
 97         for (int i = 0; i <= n; i++) mp[i].clear();
 98         stps.clear();
 99         for (int i = 1; i <= m; i++)
100         {
101             int u, v, l;
102             char op[10];
103             scanf("%d%d%d%s", &u, &v, &l,op);
104             mp[u].push_back(node(v, op[0], l));
105             char nc;
106             switch (op[0])
107             {
108             case 'N':
109                 nc = 'S';
110                 break;
111             case 'S':
112                 nc = 'N';
113                 break;
114             case 'E':
115                 nc = 'W';
116                 break;
117             case 'W':
118                 nc = 'E';
119                 break;
120             }
121             mp[v].push_back(node(u, nc, l));
122             stps.push_back(stp(u, v));
123         }
124         memset(vis, 0, sizeof(vis));
125         for (int i = 0; i <= n; i++)
126         {
127             if (mp[i].size())
128             {
129                 points[i].x = 0, points[i].y = 0;
130                 vis[i] = true;
131                 DFS(i);
132                 break;
133             }
134         }
135         scanf("%d", &k);
136         for (int i = 0; i < k; i++)
137         {
138             scanf("%d%d%d",&qrys[i].f1, &qrys[i].f2, &qrys[i].t);
139             qrys[i].id = i + 1;
140         }
141         sort(qrys, qrys + k, Cmp1);
142 
143         for (int i = 0; i <= n; i++) pre[i] = i;
144         int nowstep = 0;
145         for (int i = 0; i < k; i++)
146         {
147             int t = qrys[i].t;
148             for (; nowstep < t; nowstep++)
149             {
150                 int f1 = stps[nowstep].f1;
151                 int f2 = stps[nowstep].f2;
152                 Union(f1, f2);
153             }
154             int x = qrys[i].f1, y = qrys[i].f2;
155             int fx = Find(x), fy = Find(y);
156             if (fx != fy)
157             {
158                 ans[qrys[i].id] = -1;
159             }
160             else ans[qrys[i].id] = abs(points[x].x - points[y].x) + abs(points[x].y - points[y].y);
161         }
162         for (int i = 1; i <= k; i++)
163         {
164             printf("%d\n", ans[i]);
165         }
166     }
167     return 0;
168 }

返回主题,如何用微机模拟生物,涉及到作为套架构,其主导是去中心化这样的一个首要概念。著名的荷兰裔英国动物行为学家,尼克.丁伯根,在那个1951年底佳作《昆虫研究》中指出,动物行为是一个夺中心化协同。其核心思想是,外在表现是于犬牙交错的组成部分“代理”(简单输入输出模块)的组成中涌现出的。由于表现源头的分布式特性,底层最简便易行的代理也克以上层有预想之外的错综复杂行为。若用这些模块网络图用计算机来做,相当给逻辑流程图,所以得出的定论是:行为是好电脑化的!在是小圈子,当时MIT的媒体实验室是倒以世界之战线!派蒂.梅斯与桑迪.蓬特兰德既然电脑的拟成可能。

View Code

生一个主题谈到了当下于支配研究之一个前沿领域:怎样当未剥夺人工生命角色自由的气象下,给她设定某种结局?于是,控制研究之这种前沿思路也转移了故事情节作者们的写对象。“我们正在开创平等种植了两样之物。我所创造的免是故事,而是一个世界。我创建的是平栽质地,而无是角色之间的对话同动作。”这是前景动画电影的的确模式。而真正神奇的是,未来底人为虚拟角色,还具有从读能力。很多人不见面想到,著名的米老鼠会是人工虚拟角色的先辈之一。在KK写书的一时,2001年,数字化米老鼠已经得以伪装在一个2G底移动硬盘里。而起1997年过后,就重新为绝非丁去用手画米老鼠了。而且这个数字化的米奇,具有学习模块,经过5年地读,米奇曾开有温馨的呼吁了。此时,这个编造米奇的虚构人格,已经不可分割,就同心理学一样。而到了2007年,米奇都是一个相当对的杜撰演员了,有深强的幽默感。而且,他永世不见面要命,也永远不会见老。

10、hdu 1829 A Bug’s Life

米奇对如此同样止具有友好灵魂的虚拟米奇,它曾经失控了。虽然会间接的接受我们的熏陶以及点,但现已离了咱的主宰。对于这么的干,凯文凯利举了一个放的事例:当我们放一丛羊之时节,我们懂得好无享有了的上流,但我们也休想全凭控制。所以,当你可以当虚拟世界放牧众多人工生命时,是多么怪诞的行!

  题意:给一定一名目繁多数对准,例如a和b,表示a和b不是同一种植性别,然后连的被有这么的频繁对,问有没有发生抵触的状况。

本章最后一节约,凯文凯利以放一歌词的根基及,找到了再近乎他意的词协同控制。并引出了本章的一个意见:控制的未来是:伙伴关系,协同控制,人机混合控制。所有这些还代表,创造者必须跟外的创造物共同共享控制权,而且要同呼吸共命运。“伙伴关系、协同控制”是否好采用被店集团的保管规划里为?在“管控”和“活力”之间,获得一致种平衡。

  思路:带权并查集。

第17回生命之定义

5588葡京线路 195588葡京线路 20

随即是不行得天独厚的平章,因为深入探讨了身的定义,以及人工生命。这无异于段里,凯文凯利重点描述的少个人士:约翰霍兰同朗顿,也是《复杂》一书里的台柱。可呈现这无异于章节以及复杂性科学的不衰关系。开篇,凯文凯利从蜜蜂的蜂群行为,引入针对生之开放性的思想。

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 2100;
 4 int pre[maxn];
 5 int r[maxn];
 6 int n, m;
 7 void Init()
 8 {
 9     for (int i = 0; i <= n; i++)
10     {
11         pre[i] = i;
12         r[i] = 0;
13     }
14 }
15 int Find(int x)
16 {
17     if (pre[x] == x)return x;
18     else
19     {
20         int fa = pre[x];
21         pre[x] = Find(fa);
22         r[x] = r[x] ^ r[fa];
23         return pre[x];
24     }
25 }
26 
27 bool Join(int x, int y)
28 {
29     int fx = Find(x), fy = Find(y);
30     if (fx == fy)return true;
31     else
32     {
33         pre[fx] = fy;
34         r[fx] = r[x] ^ r[y] ^ 1;
35         return false;
36     }
37 }
38 int main()
39 {
40     int t;
41     int Case = 1;
42     scanf("%d", &t);
43     while (t--)
44     {
45         scanf("%d%d", &n, &m);
46         Init();
47         bool flag = true;
48         while (m--)
49         {
50             int u, v;
51             scanf("%d%d", &u, &v);
52             if (!flag)continue;
53             if (Join(u, v))
54             {
55                 if (r[u] ^ r[v] != 1)
56                 {
57                     flag = false;
58                 }
59             }
60         }
61         if (flag) printf("Scenario #%d:\nNo suspicious bugs found!\n\n", Case++);
62         else printf("Scenario #%d:\nSuspicious bugs found!\n\n", Case++);
63     }
64     return 0;
65 }

宇宙用会起令人震惊的多样性,是坐其当本质上是开的。生命的性状之一是她见面不断开展自己之生存空间。开放之基因组带来开放的提高。慢慢开始,科学家等要由此计算机来学生命!第3节开业,凯文凯利介绍了一个主要人士,约翰.科扎,他是约翰.霍兰德的学生,也是将霍兰德的遗传算法发扬光大的要人物。1990、1994、1998年,他分别写了重要著作《遗传编程》三本。科扎在《遗传编程》中写道:“问题之求解过程可重表达也以或是的计算机程序中搜寻最适合之么计算机程序。”人工生命的研究成果表明,逻辑程序是好由此渐进式改良进化的。“这就是软件编程的前程。定义一个问题,机器便能够在程序员打高尔夫球的时段找到解决方案。”科扎的次序世界经过发展得的代码,复杂得像只有外星人才会看明白,但效率的确大。人类审美里的大概去了哪?科扎看:“大自然并无见面只是为了优雅而简化。”的确,人类追求类似牛顿F=ma那么简单的公式,但以必然规模内,无论是大自然还是并行计算机,都非会见也复杂性的逻辑发愁。那些我们觉得既难看又于丁头晕的的附加步骤,它们能坐令人乏味的精确度运行是。

View Code

如何才会被电脑自行完成任务,而不必一步步告诉她该做呀以及怎么开?科扎的答案就是是:进化。进化而无论是有无发意义;它才关注无不管事。适应是对本人结构的掉,以要的能够研究了一个初漏洞。而进步是再老层次之更动,它改变的凡构建结构本身的架构。进化不仅是优化。我们领略进化能超越优化并创建新东西来加以优化。目前我们所知道唯一一光可持续自我更新的机,就是咱们大脑的灰质。

11、poj 2912 Rochambeau

第5省,凯文凯利说到,进化作为同种植工具,特别适用于以下三起事:如何到您想去要与此同时找不交程的领域,如何到你无法想像的天地,如何开辟新的圈子,而生物之进化,正是同栽这样放之腾飞!很多生物学家的对象,就是能启动一个进步系统,让分子自己学会如何复制自身。之后,自发进化就用替定向进化。

  题意:有N个人玩剪刀石头布,其中有私房是裁判,其他人分为3组。
这3组中每个组分别发生剪刀,石头和散布。 裁判可以肆意出3只遭之一个。
现在出M个回合,每个回合从N个人被随机选出两单人口来娱乐,并叫有结果。
要求输出最早找来裁判的回合数,以及裁判的号码。还有可能无法确定。

第6稍稍节里,克里斯.朗顿是人工生命之大,是一个满神奇经历之总人口。年轻时的异,酷爱滑翔机,有同一次吃狂风袭击,从半空落下,折断了三十五根骨头。后来半年里,他都处在半昏迷状态。在重脑震荡恢复过程遭到,朗顿感觉到外恰好羁押在自己的大脑在还开。记得他大脑深层的效益一个衔接一个之重现。他吧同一栽大庭广众的发自内心深处的直觉所感动。他见面告知您,关于心智形成是什么感觉。

  思路:利用并查集建立起相对关系,枚举裁判是呀一个,对发生异介入的合不予处理,如果以他无与的合中冒出了矛盾,那么是人肯定就无是裁判。

朗顿大四的毕业论文写的凡《文化之前进》。对客感动非常大地是冯.诺依曼的元胞自动机,这吗多亏集智俱乐部前阵子读书会的要害内容!朗顿集团的1987年首先暨世界人工生命大会是生里程碑式意义的!在这次专题讨论会上,朗顿开始追求生命的概念!其中,有个物理学家,多恩.法默提了一个范围生命之特色列表,那就是日以及空间及之能力自我复制的力量,自我表征(基因)的信息库使特征持久的新陈代谢功能,功能相互—它不用无所事事,彼此互依赖,或能死亡,在乱中维系安静之力,进化的力,某种程度上,计算机病毒是首例涌现出的人工生命。

5588葡京线路 215588葡京线路 22

要是朗顿对人工生命的定义是:“从不同之素材形式被提生命逻辑的尝尝。”
“生命是一个经过–是免为特别材料表现形式限制的行为。”
“生命是一个动词,不是名词。”朗顿给好之使命,就是造产生另外一样种植甚至是几乎种不同款式之生,以此作为真正的生物学的依据,推导出生命本原的笃定逻辑。

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 510;
 4 const int maxm = 2010;
 5 int n, m;
 6 int pre[maxn];
 7 int r[maxn];//0:平局;1:pre[x]赢了x;2:x赢了pre[x]
 8 void Init()
 9 {
10     for (int i = 0; i <= n; i++)
11     {
12         pre[i] = i;
13         r[i] = 0;
14     }
15 }
16 struct stp
17 {
18     int u;
19     int v;
20     int d;
21 }stps[maxm];
22 
23 int ok[maxn];
24 
25 int Find(int x)
26 {
27     if (pre[x] == x)return x;
28     else
29     {
30         int fa = pre[x];
31         pre[x] = Find(fa);
32         r[x] = (r[x] + r[fa]) % 3;
33         return pre[x];
34     }
35 }
36 bool Union(int x, int y,int d)
37 {
38     int fx = Find(x), fy = Find(y);
39     if (fx == fy)return true;
40     else
41     {
42         pre[fx] = fy;
43         r[fx] = (3 - r[x] + d + r[y]) % 3;
44         return false;
45     }
46 }
47 int main()
48 {
49     while (~scanf("%d%d", &n, &m))
50     {
51         for (int i = 0; i < m; i++)
52         {
53             int u, v,d;
54             char c;
55             scanf("%d%c%d", &u, &c, &v);
56             if (c == '=')d = 0;
57             else if (c == '<') d = 1;
58             else d = 2;
59             stps[i].u = u, stps[i].v=v, stps[i].d=d;
60         }
61         memset(ok, 0, sizeof(ok));
62         for (int i = 0; i < n; i++)
63         {
64             Init();
65             for (int j = 0; j < m; j++)
66             {
67                 if (stps[j].u == i || stps[j].v == i)continue;
68                 if (Union(stps[j].u, stps[j].v, stps[j].d))
69                 {
70                     if ((r[stps[j].u]+3-r[stps[j].v]) % 3 != stps[j].d)
71                     {
72                         ok[i] = j + 1;
73                         break;
74                     }
75                 }
76             }
77         }
78         int cnt = 0,rline=0,judgeperson=0;
79         for (int i = 0; i < n; i++)
80         {
81             if (ok[i]== 0)
82             {
83                 cnt++;
84                 judgeperson = i;
85             }
86             if (ok[i] > rline) rline = ok[i];
87         }
88         if (cnt == 0)printf("Impossible\n");
89         else if (cnt == 1)printf("Player %d can be determined to be the judge after %d lines\n",judgeperson,rline);
90         else printf("Can not determine\n");
91     }
92     return 0;
93 }

“人工生命相当于是合成生物学的履。”激励朗顿进行追究之,是摹写出有或有的身空间的期盼,是把我们携带那个非常广阔的“如该或有的命”领域的重任,发现持有抵制热力学第二定律的东西、过去和前程中会太进化之种种物质结合!

View Code

“目前,普通的微机程序可能出一千行长,能运作几分钟。而制人工生命的目的是要是找到同样栽计算机代码,它才出几行长,却能运行一千年。”朗顿以闻名遐迩的《人工生命:即将到来之迈入》中写道:“其他形式的命—人造生命—正准备来到这个世界。它们于使用自家来繁衍和贯彻它。” “本世纪中叶,人类都收获了摧毁生命之能力,而到本世纪末期,人类用会享有创造生命的能力。压在咱们肩膀的即刻点儿抱重担中,很难说哪一样可更致命。”

12、hdu 1272 小希的迷宫

凯文凯利写《失控》的辰是当达标世纪90年份初,现在已经通过21世纪之头十年,也许人工生命领域的开展并未像朗顿预期的那么,美国基因组研究先锋克莱格·文特和外的钻研组织今年制造产生了一个细菌的基因组,并将那个植入一个细胞内,他们创造了世界上篇个人工合成的生命结构。

  题意:如果产生一个通道连过渡了房间A和B,那么既好由此它们打房间A走至房间B,也得经过其于房间B走及房间A,为了增进难度,小希希望任意两只屋子有且只有发生雷同漫漫路可以相通(除非移动了回头路)。小希现在拿她底计划性图被你,让您拉判断其的设计图是否顺应她底统筹思路。

此世界,当一个聪明伶俐能清醒的打听自己,并越自己的时段,那便是当真由无中生有,进入了生生不息的级差了。

  思路:并查集。

5588葡京线路 235588葡京线路 24

 1 #include<algorithm>
 2 using namespace std;
 3 const int maxn = 100010;
 4 int pre[maxn];
 5 bool vis[maxn];
 6 int Find(int x)
 7 {
 8     if (pre[x] == x)return x;
 9     else
10     {
11         int fa = pre[x];
12         pre[x] = Find(fa);
13         return pre[x];
14     }
15 }
16 
17 bool Union(int x, int y)
18 {
19     int fx = Find(x), fy = Find(y);
20     if (fx == fy)return true;
21     else
22     {
23         pre[fx] = fy;
24         return false;
25     }
26 }
27 int main()
28 {
29     int u, v;
30     while (~scanf("%d%d", &u, &v))
31     {
32         if (u == -1 && v == -1)break;
33         if (u == 0 && v == 0)
34         {
35             printf("Yes\n");
36             continue;
37         }
38         for (int i = 0; i < maxn; i++)pre[i] = i;
39         bool flag = true;
40         do
41         {
42             if (!flag)continue;
43             if (Union(u, v))
44             {
45                 flag = false;
46             }
47         } while (scanf("%d%d", &u, &v) && u != 0 && v != 0);
48         if (!flag) printf("No\n");
49         else
50         {
51             memset(vis, 0, sizeof(vis));
52             int cnt = 0;
53             for (int i = 0; i < maxn; i++)
54             {
55                 if (pre[i] == i)continue;
56                 int f = Find(i);
57                 if (!vis[f])
58                 {
59                     cnt++;
60                     vis[f] = true;
61                 }
62             }
63             if (cnt == 1) printf("Yes\n");//只能有一个连通块
64             else printf("No\n");
65         }
66     }
67     return 0;
68 }

View Code

13、poj 1308 Is It A Tree

  题意:输入数据表示存在父子节点关系的接触之号码,判断是否为培育。

  思路:并查集。

5588葡京线路 255588葡京线路 26

 1 #include<algorithm>
 2 using namespace std;
 3 const int maxn = 100010;
 4 int pre[maxn];
 5 bool vis[maxn];
 6 int Find(int x)
 7 {
 8     if (pre[x] == x)return x;
 9     else
10     {
11         int fa = pre[x];
12         pre[x] = Find(fa);
13         return pre[x];
14     }
15 }
16 
17 bool Union(int x, int y)
18 {
19     int fx = Find(x), fy = Find(y);
20     if (fx == fy)return true;
21     else
22     {
23         pre[fx] = fy;
24         return false;
25     }
26 }
27 int main()
28 {
29     int u, v;
30     int Case = 1;
31     while (~scanf("%d%d", &u, &v))
32     {
33         if (u<0 && v <0)break;
34         if (u == 0 && v == 0)
35         {
36             printf("Case %d is a tree.\n",Case++);
37             continue;
38         }
39         for (int i = 0; i < maxn; i++)pre[i] = i;
40         bool flag = true;
41         do
42         {
43             if (!flag)continue;
44             if (Union(u, v))
45             {
46                 flag = false;
47             }
48         } while (scanf("%d%d", &u, &v) && u != 0 && v != 0);
49         if (!flag) printf("Case %d is not a tree.\n",Case++);
50         else
51         {
52             memset(vis, 0, sizeof(vis));
53             int cnt = 0;
54             for (int i = 0; i < maxn; i++)
55             {
56                 if (pre[i] == i)continue;
57                 int f = Find(i);
58                 if (!vis[f])
59                 {
60                     cnt++;
61                     vis[f] = true;
62                 }
63             }
64             if (cnt == 1) printf("Case %d is a tree.\n", Case++);//只能有一个连通块
65             else printf("Case %d is not a tree.\n",Case++);
66         }
67     }
68     return 0;
69 }

View Code

 14、LA 3644 X-Plosives

  题意:给来多少对准,表示a和b相连,要力保每个连通块为平颗树,要去哪些对。

  思路:并查集。

5588葡京线路 275588葡京线路 28

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 100100;
 4 int pre[maxn];
 5 int Find(int x)
 6 {
 7     if (x == pre[x]) return x;
 8     else
 9     {
10         int fa = pre[x];
11         pre[x] = Find(fa);
12         return pre[x];
13     }
14 }
15 bool Union(int x, int y)
16 {
17     int fx = Find(x), fy = Find(y);
18     if (fx == fy) return true;
19     else
20     {
21         pre[fx] = fy;
22         return false;
23     }
24 }
25 int main()
26 {
27     int a,b;
28     while (~scanf("%d", &a))
29     {
30         scanf("%d", &b);
31         for (int i = 0; i < maxn; i++) pre[i] = i;
32         Union(a, b);
33         int cnt = 0;
34         while (scanf("%d", &a) && a != -1)
35         {
36             scanf("%d", &b);
37             if (Union(a, b)) cnt++;
38         }
39         printf("%d\n", cnt);
40     }
41     return 0;
42 }

View Code

 15、LA 3027 Corporative Network

  题意:每次可了解同下合作社到那所于的不在少数的为主企业之线路长度,或者以某群的主导企业A接到任何一个群底某家公司B,并且两个多有着的商店之骨干转移呢原本B所在群的基本企业。

  思路:带权并查集。

5588葡京线路 295588葡京线路 30

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn = 20010;
 6 int pre[maxn];
 7 int val[maxn];
 8 int n;
 9 void Init()
10 {
11     for (int i = 0; i <= n; i++) pre[i] = i, val[i] = 0;
12 }
13 int Find(int x)
14 {
15     if (x == pre[x]) return x;
16     else
17     {
18         int fa = pre[x];
19         pre[x] = Find(fa);
20         val[x] = val[x] + val[fa];
21         return pre[x];
22     }
23 }
24 bool Union(int x, int y,int l)
25 {//I x y
26     int fx = Find(x), fy = Find(y);
27     if (fx == fy) return true;
28     else
29     {
30         pre[fx] = fy;
31         val[fx] = l + val[y];
32         return false;
33     }
34 }
35 int main()
36 {
37     int t;
38     scanf("%d", &t);
39     char s[5];
40     while (t--)
41     {
42         scanf("%d", &n);
43         Init();
44         while (~scanf("%s", s))
45         {
46             if (s[0] == 'O')break;
47             if (s[0] == 'E')
48             {
49                 int x;
50                 scanf("%d", &x);
51                 Find(x);
52                 printf("%d\n", val[x]);
53             }
54             else
55             {
56                 int x, y;
57                 scanf("%d%d", &x, &y);
58                 Union(x, y, abs(x - y) % 1000);
59             }
60         }
61     }
62     return 0;
63 }

View Code

 16、LA 4487 Exclusive-OR

  题意:每次告诉你A的价是稍稍要A和B异或的结果是有些,或者了解k个数连续异或的值。

  思路:带权并查集。

5588葡京线路 315588葡京线路 32

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 const int maxn = 21000;
  6 int pre[maxn], re[maxn];
  7 int vis[maxn], num[20];
  8 int supperroot = maxn - 10;
  9 void init(int n)
 10 {
 11     for (int i = 0; i <= n + 1; i++)
 12     {
 13         pre[i] = i;
 14         re[i] = 0;
 15         vis[i] = 0;
 16     }
 17     pre[supperroot] = supperroot;
 18     re[supperroot] = 0;
 19 }
 20 int Find(int x)
 21 {
 22     if (x != pre[x])
 23     {
 24         int fa = pre[x];
 25         pre[x] = Find(pre[x]);
 26         re[x] ^= re[fa];
 27     }
 28     return pre[x];
 29 }
 30 bool Union(int x, int y, int val)
 31 {
 32     int fx = Find(x);
 33     int fy = Find(y);
 34     if (fx == fy)
 35     {
 36         if ((re[x] ^ re[y]) != val) return 0;
 37         else return 1;
 38     }
 39     if (fx == supperroot) swap(fx, fy);
 40     pre[fx] = fy;
 41     re[fx] = re[x] ^ re[y] ^ val;
 42     return 1;
 43 }
 44 int main()
 45 {
 46     int n, Q, p, q, val, kase = 0;
 47     char ch[2];
 48     char s[40];
 49     while (scanf("%d%d", &n, &Q))
 50     {
 51         if (n==0&&Q==0) break;
 52         init(n);
 53         printf("Case %d:\n", ++kase);
 54         bool flag = 0;
 55         int facts = 0;
 56         for (int i = 1; i <= Q; i++)
 57         {
 58             scanf("%s", ch);
 59             if (ch[0] == 'I')
 60             {
 61                 facts++;
 62                 gets(s);
 63                 if (sscanf(s, "%d%d%d", &p, &q, &val) == 2)
 64                 {
 65                     val = q; 
 66                     q = supperroot;
 67                 }
 68                 if (flag) continue;
 69                 if (!Union(p, q, val))
 70                 {
 71                     printf("The first %d facts are conflicting.\n", facts);
 72                     flag = 1;
 73                 }
 74             }
 75             else
 76             {
 77                 int k, ans = 0;
 78                 scanf("%d", &k);
 79                 for (int i = 1; i <= k; i++)
 80                 {
 81                     scanf("%d", &num[i]);
 82                     if (flag) continue;
 83                     int fa = Find(num[i]);
 84                     ans ^= re[num[i]];
 85                     num[i] = fa;
 86                     vis[fa] ^= 1;
 87                 }
 88                 if (flag) continue;
 89                 bool unknow = false;
 90                 for (int i = 1; i <= k; i++)
 91                 {
 92                     if (vis[num[i]])
 93                     {
 94                         if (num[i] != supperroot)
 95                         {
 96                             unknow = true;
 97                         }
 98                         vis[num[i]] = 0;
 99                     }
100                 }
101                 if (!unknow) printf("%d\n", ans);
102                 else printf("I don't know.\n");
103             }
104         }
105         printf("\n");
106     }
107     return 0;
108 }

View Code

 17、uva 11987 Almost Union-Find

  题意:第一种植操作为把P和Q所在联谊和连,第二栽呢拿结点P放到Q所当集聚里,第三种是查询P所在集合的素数目及总数。

  思路:带权并查集。初始时把每个结点的祖辈指为i+n,这样当次栽操作时,就无见面潜移默化P原来集合的根本。

5588葡京线路 335588葡京线路 34

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 100100;
 4 int pre[maxn];
 5 int sum[maxn];
 6 int cnt[maxn];
 7 int n, m;
 8 int Find(int x)
 9 {
10     if (x == pre[x]) return x;
11     else
12     {
13         int fa = pre[x];
14         pre[x] = Find(fa);
15         return pre[x];
16     }
17 }
18 void Union(int x, int y)
19 {
20     int fx = Find(x), fy = Find(y);
21     if (fx != fy)
22     {
23         pre[fx] = fy;
24         sum[fy] += sum[fx];
25         cnt[fy] += cnt[fx];
26         sum[fx] = 0;
27         cnt[fx] = 0;
28     }
29 }
30 void Change(int x, int to)
31 {
32     int f = Find(to);
33     int init = Find(x);
34     pre[x] = f;
35     sum[f] += x, cnt[f]++;
36     sum[init] -= x, cnt[init]--;
37 }
38 int main()
39 {
40     while (~scanf("%d%d", &n, &m))
41     {
42         for (int i = 0; i <= n; i++) pre[i] = i+n, cnt[i+n] = 1, sum[i+n] = i,pre[i+n]=i+n;
43         int s;
44         while (m--)
45         {
46             scanf("%d", &s);
47             if (s == 1)
48             {
49                 int p, q;
50                 scanf("%d%d", &p, &q);
51                 Union(p, q);
52             }
53             else if (s == 2)
54             {
55                 int p, q;
56                 scanf("%d%d", &p, &q);
57                 Change(p, q);
58             }
59             else
60             {
61                 int p;
62                 scanf("%d", &p);
63                 printf("%d %d\n", cnt[Find(p)], sum[Find(p)]);
64             }
65         }
66     }
67     return 0;
68 }

View Code

 18、LA 5898/uva 1493/hdu 4056 Draw a
Mess

  题意:有几多个体仍顺序在n*m的黑板上绘4种植图形。求最后各种颜色所占据的像素数量。

  思路:用连查集维护每行当前职的产一个可写的职,然后倒序更新。

5588葡京线路 355588葡京线路 36

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cstring>
 6 using namespace std;
 7 
 8 const int maxn = 205;
 9 const int maxm=100500;
10 char str[maxm][25];
11 int xx[maxm], yy[maxm], p[maxm], t[maxm], c[maxm];
12 int Next[maxn][maxm];
13 int Find(int i, int t)
14 {
15     if (Next[i][t] != t)
16         Next[i][t] = Find(i, Next[i][t]);
17     return Next[i][t];
18 }
19 int dele(int i, int l, int r)
20 {
21     int ret = 0;
22     l = Find(i, l);
23     while (l <= r)
24     {
25         ret++;
26         Next[i][l] = l + 1;
27         l = Find(i, l);
28     }
29     return ret;
30 }
31 int main()
32 {
33     int n, m, q;
34     int i, j, x, y, r, w, l, h, color;
35     int tmp1, tmp2, tmp3;
36     int ans[10];
37     while (~scanf("%d%d%d", &n, &m, &q))
38     {
39         for (i = 0; i<n; i++)
40             for (j = 0; j <= m; j++)
41                 Next[i][j] = j;
42         memset(ans, 0, sizeof(ans));
43         for (i = 0; i<q; i++)
44         {
45             scanf("%s%d%d%d%d", str[i], &xx[i], &yy[i], &tmp1, &tmp2);
46             if (str[i][0] != 'R')
47                 p[i] = tmp1, c[i] = tmp2;
48             else
49             {
50                 scanf("%d", &tmp3);
51                 p[i] = tmp1; t[i] = tmp2; c[i] = tmp3;
52             }
53         }
54         for (i = q - 1; i >= 0; i--)
55         {
56             x = xx[i], y = yy[i];
57             if (str[i][0] == 'D')
58             {//菱形
59                 r = p[i], color = c[i];
60                 for (j = max(0, x - r); j <= min(n - 1, x + r); j++)//枚举行
61                     ans[color] += dele(j, max(0, y - r + abs(x - j)),min(m - 1, y + r - abs(x - j)));
62             }
63             else if (str[i][0] == 'T')
64             {//等腰三角形
65                 w = p[i], color = c[i];
66                 h = (w + 1) / 2;
67                 for (j = max(0, x); j<min(n, x + h); j++)
68                     ans[color] += dele(j,max(0, y - h + j - x + 1),min(m - 1, y + h - j + x - 1));
69             }
70             else if (str[i][0] == 'R')
71             {//矩形
72                 l = p[i], w = t[i], color = c[i];
73                 for (j = max(0, x); j <= min(n - 1, x + l - 1); j++)
74                     ans[color] += dele(j, y,min(m - 1, y + w - 1));
75             }
76             else if (str[i][0] == 'C')
77             {//圆形
78                 r = p[i]; color = c[i];
79                 for (j = max(0, x - r); j <= min(n - 1, x + r); j++)
80                 {
81                     int tmp = floor(sqrt(1ll * r*r - (j - x)*(j - x)));
82                     ans[color] += dele(j, max(0, y - tmp), min(m - 1, y + tmp));
83                 }
84             }
85         }
86         for (i = 1; i <= 9; i++)
87         {
88             if (i > 1) printf(" ");
89             printf("%d", ans[i]);
90         }
91         printf("\n");
92     }
93     return 0;
94 }

View Code