2018南京大学计算机夏令营机试题
lipper同学问了我一个算法题，由于时间原因没来得及写，lipper同学就自己动手写了出来，并且顺手写了此篇博文，文笔潇洒，与君共勉。
——dansen
1. Count number of binary strings without consecutive 1's
Given a positive integer n(3≤n≤90), count all possible distinct binary strings of length n such that there are no consecutive 1's .
Examples:
Input: 2
Output: 3 // The 3 strings are 00, 01, 10
Input: 3
Output: 5 // The 5 strings are 000, 001, 010, 100, 101中文题意：给定一个正整数n(3≤n≤90)，数出长度为n的所有可能的不同二进制串的个数，使得串中没有连续的1出现。
解题思路：考试时第一想法是用回溯法，因为长度为n的所有二进制串形成一棵子集树，所以可以用DFS遍历子集树，遍历过程中检查是否有连续的1出现，作为约束函数用于剪枝，时间复杂度为O(2n)。然而用代码实现以后发现10个测点只通过了5个，还有5个测点超时了，毕竟时间复杂度O(2n)实在是太高了。
思考了一会儿，忽然想起来以前学习数理逻辑与图论这门课的时候在递推那一章做过这道题，于是恍然大悟，可以用动态规划求解！令a[i]为长度为i的不含连续1的二进制串的个数，考虑长度为i的不含连续1的任意一个二进制串：若第i位（末位）为0，则第i-1位可以为0也可以为1，这种情况的二进制串有a[i-1]个；若第i位为1，则第i-1位只能为0（否则最后两位为连续两个1，不符题意），进一步考虑第i-2位，由第i-1位为0可知第i-2位可以为0也可以为1，这种情况的二进制串有a[i-2]个。综上可以写出递推式 a[i]=a[i-1]+a[i-2], i≥3，边界条件为a[1]=1,a[2]=3。本题动态规划的时间复杂度为O(n)，所以得到一个教训——能用动态规划做的就尽量不要用回溯法，回溯法实在太容易超时了。。。
这道题有个坑就是当n比较大的时候使用int会溢出，导致第一次用动态规划提交时只通过了5个测点，后来把数组a的元素类型改为long long就AC了。本题动态规划的代码实现如下：
#include<iostream>
using namespace std;
int main() {
int n;
cin>>n;
long long *a = new long long[n+1]{0,2,3};
for(int i=3;i<=n;i++) {
a[i]=a[i-1]+a[i-2];
}
cout<<a[n]<<endl;
return 0;
}2. Missing number
Given a positive integer n(n≤40), pick n-1 numbers randomly from 1 to n and concatenate them in random order as a string s, which means there is a missing number between 1 and n. Can you find the missing number?(Notice that in some cases the answer will not be unique, and in these cases you only need to find one valid answer.）
Examples:
Input: 20
81971112205101569183132414117
Output: 16中文题意：给定正整数n（n≤40），从1到n中随机选择n-1个数，并将它们以随机顺序连接为字符串s，这意味着在1和n之间有一个缺失的数字。你能找到那个缺失的数字吗？（请注意在某些情况下答案不唯一，此时你只需要找到一个有效的答案。）
解题思路：这题乍一看似乎和LeetCode 268 Missing Number十分相似，但实则大相径庭，因为LeetCode的Missing Number是把选中的n-1个数字以int数组的形式直接告诉我们了，而这题n-1个数字是以随机顺序连接在一起形成的字符串，没有告诉我们是如何划分的，要找出缺失的数字也没那么简单了。
注意到题中限制了n≤40，为什么n的上界取这么小呢？我觉得这就是在暗示这题解法的时间复杂度比较高，所以自然应该想到回溯法。分析本题特点，只要能找到字符串s的合理划分方法，从s中提取出n-1个数字，缺失的那个数字自然就找出来了，所以本题的关键就在于字符串s的划分。具体怎么划分呢？不妨这样考虑，设字符串s的长度为n，则对于s中的第i(1≤i≤n-1)个字符，它要么与第i+1个字符结合成一个数字，要么自己单独作为一个数字，对于第n个字符则只能单独作为一个数字。可能有人要问了，第i个字符不是还可以向前和第i-1个字符结合吗？当然可以，但是这种情况就和第i-1个字符向后与第i个字符结合的情况重叠了，所以对这种情况不做考虑。如此一来就是n个字符，除第n个字符外每个字符有两种选择，这是不是和背包问题很像呢？所以用回溯法应该是没问题的。向下一层左子树搜索的约束条件就是由第i个字符与第i+1个字符结合得到的数字落在1到n的范围内且之前未被划分出来，向下一层右子树搜索的约束条件就是由第i个字符单独形成的数字落在1到n的范围内且之前未被划分出来。如若当前字符为'0'，说明之前的划分有误（因为'0'既不能和后一个字符结合，也不能单独成数），应该直接返回上一层。如何知道已经找到了正确的划分呢？只需要在搜索到叶子结点时检验是不是已经划分出n-1个数字即可。
这题需要注意的是对于某些测点可能会有两个答案，比如n=27，s="37258161810262717111420212324131912956152241212345678910" ，s有两种可能的划分，一种是“3 7 25 8 16 18 10 26 27 17 11 14 20 2 1 23 24 13 19 12 9 5 6 15 22 4”，另一种是“3 7 25 8 16 18 10 26 27 17 11 14 20 21 23 24 13 19 1 2 9 5 6 15 22 4”，前者得到的答案是21，后者得到的答案是12，两个答案都是合理答案，至于导致答案不唯一的原因请读者自己揣摩。
有一点我要坦白：很遗憾考试时我并没有做出这题，由于当时第一题用回溯法超时了，这题又被LeetCode上的Missing Number带偏了思路，所以考试时压根就没往回溯法去想，只靠一点骗分技巧骗了点分。考完以后才想到这题也可以用回溯法，然后自己试着实现了一下。为了便于调试，本题的测点全部随机产生，经检验在100000个测点的情况下依然是可以AC的，调试的时候测了下时间，当n接近40的时候回溯部分的耗时也在10-5~10-4 s量级，应该不用担心TLE。回溯法的实现代码如下：
#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<sstream>
#include<ctime>
#include<algorithm>
using namespace std;
const int total=100000; //测点总数
int n;
string s;
void createSample(int& ans,vector<int>& split);
void backtrack(int index,int cnt,vector<bool>& existed,set<int>& myAns);
int main() {
srand((unsigned int)time(NULL));
int num=0; //通过的测点数
for(int i=0;i<total;i++) {
int ans; //缺失的数字，即本题答案
vector<int> split; //测点字符串产生时的划分方法
n=rand()%40+1;
s.clear();
createSample(ans,split);
set<int> myAns; //使用回溯法得到的答案
vector<bool> existed(n+1,false); //标记已划分出来的数字，existed[i]=true表示数字i已划分出来
backtrack(0,0,existed,myAns);
set<int>::iterator it;
it=myAns.find(ans);
if(it!=myAns.end()) {
num++;
}
else {
cout<<n<<endl<<s<<endl;
cout<<"Split:";
for(auto n : split) {
cout<<n<<' ';
}
cout<<endl;
cout<<"Your answer:";
for(set<int>::iterator it=myAns.begin();it!=myAns.end();it++ ) {
cout<<*it<<' ';
}
cout<<endl;
cout<<"Expected answer:"<<ans<<endl;
cout<<"Passed/Total: "<<num<<'/'<<total<<endl;
cout<<"Wrong answer"<<endl;
break;
}
}
if(num==total) {
cout<<"Passed/Total: "<<num<<'/'<<total<<endl;
cout<<"Accepted"<<endl;
}
return 0;
}
//随机产生测点字符串s,缺失的数字存放在ans中，字符串的划分方法存放在split中
void createSample(int& ans,vector<int>& split) {
int m,num=0;
vector<bool> existed(n+1,false);
while(num < n-1) { //每一轮随机产生一个数字m，直至产生n-1个数字为止
m=rand()%n+1;
//检查数字m之前是否已经产生过，只有未产生过的数字才能加入到字符串中
if(existed[m]==false) {
//将int转换为string,加入到字符串s中，并将数字m保存到split中
stringstream ss;
string tmp;
ss<<m;
ss>>tmp;
s+=tmp;
existed[m]=true;
split.push_back(m);
num++;
}
}
vector<bool>::iterator it;
it=find(existed.begin()+1,existed.end(),false);
ans=it-existed.begin();
}
//回溯法求解字符串s的划分，index为字符串s的下标，cnt为已经划分出的数字个数，existed标记已经划分出了的数字，myAns为求解出的缺失的数字
void backtrack(int index,int cnt,vector<bool>& existed,set<int>& myAns) {
if(index >= s.length()) {
//已经划分出n-1个数字，existed中未被标记的就是缺失的数字
if(cnt==n-1) {
vector<bool>::iterator it;
it=find(existed.begin()+1,existed.end(),false);
myAns.insert(it-existed.begin());
}
return;
}
if(s[index]=='0') return; //用于剪枝
//下标为index的字符与下标为index+1的字符组合成一个数字
if(index < s.length()-1) {
int tmp1=(s[index]-'0')*10+s[index+1]-'0';
if(tmp1 >= 1&&tmp1 <= n&&existed[tmp1]==false) {
existed[tmp1]=true;
cnt++;
backtrack(index+2,cnt,existed,myAns);
cnt--;
existed[tmp1]=false;
}
}
//下标为index的字符单独作为一个数字
int tmp2=s[index]-'0';
if(tmp2 >= 1&&tmp2 <= n&&existed[tmp2]==false) {
existed[tmp2]=true;
cnt++;
backtrack(index+1,cnt,existed,myAns);
cnt--;
existed[tmp2]=false;
}
}机试还有一道题，但是题目我记不太清了，考试的时候就粗略看了下题目，觉得没啥想法，直接放弃了。考完google了一下题目里的一些关键词，并没有搜到原题，连相似的题目都没找到，所以这里也就不介绍了。
总体来说南大的机试题还是不算难的，考察的都是比较基本的算法，从近几年的机试题来看，如果是三道题的话，一般第一题是动态规划，第二题是回溯法（DFS），第三题就不好说了。考试按测点给分，三道题每题十个测点，一个测点10分，满分300分。然而往年也有四道题选做两道，按ACM形式排名的，就是提交没有AC的话要罚时，按AC的题数和总用时排名，那种就比较坑了，不知道以后会不会又采用那种形式。
第一次发表文章，希望能帮助到大家，文章里有错误的话欢迎大家帮忙修订哦。感谢您的阅读！