//分析解决方案很明显的一个用并查积解决的问题：如果只用一个根肯定满足要求，遍历数组即可
//如果某两个要合并的节点同根肯定会构成回路，不满足要求
这里用sign 标记是否出现了同根，分两种情况处理即可，也WA 了几次，因为复制粘贴把那个求minn 和 maxn 弄错了
还有就是没处理一组输入的时候一定要避免上一组输入的影响，那就是初始化
其他的就是套用并查积的模板就可以了
#include <iostream>
#include <string>
using namespace std;
struct node
{
int parent;
int weight;
};
node maze[100001];
int visit[100001]; //是集合中的元素都被标记
int findfather ( int i )
{
while ( i != maze[i].parent )
i = maze[i].parent;
return i;
}
void merge ( int a, int b )
{
if ( maze[a].weight == maze[b].weight )
{
maze[b].parent = a;
maze[a].weight = b;
}
else if ( maze[a].weight > maze[b].weight )
maze[b].parent = a;
else
maze[a].parent = b;
}
int main ()
{
int a, b, a1, b1, sign;
while ( scanf ("%d %d", &a, &b) != EOF )
{
memset (visit , 0, sizeof (visit));
int maxn = 0;
int minn = 1000000;
//并查积算法的初始化
for ( int i = 1; i < 100001; i ++ )
{
maze[i].parent = i;
maze[i].weight = 1;
}
if ( a == -1 && b == -1 )
break;
if ( a == 0 && b == 0 )
{
printf ("Yes\n");
continue;
}
sign = 0;
do {
if ( a < minn ) minn = a; //找到输入 的所有数据中最小的和最大的便于减小最后数组遍历时的复杂度
if ( b < minn ) minn = b;
if ( a > maxn ) maxn = a;
if ( b > maxn ) maxn = b;
visit[a] = visit[b] = 1;
a1 = findfather (a);
b1 = findfather (b);
if ( a1 == b1 ) //节点同根
{
sign = -1;
}
else
merge (a1, b1);
scanf ("%d %d", &a, &b);
if ( a== 0 && b == 0)
break;
}while (1);
if ( sign == -1 )
{
printf ("No");
}
//遍历并查积看有几个根节点
if ( sign == 0 )
{
for (int i = minn; i <= maxn; i ++)
{
if ( visit[i] && maze[i].parent == i )
sign ++;
}
if (sign == 1)
printf ("Yes\n");
else
printf ("No\n");
}
}
//system ("pause");
return 0;
}
posted @
2010-08-26 10:41 雪黛依梦 阅读(825) |
评论 (1) |
编辑 收藏这可是第一个并查积的题目哦！
先从问题的简单做法入手，构造出原始模型。
如果原始模型是对于集合之间合并处理问题，那么就可以使用并查集使得程序变得高效。
并查集的路径压缩只有在元素之间的特性存在递推关系时才可以使用。
关键是要理解那两个调用的函数，以及用树结构处理时要注意的问题：
1.合并的时候要注意是将高度较小的树合并到高度较大的树，所以小树的parent指向大树根节点
2.一定要理解一点就是合并两个节点实际上是合并他们的根节点，所以一定要找到节点，找到时候理解好也就是为什么findfather中为什么要用while的原因了
//此题运用并查积：就是将所有的村庄放到一个集合中
#include <iostream>
#include <string>
using namespace std;
struct node
{
int parent;
int height;
};
node village[1000];
//找根节点
int findfather (int a)
{
while ( a != village[a].parent ) //理解while 树状结构：找到最终的跟节点
a = village[a].parent;
return a;
}
//合并到同一集合
void merge (int a, int b)
//注意参数：要合并两个节点的根
{
if ( village[a].height == village[b].height )
{
village[b].parent = a;
village[a].height ++;
}
//小树合并到大树
else if ( village[a].height > village[b].height )
{
village[b].parent = a;
}
else
village[a].parent = b;
}
int main ()
{
int n, m;
while ( scanf ("%d", &n) != EOF && n)
{
for (int i = 1; i <= n; i ++) //根据并查积的算法，先将数组初始化，设定本身为一个独立的集合，并且高度都是 1
{
village[i].parent = i;
village[i].height = 1;
}
scanf ("%d", &m);
int a, b;
int a1, b1;
for (int i = 0; i < m; i ++)
{
scanf ("%d %d", &a, &b); //找出要并入集合的元素的根，如果根节点相同则不并入同一个集合，反之，则并入到同一个集合
a1 = findfather (a);
b1 = findfather (b);
if ( a1 != b1 ) //当根节点不同时合并跟节点
merge (a1, b1);
}
//最后遍历并查积数组看看一共有几个不同的集合
int sum = -1;
for (int i = 1; i <= n; i ++)
{
if ( i == village[i].parent )
sum ++;
}
printf ("%d\n", sum);
}
//system ("pause");
return 0;
}
posted @
2010-08-25 22:48 雪黛依梦 阅读(300) |
评论 (0) |
编辑 收藏/*求解过程如下：首先对每个区间，以其起始坐标为关键字，从小到大排序。再依次找每查询一次能覆盖
到的最大的区间，假设还没有看过的书页为(sta , end)，每次可以查询的小段区间用(xi , yi) 表示，
那么对于没有找过的每段区间，我们都是找 xi<=sta，并且yi > sta的区间中yi最大的区间，直到yi = end为止。
最后统计区间的个数，即为最少的查询次数。*/
1#include <iostream>
2#include <algorithm>
3using namespace std;
4#include <string.h>
5
6struct book
7{
8 int ai;
9 int bi;
10}page[5001];
11
12bool cmp (const book &a, const book &b)
13{
14 return a.ai < b.ai;
15}
16int main ()
17{
18 int t, n;
19 while ( scanf ("%d", &t) != EOF )
20 {
21 for ( int i = 0; i < t; i ++ ) //t 组测试数据
22 {
23
24 memset (page, 0, sizeof (page));
25 scanf ("%d", &n);
26 for ( int i = 0; i < n; i ++ ) //总共有 n 页书
27 {
28 scanf ("%d %d", &page[i].ai, &page[i].bi);
29 }
30
31 sort (page, page + n, cmp); //进行排序
32
33
34 //找到最多发送请求的次数: 思路 ：找到第一个end 值之后，通过设定满足题意的条件 while (i < n && page[i].ai <= sta)
35 //找到新的end 值并且赋值为 j 通过比较 j 和上一次的 end 看看是否得到了新的页数信息，出口时end == n
36 int count = 1;
37 int sta = page[0].ai;
38 int end = page[0].bi;
39 int j, i = 1;
40
41 while ( i < n && page[i].ai == sta )
42 {
43 if (end < page[i].bi)
44 end = page[i].bi;
45 i ++;
46 }
47
48 while ( end != n )
49 {
50 sta = end + 1;
51 j = page[i].bi;
52 i ++;
53 while (i < n && page[i].ai <= sta) //
54 {
55 if ( page[i].bi > j)
56 {
57 j = page[i].bi; //以最小的覆盖找到最大的区间长度 ，即 j 保存当前这一组sta 的end
58 }
59 i ++;
60 }
61 if ( j > end )
62 {
63 count ++;
64 end = j;
65 }
66 }
67 printf ("%d\n", count);
68 }
69}
70 // system ("pause");
71 return 0;
72}
73
posted @
2010-08-25 12:14 雪黛依梦 阅读(2293) |
评论 (0) |
编辑 收藏这个题目如果直接在sort中比较 Ji / Fi 会出现RUNTIME ERROR 因为 分母不能为 0 ，这里在输入时直接将它算出来用weight 表示
贪心策略：weight最大的
1#include <iostream>
2using namespace std;
3
4struct food
5{
6 int ji;
7 int fi;
8 double weight;
9}a[1001];
10
11/**//*int cmp (const void *a, const void *b)
12{
13 return (*((food *)a)).weight < (*((food *)b)).weight;
14}*/
15
16bool cmp1 (const food &a, const food &b)
17{
18 return a.weight > b.weight;
19}
20
21int main ()
22{
23 int m, n;
24 while ( scanf ("%d %d", &m, &n) != EOF && (m != -1 && n != -1))
25 {
26 double sum = 0;
27 //输入处理
28 for (int i = 0; i < n; i ++)
29 {
30 scanf ("%d %d", &a[i].ji, &a[i].fi);
31 a[i].weight = (1.0 * a[i].ji) / a[i].fi;
32 }
33
34 printf ("\n");
35 //按每个房间 1 的 猫食能够得到最大数量的Javabeans排序
36 //qsort (a, n, sizeof(a[0]), cmp);
37 sort (a, a + n, cmp1);
38
39 for (int i = 0; i < n; i ++)
40 {
41 printf ("%d %d\n", a[i].ji, a[i].fi);
42 }
43
44 //求的最大量的食物
45 for (int i = 0; i < n; i ++)
46 {
47 if ( m >= a[i].fi)
48 {
49 m -= a[i].fi;
50 sum += a[i].ji;
51 }
52 else if ( m < a[i].fi )
53 {
54 sum += ( m * (1.0 * a[i].ji / a[i].fi ) ); //猫食不够了
55 break;
56 }
57 }
58
59 printf ("%.3f\n", sum);
60 }
61 // system ("pause");
62 return 0;
63}
64
posted @
2010-08-24 18:41 雪黛依梦 阅读(710) |
评论 (0) |
编辑 收藏
开始时这道题目想了挺久的，也走了一点弯路，其实主要是C 语言的二维字符数组没理解好，都是一些基础知识没有掌握，注意打红色的部分就好了
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4char code[1001][17];
5int num[1001];
6int main ()
7{
8 int n;
9 while (scanf ("%d", &n) != EOF && n != 0)
10 {
11 getchar ();
12 memset (code, 0, sizeof (code));
13 memset (num, 0 , sizeof (num));
14
15 for (int i = 0; i < n; i ++) //输入处理
16 {
17 int j = 0;
18 while ( (code[i][j] = getchar ()) != '\n' ) i 代表这是第几个串
19 j ++;
20 }
21
22
23 for (int m = 0; m < n; m ++) //匹配
24 {
25 for (int k = m + 1; k < n; k ++)
26 {
27 if ( !strcmp (code[m], code[k]) ) //相等返回 0
28 num[m]++;
29 }
30 }
31
32 int max = -1; int index = 0;
33 for ( int k = 0; k < n; k ++) //找到出现次数最多的下标
34 {
35 if (max < num[k])
36 {
37 max = num[k];
38 index = k;
39 }
40 }
41 printf ("%s", code[index]);
42 }
43 //system ("pause");
44 return 0;
45}
46
posted @
2010-08-24 16:46 雪黛依梦 阅读(538) |
评论 (0) |
编辑 收藏
//本来以为是一道简单题谁知道。。。。
//用递归写想都不要想，绝对超时，所以还应当回到题目本身的分析上来
//正确思路是：因为mod7的关系，而且f(1)=f(2)=1，所以f(n)的值是循环分布的，而且一定会回到f(n-1)=f(n)=1，
//并且还可得出，这个循环不大于49，因为相邻连个f只有7种取值，这样f(n-1)和f(n)共有49种组合。
//所以，只要找出循环因子即可，寻找方法正是根据f(n-1)=f(n)再次出现的地方来计算
//可以首先为这个题目写一个测试的程序设定一个 a b n（n 比较小时） 的值 看看输出规律
1#include <stdio.h>
2#include <stdlib.h>
3int f[51];
4int main ()
5{
6 int a, b, n;
7 while ( scanf ("%d %d %d", &a , &b, &n) != EOF && a != 0 && b != 0 && n != 0 )
8 {
9 f[1] = f[2] = 1;
10 int i;
11 for (i = 3; i < 51; i ++)
12 {
13 f[i] = (a * f[i - 1] + b * f[i - 2]) % 7;
14 if ( f[i] == 1 && f[i - 1] == 1 ) //找到循环因子 i
15 {
16 break;
17 }
18 }
19
20 n = n % (i - 2);
21 if (n == 0) //刚好经过一个循环
22 printf ("%d\n", f[i - 2]); //开始时，我是因为看了测试程序，把这里设定为输出 0 这种想法是错的，太片面了，因为数据范围很大
23 else
24 printf ("%d\n", f[n]);
25 }
26 //system ("pause");
27 return 0;
28}
29
30
posted @
2010-08-24 14:01 雪黛依梦 阅读(1477) |
评论 (1) |
编辑 收藏AC
1#include <stdio.h>
2int main ()
3{
4 int m, k;
5 while ( scanf ("%d %d", &m, &k) != EOF && m != 0 && k != 0)
6 {
7 int days = 0;
8 while ( m )
9 {
10 m --;
11 days ++;
12 if (days % k == 0)
13 m ++;
14 }
15
16 printf ("%d\n", days);
17 }
18 return 0;
19}
20
posted @
2010-08-24 12:31 雪黛依梦 阅读(208) |
评论 (0) |
编辑 收藏
超时代码：
#include <stdio.h>
#include <stdlib.h>
int a, b;
int com (int n)
{
if (n == 1 || n == 2)
return 1;
else
return ( a * com( n - 1 )+ b * com(n - 2) ) % 7;
}
int main ()
{
int n;
while ( scanf ("%d %d %d", &a, &b, &n) != EOF && ( a != 0 && b != 0 && n != 0 ))
{
printf ("%d\n", com(n));
}
system ("pause");
return 0;
}
posted @
2010-08-23 21:39 雪黛依梦 阅读(87) |
评论 (0) |
编辑 收藏
这样的水题也被我WA了几次，惭愧啊！ 就是就是没有注意当i > j 时输出位置不变的问题
看来做题目一定要细心，小心陷阱
我的代码：
1#include <stdio.h>
2#include <stdlib.h>
3
4int cylen (int a, int b)
5{
6 int max = 0;
7 for (int i = a; i <= b; i ++)
8 {
9 int n = i;
10 int count = 1;
11 while ( n != 1)
12 {
13 count ++;
14 if ( n % 2 == 0)
15 n = n / 2;
16 else
17 n = 3 * n + 1;
18 }
19
20 if (max < count)
21 max = count;
22 }
23 return max;
24}
25
26int main ()
27{
28 int i, j;
29 while ( scanf ("%d %d", &i, &j) != EOF )
30 {
31 int index;
32 if (i > j)
33 {
34 index = i;
35 i = j;
36 j = index;
37 printf ("%d %d %d\n", j, i, cylen (i, j));
38 }
39 else
40 printf ("%d %d %d\n", i, j, cylen (i, j));
41 }
42
43 //system ("pause");
44 return 0;
45}
46
网上的代码：用递归做的，两个代码复杂度完全一样
1# include <stdio.h>
2#include <stdlib.h>
3int fun(long a ,int len)
4{
5 if (a ==1)
6 return len;
7 else if (a %2 ==0)
8 return fun(a/2,len+1);
9 else return fun(3*a+1,len +1);
10}
11int main()
12{
13 unsigned long a,b;
14 unsigned long i,max,temp;
15
16 while (scanf("%ld%ld",&a,&b)!=EOF)
17 {
18 printf("%ld %ld ",a,b);
19 if(a>b) {i = a;a=b;b=i;}
20 for (max = 0,i = a; i <= b; i ++)
21 {
22 temp = fun(i,1);
23 if (max < temp)
24 max = temp;
25 }
26 printf("%ld\n",max);
27 }
28 //system ("pause");
29 return 0;
30}
31
posted @
2010-08-23 19:42 雪黛依梦 阅读(350) |
评论 (0) |
编辑 收藏
和 1102 完全一个类型的，只是调用几个数学函数求距离
1
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5
6int main ()
7{
8 int n, q, a, b;
9 int lowcost[101]; //开始时储存源点到其他各顶点的边值，随后根据加进来的顶点，不断改变所存的边值
10 int edge[101][101]; //存输入的边之间的长度
11 int visit[101]; //标志顶点是否已经加入
12
13 while ( scanf ("%d", &n)!= EOF )
14 {
15 memset (visit, 0, sizeof (visit));
16 memset (lowcost, 0, sizeof (lowcost));
17
18 //输入处理
19 for (int i = 1; i <= n; i ++)
20 {
21 for (int j = 1; j<= n; j ++)
22 {
23 scanf ("%d", &edge[i][j]);
24 }
25 }
26 scanf ("%d", &q);
27 if ( q )
28 {
29 for (int i = 0; i < q; i ++) //本身存在边则该顶点被标记
30 {
31 scanf ("%d %d", &a, &b);
32 edge[a][b] = edge[b][a] = 0;
33 }
34 }
35
36 //prime:每次都从剩下的边中选出最短的一条，标记相关的顶点，并且修改相关边的值
37 //对lowcost 进行初始化处理
38 for (int i = 1; i <= n; i ++ )
39 {
40 lowcost[i] = edge[1][i];
41 }
42
43 int sum = 0;
44 int k;
45 for (int i = 1; i <= n; i ++)
46 {
47 int max = 10000;
48
49 for ( int i = 1; i <= n; i ++ )
50 {
51 if ( lowcost[i] < max && !visit[i] )
52 {
53 max = lowcost[i];
54 k = i;
55 }
56 }
57
58 if (max == 10000) //如果没有找到最小的边一下一个顶点作为起点 ，这就是和找最短路径不同的地方
59 break;
60
61 visit[k] = 1;
62 sum += lowcost[k];
63
64 for (int i = 1; i <= n; i ++)
65 {
66 if ( !visit[i] && lowcost[i] > edge[k][i]) //新引入的顶点到其他顶点的边值 是否 小于 原来的边值
67 {
68 lowcost[i] = edge[k][i];
69 }
70 }
71 }
72 printf ("%d\n", sum);
73 }
74 // system ("pause");
75 return 0;
76}
77
posted @
2010-08-23 15:35 雪黛依梦 阅读(439) |
评论 (0) |
编辑 收藏