POJ 2253 Frogger 解题报告

题目大意，有两只青蛙，分别在两个石头上，青蛙A想要到青蛙B那儿去，他可以直接跳到B的石头上，也可以跳到其他石头上，再从其他石头跳到B那儿，求青蛙从A到B的所有路径中最小的Frog Distance，我们定义Frog Distance为从A到B的一条路径中所跳的最大距离，例如，如果从A到B某条路径跳的距离是2，5，6，4，则Frog Distance就是6，题目输入的第一行代表石头的个数，当个数为0时结束程序，接着有n行，其中第2，3行分别代表A，B青蛙的坐标，其他n-2行分别代表空的石头的坐标，输出一个小数（保留三位），具体格式参见样例，注意没输出一个答案还要再空一行。

题目数据1很明显为5.000

对于数据2青蛙有两种方案

  • 方案1：1-2则经过距离为2.000故此时Frog Distance=2.000
  • 方案2：1-3-2 则经过距离分别是1.414 1.414 故此时Frog Distance=1.414

故所求的最小的Frog Distance=1.414

这道题和POJ1797比较类似，那个是求最大生成树的最小权，这个是求最小生成树的最大权，哪题是用Kruskal+并查集做的，比较麻烦，则此从网上搜了小Prim算法，果然比较方面，开始时从图中取出点0（数组从0开始），入集合，然后搜索集合外的点到集合的距离，找出距离最小的点，入集合，重复该步骤，直到点1也进入了集合，则此时的权值就是所求的值。

刚开始输出没注意，WA了一次，这还是要提醒我们要小心注意题目的输入输出，别遗漏，确保万无一失才能交；

poj2253 Froggerview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
pair<int ,int> a[200];            //保存n个石头的坐标
double lowcost[200],closet[200];//Prim算法必备，lowcost[i]表示i距离集合的最近距离，closet[i]表示i距离集合最近的点
double map[200][200];            //两点之间的距离
int main()
{
    int n;
    int k=1;
    while(cin>>n,n)
    {
        int i,j;
        for (i = 0 ;i < n ; i++ )
            cin>>a[i].first>>a[i].second;    //输入n个点的坐标，从0开始，也就是说题目编程求0-1的最小Frog Distance
        memset(lowcost,0,sizeof(lowcost));    //清零
        for ( i = 0 ; i < n ; i ++ )
        {
            for ( j = 0 ; j < n ; j ++ )
            {//求任意两点的距离，保存到map中
                map[i][j]=1.0*sqrt(pow(1.0*abs(a[i].first-a[j].first),2)+pow(1.0*abs(a[i].second-a[j].second),2));
            }
        }
        double ans=0.0;//所要求的答案，初始化为0
        for ( i = 0 ; i< n ; i++ )
        {//把0放入集合，则点到集合的距离此时是点到0的距离
            lowcost[i]=map[0][i];
            closet[i]=0;
        }

        for ( i = 0 ; i < n - 1 ; i ++ )
        {
            double mindis=1.0*(1<<20);        //点到集合最小距离，初始化为最大
            int minone;                        //到集合最小距离对应的点
            for ( j = 0 ; j < n ; j ++ )
            {
                if(lowcost[j]&&mindis>lowcost[j])
                {//j点不在集合中，并且j到集合的距离比最小距离还小，则更新最小距离
                    mindis=lowcost[j];
                    minone=j;
                }
            }
            if(ans<mindis)        //如果答案并不比更新的最小距离大
                ans=mindis;        //更新答案
            lowcost[minone]=0.0;//将该点入集合
            if(minone==1)        //如果改点是1，则水明义江找到了答案
                break;
            for ( j = 0 ; j < n ; j ++ )
            {//更新各点到集合的最小距离
                if(map[j][minone]<lowcost[j])
                {//如果minone到某点j的距离比原来的j到集合的距离要小，则更新该点到集合的距离为改点到minone的距离
                    lowcost[j]=map[j][minone];
                    closet[j]=minone;
                }
            }
        }
        cout<<"Scenario #"<<k<<endl;
        printf("Frog Distance = %.3f\n\n",ans);
        k++;
    }
    return 0;
}

