【算法作业】实验三：划分集合-贪心 & 可能的IP地址-回溯

---

---

第一题：划分集合

1.题目

给定一组整数（它可以包含相等的元素）。
你必须把它分成两个子集A和B（它们都可以包含相等的元素或是空的）。你必须使mex（A）+mex（B）的值最大化。
这里集合的mex表示集合中不存在的最小非负整数。例如：
mex（{1,4,0,2,2,1}）=3
mex（{3,3,2,1,3,0,0}）=4
mex（∅）=0（mex为空集合）
输入
输入由多个测试用例组成。第一行包含一个整数t（1<=t<=100）——测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数n（1<=n<=100）表示集合的大小。
每个测试用例的第二行包含n个整数a1，a2，…an（0<=ai<=100）表示集合中的数字。
输出
对于每个测试用例，打印mex（A）+mex（B）的最大值。
4
6
0 2 1 5 0 1
3
0 1 2
4
0 2 0 1
6
1 2 3 4 5 6
5
3
4
0
注意
在第一个测试用例中，A={0,1,2}，B={0,1,5}是一个可能的选择。
在第二个测试用例中，A={0,1,2}，B=∅是一个可能的选择。
在第三个测试用例中，A={0,1,2}，B={0}是一个可能的选择。
在第四个测试用例中，A={1,3,5}，B={2,4,6}是一个可能的选择。

2.问题分析和算法设计思路

初看这个题目，很容易产生一个暴力的想法：尝试所有的划分情况，计算它们的$mex(A)+mex(B)$的值，然后进行比较。但这样算法的时间复杂度就太大了，因为一个集合的子集数量，随集合的大小n是呈指数式变化的。

这个问题可以采用贪心算法的思路分析：

假设初始有两个空的集合 A、B，而输入的一组整数已经按照非递减的顺序排列好。现在我们需要从这一组整数的第一个数开始，逐个整数取出并放到A、B两个集合中的一个里。现在思考一下：如何放才能让$mex(A)+mex(B)$的值最大化呢？

我们每次将一个数放入集合中，产生的效果可以分为两种：

• $mex(A)+mex(B)$的值增加1
• $mex(A)+mex(B)$的值不变

为了进一步简化我们的问题，我们可以假设：这组非递减的整数是连续的。为什么能够做出这样的假设呢？因为如果某一处不连续，则从此处开始后面的整数将是无意义的。例如，考虑下面两组整数：

• 连续：1，2，3，4
• 不连续：1，2，3，4，6，7，8，9

显然，上面两组输入将得到相同的结果。即一组不连续的整数可以等效为另一组连续的整数的情况。

现在我们开始向两个集合中放数字。考虑如果我们遵守这样的规则：“每取一个数字，我们总是先考虑集合A的需求，当集合A中没有这个数字时，我们就将它放入集合A；否则我们就将它放入集合B。” 而这组整数又是连续的（前面假设），因此每次我们向集合A中添加元素，都将导致“$mex(A)+mex(B)$的值增加1”。于是我们就可以认为每次将元素放入A中都是值得的。

那有没有可能，我把某个元素放入A中时，虽然$mex(A)+mex(B)$的值增加1；但是如果把这个元素放到B中，在后来它将产生增加大于1的影响呢？答案是不能的。这里并不打算仔细讨论这个问题（可能我自己也还没有想的足够清楚）

注：采用贪心的思路，为确保我们每次局部最优的选择，在最终将导致全局最优的结果，我们的选择策略必须具备无后效性。

3.算法实现

前面我们的讨论中作出了“输入的整数已经有序”的假设。其实在无序的情况下，我们按照 “集合A优先” 的策略得到的效果也是一样的，并不需要先对整数进行排序操作。

实现代码：

#include
using namespace std;

int main(){
	int t=0;//测试的组数
	int n=0;//每组测试的数据量
	int a[102]={};//存放数
	int num1=0;
	int num2=0;
	int out[102]={};//存放输出 
	
	cin>>t;
	
	for(int i=0; i<t; i++){
		int mex1[102]={};//第一个集合 
		int mex2[102]={};
		cin>>n;
		
		//输入，同时划分集合 
		for(int j=0; j<n; j++){
			//输入 
			cin>>a[j];
			
			//划分集合 
			if(mex1[a[j]] == 0){
				mex1[a[j]] = 1;
			}
			else if(mex2[a[j]] == 0){
				mex2[a[j]] = 1;
			}
		}
		
		//得到最大值
		for(int j=0; j<=n; j++){
			if(mex1[j] == 0){
				num1 = j;
				break;
			}
		} 
		
		for(int j=0; j<=n; j++){
			if(mex2[j] == 0){
				num2 = j;
				break;
			}
		} 
		
		//保存输出
		out[i] = (num1 + num2);
	}
	
	//输出 
	for(int i=0; i<t; i++){
		cout<<out[i]<<endl;
	}
	
	return 0;
}
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

