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

poj3310 题目链接 题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。 思路：一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过 环的话并查集就好。。 关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长？ 于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。 具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一 …

hdu4514 题意：给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。 思路：无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。 但是需要注意的是。。。题目并没有保证图一定是联通的。。。所以gg了。。 也就是要在一个不联通的图中求最长路径。。。 没想出来。。搜了一下。。有树形dp的做法。。。有并查集的时候带权的做法。。。 不过感觉最容易想到的还是求多次直径的做法。。。 也就是。。每一个联通块求一次直径。。。取最大。。。 具体做的时候。。。加一个bool数组在bfs标记一下就好。。。 以及bfs的时候。。。由于我之后是要得到最大值。。。而图本身可能是不联通的。。所以要注 …

hdu2874题目链接 题意：给一个森林，问两点的最短距离，或者输出两点不联通。 思路：最最重要的一点是:添加虚点！ 最最重要的一点是:添加虚点！ 最最重要的一点是:添加虚点！ 所谓虚点，就是之前假设某个不存在的点，有点类似做辅助线。 通过添加虚点，我们可以把这个森林转化成一棵树。 这样求两点的距离就可以转化成一棵树上的两点的距离。 用dis[u]+dis[v]-2*dis[LCA(u,v)]来求。 dis[i]表示节点i到新的树根节点的距离。 不联通的话就是LCA 为0的情况（0是添加的虚点，作为新的树的根） 具体添加虚点的方法是：森林中每棵树的根连边到虚点上。权值大小随意，因为最后会抵消（？） 为了知道每棵树的根，需要用到并查 …

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

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就日了汪了。。。 还是把数据的读完再进行操作比较好== 1 2 3 4 /* *********************************************** 5Author :111qqz 6Created Time :2016年03月03 …

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” 1 2 3 4 /* …