展开全文 >>

POJ2262Goldbach's Conjecture 简单的素数判定

题目大意就是输入一个不小于6的合数，把它表示成两个质数的和，如果有多个，数出相差最大的一组

这题就是简单的枚举+素数判定，没什么技巧

行开始时分解合数时到sqrt（n）时停止，WA了一次，应该是n/2

poj2262 Goldbach's Conjectureview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
bool isprime ( int k )
{
    int t = sqrt ( k + 0.5 ) ;
    for ( int i = 2  ; i <= t ; i ++ )
        if ( k % i == 0 )
            return false ;
    return true ;
}
int main()
{
    int n ;
    while ( scanf ("%d", &n) , n )
    {
        int i ;
        int t = n / 2 ;
        for ( i = 3 ; i <= t ; i += 2 )
            if ( isprime ( i ) && isprime ( n - i ) )
                break ;
        printf ( "%d = %d + %d\n" , n , i , n - i ) ;
    }
    return 0;
}

展开全文 >>

从poj2356来体会 抽屉原理 的妙用

题目大意就是先给出一个数N，接着再给出N个数，要你从这N个数中任意选择1个或多个数，使得其和是N的倍数

如果找不到这样的答案 则输出0

答案可能有多个，但智勇任意输出一个解就行。

输出的第一行是选择元素的个数M，接着M行分别是选择的元素的值

刚开始的时候并不同为什么这一题回事抽屉原理，分析后才明白，昨晚后更有体会

实际上此题一定有解，不存在输出0的结果

证明如下

我们可以依次求出a[0],a[0]+a[1],a[0]+a[1]+a[2],……,a[0]+a[1]+a[2]…+a[n]；
假设分别是sum[0],sum[1],sum[2],……,sum[n]
如果在某一项存在是N的倍数，则很好解，即可直接从第一项开始直接输出答案
但如果不存在，则sum[i]%N的值必定在[1,N-1]之间，又由于有n项sum，有抽屉原理：

把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。
则必定有一对i，j，使得sum[i]=sum[j]，其中i！=j，不妨设j>i

则（sum[j]-sum[i]）%N=0，故sum[j]-sum[i]是N的倍数

则只要输出从i+1～j的所有的a的值就是答案

然后就利用这个思路就可以直接的解出该题的答案

刚开始时是因为第一次做这题，代码写的过长，实际上第一种情况和第二种情况可以算一种情况考虑，关于简化后的的代码可以参考 poj3370同样的是抽屉原理

poj2356 Find a multipleview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[10000] ;
int mod[10000] ;//mod存储判断sum%n是否出现过，如果没出现时-1，如果出现，则是此时sum对应的k值，即前k项和
int sum [10001];//sum存储的与描述略有不同，sum[k]=a[0]+a[1]+...+a[k-1]；
int main()
{
    int n ;
    int i ;
    while ( cin >> n )
    {
        memset ( mod , -1 , sizeof ( mod ) ) ;
        sum[0]=0;
        for ( i = 0 ; i < n ; i ++ )
        {
            cin >> a[i] ;
        }
        for ( i = 0 ; i < n ; i ++ )
        {
            sum[i+1]=sum[i]+a[i];

            if ( sum [i+1] % n == 0 )
            {//如果是N的倍数，则输出
                int j ;
                cout<<i+1<<endl;
                for ( j = 0 ; j <= i ; j ++ )
                    cout<<a[j]<<endl;
                break;
            }
            if ( mod[sum [i+1] % n]!=-1)
            {//如果找到两个数的余数相同，则依次输出
                int j ;
                cout<<i-mod[sum [i+1] % n]<<endl;
                for ( j = mod[sum [i+1] % n]+1 ; j <= i ; j ++ )
                    cout<<a[j]<<endl;
                break;
            }
            mod[sum [i+1] % n]=i;//将此时对应的余数存到mod中，值为此时的i
        }
    }
    return 0;
}

展开全文 >>

POJ2407Relatives --欧拉函数的简单运用