4.运行结果

5.算法分析

算法的时间复杂度为：$o(n)$，对于每组测试数据，我们都只需遍历一次即可。

---

第二题：可能的IP地址

1.题目

给定一个只包含数字的字符串，通过返回所有可能的有效IP地址组合来恢复该字符串。
有效的IP地址必须采用A.B.C.D的形式，其中A、B、C和D是0-255之间的数字。除非数字为0，否则不能以0作为前缀。

输入描述
输入第一行n，为测试用例个数
接下来n行，输入n个整数字符串
如果可以分解为ip，则输出所有可能的ip，每个ip都要换行；如果不能分解，则输出一个-1。
输入
2
25525511135
25505011535
输出
255.255.11.135
255.255.111.35
-1

2.问题分析和算法设计思路

可以采用回溯法的思路，输入与输出之间就差了三个小数点，我们只需找出小数点合法的位置即可。

如果一个数字串可以成为合法的IP地址，那么它一定是恰好有3个小数点。于是我们可以选择将小数点的位置作为回溯的对象（而不是去确定每个位置会不会有小数点），这样回溯就只有三层。

我们可以从前往后依次来尝试三个小数点的位置：先放第一个小数点，再放第二个小数点，在放第三个。每次放小数点时检查是否合法，不合法就回溯。

3.算法实现

代码：

#include
#include
using namespace std;

const int BigNum = 999;

//将字符串，转化为整数 
long long  str2num(char str[], int first, int end) {
	
	int len = end - first + 1;
	long long sum=0;
	
	//非零整数的零前缀情况 
	if(len > 1 && str[first] == '0') sum = BigNum;
	
	for(int i=0; i<len; i++){
		int num = str[first+i] - '0';
		sum = sum * 10 + num;
	}
	return sum;
}

int main(){
	int n=0;//测试组数
	
	cin>>n;
	cin.get();//读取回车 
	
	//迭代不同的测试组 
	for(int i=0; i<n; i++){
		
		char str[100]={};
		int end[3]={};
		int len=0;//字符串的长度 
		int flag=0;//是否有可能的ip地址 
	
		//输入一串数字
		char temp=cin.get();
		
		for(int j=0; temp != '\n'; j++){
			str[j] = temp;
			len++;
			temp = cin.get();
		} 
		
		//数字太长则无法转为ip地址
		if(len > 12) {
			cout<<"-1"<<endl; 
			continue;
		}
		
		//开始
		long long num=0;//字符串转整数
		
		//迭代第一个小数点的位置 
		for(int j=0; j<len; j++){
			end[0] = j;  

			num = str2num(str, 0, end[0]); 
			if(num > 255) continue;
			
			//迭代第二个小数点的位置 
			for(int k=j+1; k<len; k++){
				end[1]=k;
				
				num = str2num(str, end[0] + 1, end[1]);  
				if(num > 255) continue;
				
				//迭代第三个小数点的位置 
				for(int l=k+1; l<len; l++){
					end[2]=l;
					
					num = str2num(str, end[1] + 1, end[2]);  
					if(num > 255) continue;
					
					else if(str2num(str, end[2] + 1, len - 1) > 255) continue;

					//成功输出结果 
					else {
						for(int m=0; m<len; m++){
							cout<<str[m];
							if(m == end[0] || m == end[1] || m == end[2]) cout<<".";
						} 
						cout<<endl;
						
						flag = 1;
					}
				}
			}
		} 
		
		if(! flag) cout<<"-1"<<endl;
	} 
	
	return 0;
}
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

4.运行结果

5.算法分析

时间复杂度的准确分析会比较复杂，因为每一次小数点的放置都会改变其它小数点可选位置的数量，于是我放弃了。但它至少随着数字串长度的增加，时间复杂度应当是多项式级别，而非指数级别，因为小数点确定只有三个。

---

感谢阅读

博主主页：清风莫追

CSDN话题挑战赛第2期
参赛话题：学习笔记