首页 > 搜索 > DFS搜索 > HDU 3335-Divisibility-数论-[解题报告]HOJ
2014
03-16

HDU 3335-Divisibility-数论-[解题报告]HOJ

Divisibility

问题描述 :

As we know,the fzu AekdyCoin is famous of math,especially in the field of number theory.So,many people call him "the descendant of Chen Jingrun",which brings him a good reputation.
AekdyCoin also plays an important role in the ACM_DIY group,many people always ask him questions about number theory.One day,all members urged him to conduct a lesson in the group.The rookie daizhenyang is extremely weak at math,so he is delighted.
However,when AekdyCoin tells us "As we know, some numbers have interesting property. For example, any even number has the property that could be divided by 2.",daizhenyang got confused,for he don’t have the concept of divisibility.He asks other people for help,first,he randomizely writes some positive integer numbers,then you have to pick some numbers from the group,the only constraint is that if you choose number a,you can’t choose a number divides a or a number divided by a.(to illustrate the concept of divisibility),and you have to choose as many numbers as you can.
Poor daizhenyang does well in neither math nor programming.The responsibility comes to you!

输入:

An integer t,indicating the number of testcases,
For every case, first a number n indicating daizhenyang has writen n numbers(n<=1000),then n numbers,all in the range of (1…2^63-1).

输出:

An integer t,indicating the number of testcases,
For every case, first a number n indicating daizhenyang has writen n numbers(n<=1000),then n numbers,all in the range of (1…2^63-1).

样例输入:

1
3
1 2 3 

样例输出:

2


Hint:
If we choose 2 and 3,one is not divisible by the other,which is the most number you can choose.

题意是说给你一列数,让你从中选出最多的数能够使得其两两之间不能整除

二分图匹配,求最小路径覆盖即可

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1001;
long long n,a[maxn],match[maxn];
bool map[maxn][maxn],vis[maxn];
bool find(int u)
{
    for(int i=0;i<n;i++)
    {
	if(!map[u][i]||vis[i])
	    continue;
	vis[i]=1;
	if(match[i]==-1||find(i))
	{
	    match[i]=u;
	    return 1;
	}
    }
    return 0;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
	memset(map,0,sizeof(map));
	memset(match,-1,sizeof(match));
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
	    scanf("%I64d",&a[i]);
	    for(int j=0;j<i;j++)
		if(a[i]%a[j]==0||a[j]%a[i]==0)
		    map[j][i]=1;
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
	    memset(vis,0,sizeof(vis));
	    if(find(i))
		ans++;
	}
	printf("%d\n",n-ans);
    }
    return 0;
}

网上居然看到有人用DFS飘过,自己写了下~

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1001;
long long a[maxn],n;
bool vis[maxn];
void DFS(int index)
{
    vis[index]=1;
    for(int i=index+1;i<n;i++)
	if(a[i]%a[index]==0)
	{
	    DFS(i);
	    return;
	}
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
	memset(vis,0,sizeof(vis));
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	    scanf("%I64d",&a[i]);
	sort(a,a+n);
	int ans=0;
	for(int i=0;i<n;i++)
	    if(!vis[i])
	    {
		DFS(i);
		ans++;
	    }
	printf("%d\n",ans);
    }
    return 0;
}

参考:http://blog.csdn.net/z309241990/article/details/9310307


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确