题目大意就是给一个数n，求出不大于n且与n互素的数的个数，
这就是简单的欧拉函数的运用，关于欧拉函数的求法，网上一搜一大堆，这里省略。
提交一次就A了，不过测试数据不强，我的程序对于1输出的是1，而实际应该是0

poj2407 Relativesview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
    int n ;
    while ( scanf ( "%d", & n ) , n )
    {
        if ( n == 1 )
            printf ("0\n") ; 
        else
        {
            int i , j , m;
            m = sqrt ( n + 0.5 ) ;
            int ans = n ;
            for ( i = 2; i <= m ; i ++ )
                if ( n % i == 0)
                {
                    ans = ans / i * ( i - 1 ) ;
                    while ( n % i == 0 ) 
                        n /= i ;
                }
            if ( n > 1 )
                ans = ans / n * ( n - 1 ) ;

            printf ("%d\n",ans);
        }
    }
    return 0;
}

展开全文 >>

poj2409 Let it Bead 解题报告

题目地址:http://poj.org/problem?id=2409

Polya计数，直接套模版水过，关于Polya计数，任何一本关于组合数学的书都有，详细证明略去。模版地址burnside定理，polya计数 模版

poj2409 Let it Beadview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int gcd (int a, int b) 
{ 
	return b ? gcd(b,a%b) : a; 
}
ll polya(int c,int s)
{
	int k;
	ll p[64]; 

	// power of c
	p[0] = 1; 
	for (k=0 ; k<s ; k++) 
		p[k+1] = p[k] * c;

	// reflection part
	ll count = s&1 ? s * p[s/2 + 1] :
	(s/2) * (p[s/2] + p[s/2 + 1]);

	// rotation part
	for (k=1 ; k<=s ; k++) 
		count += p[gcd(k, s)];
	count /= 2 * s;
	return count;
}

int main (void)
{
	int c, s;
	while (scanf("%d%d", &c, &s),c||s) 
	{
		cout<<polya(c,s)<<endl;
	}
	return 0;
}

展开全文 >>

poj2478 又一欧拉公式的运用

题目大意就是求Fi集合中元素的个数，其中Fi集合的元素满足下列条件

形如a/b，且0 < a < b <= i, gcd(a,b)=1

很明显，这题就是欧拉公式的运用，关于欧拉公式可查看下这篇文章 POJ2407Relatives --欧拉函数的简单运用

对于这题，可以先求出以每一个小于m的数为分母的数的个数，即也是与该数互素的数的个数，也就是求的phi[i]；

然后再每一个phi都加起来

题目就是比较简单的欧拉运用，1A

poj2478 Farey Sequenceview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
usingnamespace std;
int phi[1000005];
int main()
{
    int i , j ;
    memset ( phi , 0 ,sizeof ( phi ) ) ;
    for ( i =2 ; i <=1000000 ; i ++ )
    {//筛选求phi
if ( ! phi [i] )
        {
            for ( j = i ; j <=1000000 ; j += i )
            {
                if ( ! phi [j] )
                    phi [j ] = j ;
                phi [j] = phi [j] / i * ( i -1 ) ;
            }
        }
    }
    int n ;
    while ( cin >> n  , n )
    {
        __int64 sum =0 ;
        for ( i =2 ; i <= n ; i ++ )
            sum += phi [i] ;
        cout<<sum<<endl;
    }
    return0;
}

展开全文 >>

poj2479与poj2593,同一道DP题

这两道题的题目的题目大意如上，对于输入的n个数，求出最大的S,这是一个简单的DP题，开两个数组，DP[i][0],DP[i][1];,其中DP[i][0]表示的是从0～i中连续子串的最大和,DP[i][1]表示i～n-1中连续子串的最大和,则题目就变成求max{DP[i][0]+DP[i+1][1]}

参考代码：
poj2479

