hdu 5506 GT and set（dfs爆搜）-白红宇

hdu 5506 GT and set（dfs爆搜）

阅读量：6882 次

发布时间：2019-06-27

本文共 3045 字，大约阅读时间需要 10 分钟。

Problem Description

You are given

Input

In the first line there is the testcase

Output

For each test print

Sample Input

      2 2 1 1 1 1 2 3 2 3 1 2 3 3 4 5 6 3 2 5 6 

Sample Output

      NO YES 
Hint
 For the second test,there are three sets:{1,2,3},{4,5,6},{2,5,6} You are asked to divide into two parts. One possible solution is to put the second and the third sets into the same part,and put the first in the other part. The second part and the third part have same number 6. Another solution is to put the first and the third sets into the same part,and put the second in the other part. 

题意:

有n个集合,问你能否在L次内把所有集合都删去,如果两个或者更多集合内含有一个相同的数,则这些集合可以同时删除

每个集合中的元素小于10,L<=5,n<=30

分析:

由于数据范围都比较小,很容易想到搜索

很容易想到可以枚举当前集合应该删除哪个数,如果下一个集合中已经出现过了这个数,则跳过下一个集合,可以选择的删除的数不超过5个

每个集合中最多有10个数能被选择,所以时间复杂度也就为10^5*n,乘以n是因为要判断需不需要从当前这个集合中删除一个数

首先贴上第一个代码，这个代码在oj上能AC，但是题目给出的样例中的第一个样例却过不来。和下面贴出的第二个样例写得差不多，但就是样例有一个过不了，不懂什么原因。

1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               12 #include
                
                 13 #include
                 
                  14 using namespace std;15 #define ll long long16 #define eps 1e-1017 #define MOD 100000000718 #define N 3619 #define M 30620 #define inf 1e1221 int n,L;22 vector
                  
                    g[N];23 int s[N];24 int vis[M];25 int flag;26 bool judge(int num){27 for(int i=0;i
                   
                    =n){37 flag=1;38 return;39 }40 if(judge(num)){41 dfs(num+1,d);42 }43 if(flag){44 return;45 }46 47 if(d>L){48 return;49 }50 51 for(int i=0;i

View Code

第二个代码，正确。

1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               12 #include
                
                 13 #include
                 
                  14 using namespace std;15 #define ll long long16 #define eps 1e-1017 #define MOD 100000000718 #define N 3619 #define M 30620 #define inf 1e1221 int n,L;22 vector
                  
                    g[N];23 int s[N];24 int vis[M];25 int flag;26 bool judge(int num){27 for(int i=0;i
                   
                    =n){38 //flag=1;39 return true;40 }41 if(judge(num)){42 return dfs(num+1,d);43 }44 //if(flag) return;45 if(d>=L) return false;46 for(int i=0;i

View Code

转载地址：http://hknbl.baihongyu.com/

你可能感兴趣的文章