第一题：划分集合
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.问题分析和算法设计思路
初看这个题目，很容易产生一个暴力的想法：尝试所有的划分情况，计算它们的m e x ( A ) + m e x ( B ) mex(A)+mex(B)mex(A)+mex(B)的值，然后进行比较。但这样算法的时间复杂度就太大了，因为一个集合的子集数量，随集合的大小n是呈指数式变化的。
这个问题可以采用贪心算法的思路分析：
假设初始有两个空的集合 A、B，而输入的一组整数已经按照非递减的顺序排列好。现在我们需要从这一组整数的第一个数开始，逐个整数取出并放到A、B两个集合中的一个里。现在思考一下：如何放才能让m e x ( A ) + m e x ( B ) mex(A)+mex(B)mex(A)+mex(B)的值最大化呢？
我们每次将一个数放入集合中，产生的效果可以分为两种：
m e x ( A ) + m e x ( B ) mex(A)+mex(B)mex(A)+mex(B)的值增加1
m e x ( A ) + m e x ( B ) mex(A)+mex(B)mex(A)+mex(B)的值不变
为了进一步简化我们的问题，我们可以假设：这组非递减的整数是连续的。为什么能够做出这样的假设呢？因为如果某一处不连续，则从此处开始后面的整数将是无意义的。例如，考虑下面两组整数：
连续：1，2，3，4
不连续：1，2，3，4，6，7，8，9
显然，上面两组输入将得到相同的结果。即一组不连续的整数可以等效为另一组连续的整数的情况。
现在我们开始向两个集合中放数字。考虑如果我们遵守这样的规则：“每取一个数字，我们总是先考虑集合A的需求，当集合A中没有这个数字时，我们就将它放入集合A；否则我们就将它放入集合B。” 而这组整数又是连续的（前面假设），因此每次我们向集合A中添加元素，都将导致“m e x ( A ) + m e x ( B ) mex(A)+mex(B)mex(A)+mex(B)的值增加1”。于是我们就可以认为每次将元素放入A中都是值得的。
那有没有可能，我把某个元素放入A中时，虽然m e x ( A ) + m e x ( B ) mex(A)+mex(B)mex(A)+mex(B)的值增加1；但是如果把这个元素放到B中，在后来它将产生增加大于1的影响呢？答案是不能的。这里并不打算仔细讨论这个问题（可能我自己也还没有想的足够清楚）
注：采用贪心的思路，为确保我们每次局部最优的选择，在最终将导致全局最优的结果，我们的选择策略必须具备无后效性。
3.算法实现
前面我们的讨论中作出了“输入的整数已经有序”的假设。其实在无序的情况下，我们按照 “集合A优先” 的策略得到的效果也是一样的，并不需要先对整数进行排序操作。
实现代码：
#include<iostream> 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; }
4.运行结果
5.算法分析
算法的时间复杂度为：o ( n ) o(n)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<iostream> #include<cstdio> 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; }
4.运行结果
5.算法分析
时间复杂度的准确分析会比较复杂，因为每一次小数点的放置都会改变其它小数点可选位置的数量，于是我放弃了。但它至少随着数字串长度的增加，时间复杂度应当是多项式级别，而非指数级别，因为小数点确定只有三个。
