冬令营的平方数

题目传送门

思路：用for循环试一遍每个数量，然后dfs，每次标记一个数位，标记完后计算，如果是计算，如果是平方数就返回true，并输出。

代码：

#include <iostream>
#include <cmath>
#define int long long
using namespace std;

string num;
bool flag;

void dfs(string s, int cur, int mb) {
	if(cur == mb) {
		int x = 0;
		for(int i = 0; i < s.size(); i++) {
			if(s[i] != 'a') x = x * 10 + (s[i] - '0');
		}
		if(x != 0LL && abs(sqrt(x) - (int)sqrt(x)) <= 1e-11) flag = true;
		return;
	}
	if(flag) return;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] != 'a') {
			char tmp = s[i];
			s[i] = 'a';
			dfs(s, cur + 1, mb);
			s[i] = tmp;
		}
	}
}

bool check(int x) {
	flag = false;
	dfs(num, 0, x);
	return flag;
}

signed main() {
	cin >> num;
	for(int i = 0; i < num.size(); i++) {
		if(check(i)) {
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

然后这个代码获得了85分的好成绩。

我就是这么逝掉的

易错点：要判断前导0！！！

真正的AC代码要加上这一段：

if(x != 0) {
	for(int i = 0; i < s.size(); i++) {
		if(s[i] != 'a') {
			if(s[i] == '0') return;
			else break;
		}  
	}
}

AC代码：

#include <iostream>
#include <cmath>
#define int long long
using namespace std;

string num;
bool flag;

void dfs(string s, int cur, int mb) {
	if(cur == mb) {
		int x = 0;
		for(int i = 0; i < s.size(); i++) {
			if(s[i] != 'a') x = x * 10 + (s[i] - '0');
		}
		if(x != 0) {
			for(int i = 0; i < s.size(); i++) {
				if(s[i] != 'a') {
					if(s[i] == '0') return;
					else break;
				}  
			}
		}
		if(x != 0LL && abs(sqrt(x) - (int)sqrt(x)) <= 1e-11) flag = true;
		return;
	}
	if(flag) return;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] != 'a') {
			char tmp = s[i];
			s[i] = 'a';
			dfs(s, cur + 1, mb);
			s[i] = tmp;
		}
	}
}

bool check(int x) {
	flag = false;
	dfs(num, 0, x);
	return flag;
}

signed main() {
	cin >> num;
	for(int i = 0; i < num.size(); i++) {
		if(check(i)) {
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

点个赞吧