Description

lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次？

poj3310 题目链接

题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。

hdu4514

题意：给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。

思路：无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。

hdu2874题目链接

题意：给一个森林，问两点的最短距离，或者输出两点不联通。

思路：最最重要的一点是:添加虚点！

最最重要的一点是:添加虚点！

最最重要的一点是:添加虚点！

题目链接 题意：没图不好描述，有中文题面中文题面，直接看吧。 思路：据说这道题有三种做法。 当时比赛一种都不会。

先说一种：做法是把格子看成点，可以到达的相邻格子之间看成有边相连，然后倒过来用并查集判断无向图的连通性。具体做法是：先统计初始所有空的位置，然后把所有要增加的山都加上（先统计空的位置是因为山之后要去掉，而去掉以后要得到该点的标号），然后将把所有空的点以及china(设标号为n*m+1)点,和india(**设标号为n*m+2) **点通过并查集来合并..可以从上往下从左往右，每次只需要判断上面的点和左边的点是否有空，如果有就用并查集合并。 china点和india点特殊搞就好。

http://acm.hdu.edu.cn/showproblem.php?pid=5631 题意;给出一张n个点n+1（n<=100）条边的无向图，现在删除若干条边（至少一条边），问删完之后图依然联通的方案数。 思路：分析可知，由于只删边，不删点，n个点，最少需要n-1条边才能联通，所以最多删两条边。我们可以暴力枚举删除的两条边（或者一条边） O(n^2)的复杂度完全可以接受。剩下的问题就变成了每次删边之后判断图的连通性。 题解给出的是bfs。。。大概是bfs一遍，然后入队的点数是n就联通？ 或者dfs一遍也可以？ 也是标记过的点数是n就说明联通？ 但是看到排名考前的人都是用到了并查集来判断...比较巧妙。

http://www.lydsy.com/JudgeOnline/problem.php?id=1604 题意：了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的： 1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C. 2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群． 给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有 …

http://poj.org/problem?id=2492

Hint

Huge input,scanf is recommended.

也是带种类的冰茶几。

由于只分了两类...我们还是可以按照上道题的做法。。

感觉完全是一样的题啊。。

结果一直WA。。。。

最后发现。。。我边读入边判断。。发现同性恋了就直接Break掉了。。。后面改组的数据读到下一组去了233，不WA就日了汪了。。。

http://poj.org/problem?id=1703

种类冰茶几...看到还有一种算是拓展的交加权冰茶几？ 看到有做法是在开一个数组。。。记录是哪一组.... 但是因为只有两组....我们可以分别存... 因为不知道每一个D的两个人分别是哪个组（帮派？） 可以都存一下。 TLE了两次....应该是用了cin的事。。。改成scanf就变WA了。。。 想了下。原来是我对“not sure yet”的判断出现失误。 我开了一个v数组，记录在D下出现的人。 我误以为出现的人的帮派一定是确定的。 实际上并不是。 比如 1,3 5,7 3和7都出现了。但是3和7是一组与否显然还是“not sure yet”