原帖子https://blog.csdn.net/da_kao_la/article/details/82381617
我在原帖的基础上加以了改进,改成一次dfs解决一切
被遗漏的数字(30 分)
小明写了一个函数,将1-n 的数随机排列组成一个字符串,每个数字使用且仅使用一次。但是小明在写的时候粗心了,导致生成的字符串丢失了其中一个数字。帮助小明找出这个数字
测试输入包含若干测试用例,每个测试用例占两行,第一行是n(2<=n<=200),第二行是一个字符串。
对每个测试用例输出1 行,输出缺漏的数字
5
1234
20
12345678910111314151617181920
5
12
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
constintMAXN =1e5+5;
intvis[MAXN];
charstr[MAXN];
intans = -1;
boolsolve(char* s,intn,intlast){
if(last ==0) {
ans= -1;
for(inti =1; i <= n; i++) {
if(vis[i] ==1)continue;
if(vis[i] ==0&&ans== -1)ans= i;
else return false;
}
if(ans== -1)returnfalse;
return true;
}
intt =0;
for(inti =0; i < last; i++) {
t *=10;
t += s[i] -'0';
if(t > n)returnfalse;
if(vis[t] !=0)continue;
vis[t] =1;
booltmp =solve(s + i +1, n, last - (i +1));
if(tmp ==true)returntrue;
vis[t] =0;
}
return false;
}
intmain() {
//freopen("/Users/cardinal/Documents/kickstart/B-large.in", "r", stdin);
dodo();
int_;
cin>> _;
while(_--){
strings;
intn;
cin>> n >> s;
fill(vis,vis+ n +1,0);
strcpy(str, s.c_str());
intlen=s.length();
if(solve(str, n, len)) {
cout<
}else{
cout<< -1<
}
}
return 0;
}
网友评论