poj2479 Maximum sumview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[50005];
int dp[50005][2];
int i ;
int main()
{
    int t ;
    scanf("%d",&t);
    while ( t -- )
    {
        int n ;
        int sum=0;
        scanf("%d",&n);
        for ( i = 0 ; i < n ; i ++ )
        {
            scanf ("%d", &a[i]) ;
            if (  i )
            {
                sum = max(sum+a[i],a[i]);
                dp[i][0]=max(sum,dp[i-1][0]);
            }
            else
                dp[i][0]=sum=a[i];
        }
        for ( i = n -1 ; i>=0 ; i -- )
        {
            if ( i != ( n - 1 ) )
            {
                sum = max(sum + a[i] , a[i]);
                dp[i][1]=max(sum,dp[i+1][1]);
            }
            else
                dp[i][1]=sum=a[i];
        }
        sum = -(1<<30) ;
        for ( i = 0 ; i < n - 1 ; i ++ )
            sum = max ( sum , dp[i][0]+dp[i+1][1] );
        printf("%d\n",sum);
    }
    return 0;
}

poj2593

poj2593 Max Sequenceview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[100005];
int dp[100005][2];
int i ;
int main()
{
    int n ;
    while ( scanf("%d",&n) , n )
    {

        int sum=0;
        for ( i = 0 ; i < n ; i ++ )
        {
            scanf ("%d", &a[i]) ;
            if (  i )
            {
                sum = max(sum+a[i],a[i]);
                dp[i][0]=max(sum,dp[i-1][0]);
            }
            else
                dp[i][0]=sum=a[i];
        }
        for ( i = n -1 ; i>=0 ; i -- )
        {
            if ( i != ( n - 1 ) )
            {
                sum = max(sum + a[i] , a[i]);
                dp[i][1]=max(sum,dp[i+1][1]);
            }
            else
                dp[i][1]=sum=a[i];
        }
        sum = -(1<<30) ;
        for ( i = 0 ; i < n - 1 ; i ++ )
            sum = max ( sum , dp[i][0]+dp[i+1][1] );
        printf("%d\n",sum);
    }
    return 0;
}

展开全文 >>

POJ 2485 Highways 解题报告

题目大意就是求最小生成树的最大权边，关于求法不再重复，详情请见本博客的今天和昨天题目的解题报告，可以看到此题的类似解法，可以直接把那代码贴过来，改两行就行了。

poj2485 Window Painsview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int map[500][500];
int lowcost[500];
const int inf = (1<<20) ;
int main()
{
    int n;
    int t;
    cin >> t;
    while ( t -- )
    {
        cin >> n ;
        int i , j ;
        for ( i = 0 ; i < n ; i ++ )
            for ( j = 0 ; j < n ; j ++ )
                cin >> map[i][j];
        for ( i = 0 ; i < n ; i ++ )
            lowcost[i]=map[0][i];    //初始化各点到集合的距离
        int ans=0;//记录生成树的最大权值
        for ( i = 0 ; i < n-1 ; i ++ )
        {
            int mindis=inf;
            int minone;
            for ( j = 0 ; j < n ; j ++ )
            {//寻找到集合距离最近的点
                if(lowcost[j]&&mindis>lowcost[j])
                {
                    mindis=lowcost[j];
                    minone=j;
                }
            }
            if(ans <mindis )
                ans =mindis;
            lowcost[minone]=0;
            for ( j = 0 ; j < n ; j ++ )
            {//更新各点到集合的距离
                if(lowcost[j]>map[minone][j])
                    lowcost[j]=map[minone][j];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

展开全文 >>

POJ2488 A Knight's Journey 解题报告

题目大意是给出一个规格小于8*8的棋盘，判断一个只能走“日”的骑士能否不重复的走遍整个棋盘，如果能，按字典序输出走的路径，否则输出“impossible”

这题是一道搜索题，可以用DFS直接解决。每次从左到右，从上到下进行搜索，并标记搜索过的地方；

poj2488 Snakesview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct prog {
	char a ;
	int b ;
}tra;
struct proglu{
	char str[900];
}map;
bool hash[900];
bool found=false;
int p , q ;
int number=0;
void DFS(prog tmp , int n ,proglu map ,int k)
{
	if(found)
		return ;
	if(n==1)
	{
		int i;
		cout<<"Scenario #"<<number<<":"<<endl;
		for(i=0;i<k;i++)
		{

			cout<<map.str[i];
		}
		cout<<endl;
		found=true;
	}
	int t=(tmp.a-'A')*30+tmp.b;
	hash[t]=true;
	prog tmp2;
	tmp2=tmp;
	tmp2.a-=2;
	tmp2.b--;
	if(tmp2.a>='A'&&tmp2.b>=1&&hash[(tmp2.a-'A')*30+tmp2.b]==false)
	{
		map.str[k]=tmp2.a;
		map.str[k+1]=tmp2.b+'0';
		DFS(tmp2,n-1,map,k+2);
		hash[(tmp2.a-'A')*30+tmp2.b]=false;
	}

	tmp2=tmp;
	tmp2.a-=2;
	tmp2.b++;
	if(tmp2.a>='A'&&tmp2.b<=q&&hash[(tmp2.a-'A')*30+tmp2.b]==false)
	{
		map.str[k]=tmp2.a;
		map.str[k+1]=tmp2.b+'0';
		DFS(tmp2,n-1,map,k+2);
		hash[(tmp2.a-'A')*30+tmp2.b]=false;
	}

	tmp2=tmp;
	tmp2.a-=1;
	tmp2.b-=2;
	if(tmp2.a>='A'&&tmp2.b>=1&&hash[(tmp2.a-'A')*30+tmp2.b]==false)
	{
		map.str[k]=tmp2.a;
		map.str[k+1]=tmp2.b+'0';
		DFS(tmp2,n-1,map,k+2);
		hash[(tmp2.a-'A')*30+tmp2.b]=false;
	}

	tmp2=tmp;
	tmp2.a-=1;
	tmp2.b+=2;
	if(tmp2.a>='A'&&tmp2.b<=q&&hash[(tmp2.a-'A')*30+tmp2.b]==false)
	{
		map.str[k]=tmp2.a;
		map.str[k+1]=tmp2.b+'0';
		DFS(tmp2,n-1,map,k+2);
		hash[(tmp2.a-'A')*30+tmp2.b]=false;
	}

	tmp2=tmp;
	tmp2.a+=1;
	tmp2.b-=2;
	if(tmp2.a<='A'+p-1&&tmp2.b>=1&&hash[(tmp2.a-'A')*30+tmp2.b]==false)
	{
		map.str[k]=tmp2.a;
		map.str[k+1]=tmp2.b+'0';
		DFS(tmp2,n-1,map,k+2);
		hash[(tmp2.a-'A')*30+tmp2.b]=false;
	}

	tmp2=tmp;
	tmp2.a+=1;
	tmp2.b+=2;
	if(tmp2.a<='A'+p-1&&tmp2.b<=q&&hash[(tmp2.a-'A')*30+tmp2.b]==false)
	{
		map.str[k]=tmp2.a;
		map.str[k+1]=tmp2.b+'0';
		DFS(tmp2,n-1,map,k+2);
		hash[(tmp2.a-'A')*30+tmp2.b]=false;
	}

	tmp2=tmp;
	tmp2.a+=2;
	tmp2.b-=1;
	if(tmp2.a<='A'+p-1&&tmp2.b>=1&&hash[(tmp2.a-'A')*30+tmp2.b]==false)
	{
		map.str[k]=tmp2.a;
		map.str[k+1]=tmp2.b+'0';
		DFS(tmp2,n-1,map,k+2);
		hash[(tmp2.a-'A')*30+tmp2.b]=false;
	}

	tmp2=tmp;
	tmp2.a+=2;
	tmp2.b+=1;
	if(tmp2.a<='A'+p-1&&tmp2.b<=q&&hash[(tmp2.a-'A')*30+tmp2.b]==false)
	{
		map.str[k]=tmp2.a;
		map.str[k+1]=tmp2.b+'0';
		DFS(tmp2,n-1,map,k+2);
		hash[(tmp2.a-'A')*30+tmp2.b]=false;
	}
}

int main()
{
	int k = 1 ;

	int t;
	cin>>t;
	while(t--)
	{
		number++;
		cin >> q >> p ;
		if(number!=1)
			cout<<endl;
		memset(hash,false,sizeof(hash)) ;
		tra.a='A';
		tra.b=1;
		memset(map.str,0,sizeof(map.str));
		map.str[0]='A';
		map.str[1]='1';
		found=false;
		DFS(tra,p*q,map,2); 
		if(!found)
		{
			cout<<"Scenario #"<<number<<":"<<endl;

			cout<<"impossible"<<endl;
		}
	}
	return 0;
}

展开全文 >>

poj 2492 并查集

题目有点怪，就是告诉你有n只虫子，m条信息，每一条信息的i和j有JQ，求出根据所给的信息能否判断出有搞基的虫子，并按照题目要求信息输出这题用并查集解决起来很方便，当然搜索也可以解

首先分析第一组数据，则可知1和2异性，2和3也异性，可是1和3竟然也有JQ ，这是怎么回事？只能说他们在搞基，则输出Suspicious bugs found!

然后就是这题的处理办法，首先应该想到的是并查集，对于每一对有JQ的虫子，可以将他们分入到两个不同的并查集中，并记录跟这只虫子有JQ的虫子如果加入后存在冲突，则说明有搞基的虫子，没办法，这样就可以不用再考虑以后的虫子JQ了。

上面是大体思路，但有些小细节要考虑

如果那两只虫子之前都没有对象，都是处虫，则更新他们的对象信息；

如果只有其中的一个有对象，假设是a，而b没对象，则将b的对象更新为a，并且让a的对象和b同性，也就是入同一个并查集；

如果a和b都有对象，则有两种情况：

  • a和b在同一个并查集里，则说明a和b有JQ，则可以不必考虑后面的虫子了；
  • 否则，将a和b之前的对象入同一个并查集，b和a之前的对象入同一个并查集；

这就是解这题我的思路，虽不是最优！

开始时因为很久没写并查集了，竟然写错了，WA了一个，然后就是对a和b都有对象的情况考虑不完整，也WA了一次，修正后果然AC了！

poj2492 Standard Point Systemview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int pre[2005];    //并查集常用
int com[2005];    //保存i的对象
int find(int x)
{//并查集的find
    return pre[x]==x?x:pre[x]=find(pre[x]);
}
void join(int x , int y)
{//并查集的join
    int px=find(x);
    int py=find(y);
    if(px!=py)
        pre[px]=py;
}
int main()
{
    int t ;
    scanf("%d",&t);
    int cas=1;
    while (t--)
    {
        int n , m ;
        scanf("%d%d",&n,&m);
        int i ;
        for (i=0;i<2005;i++)
        {//pre初始化
            pre[i]=i;
        }
        memset(com,-1,sizeof(com));

        bool found = false;        //判断是否找到搞基的虫子
        for(i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(found)            //如果找到搞基的虫子，则不用考虑后面了
                continue;
            if (com[a]!=-1)
            {//如果a有对象
                if(com[b]!=-1)
                {//b也有对象
                    if (find(a)==find(b))
                    {//并且a和b也在同一个并查集，则a和b在搞基
                        found=true;
                    }
                    //否则，将a和b之前的对象入同一个并查集，b和a之前的对象入同一个并查集
                    join(a,com[b]);
                    join(b,com[a]);
                    continue;
                }

                //b没对象，则将b的对象更新为a，并且让a的对象和b同性，也就是入同一个并查集
                join(com[a],b);
                com[b]=a;
            } 
            else
            {//a没对象
                if(com[b]!=-1)
                {//b有对象，则将a的对象更新为b，并且让b的对象和a同性，也就是入同一个并查集
                    join(a,com[b]);
                    com[a]=b;
                }
                else
                {//a和b都没对象，则更新他们的对象信息
                    com[a]=b;
                    com[b]=a;
                }
            }
        }
        printf("Scenario #%d:\n",cas++);
        if (found)
        {
            printf("Suspicious bugs found!\n");
        } 
        else
        {
            printf("No suspicious bugs found!\n");
        }
        printf("\n");
    }
    return 0;
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

小龙少，年二十有二。始从文，连考而不中。遂习武，练武场上发一矢，中鼓吏，逐之出。改学IT，自建一变量，用之，烫烫烫烫烫烫烫烫烫烫！