dfs 二进制枚举
dfs
很多值得学习的地方，很多细节
#include <bits/stdc++.h>
using namespace std;
const int N = 11, INF = 0x3f3f3f3f;
char str[N];
int res = INF;
bool check(int x)
{
int t = (int)sqrt(x);//强制转换，可能是浮点数
return x && t * t == x;//x>0很关键
}
void dfs(int u, int t, int s)
{
if (!str[u]) {//枚举到字符串最后一位,注意不能写str[u] == '0'，含义不一样，或者可以写str[u] == '\0'
if (check(s)) res = min(res, t);
return;
}
//t和t+1的理解：
//t表示在当前位置不再删除新的数字
//t + 1表示在当前位置删除一个新的数字
dfs(u + 1, t + 1, s);//分割出完全平方数，s不变
if (s || str[u] != '0') //s不能为0，同时避免添加前导零
dfs(u + 1, t, s * 10 + str[u] - '0');
//两个dfs递归函数参数t的理解、
//思路是反向的，因为不是删数，而是添数（如果是正向，删除任意一位数字不好删）
//如果s不变，那就是相当于删去一个数字，所以t+1
//如果s变，那就是相当于数字不变，所以是t
}
int main()
{
int T;
cin >> T;
while (T -- )
{
scanf("%s", str);
res = INF;//每组测试数据res要重置
dfs(0, 0, 0);//搜索到第几位数字，已经删除了t个完全平方数，删除数字后的数字之和s
if (res == INF) puts("-1");
else cout << res << endl;
}
return 0;
}
二进制枚举
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
int T;
cin >> T;
while (T -- )
{
string str;
cin >> str;
int n = str.size();
int res = INF;
for (int i = 0; i < 1 << n; i ++ )
{
int x = 0;
for (int j = 0; j < n; j ++ )
if (i >> j & 1)
x = x * 10 + str[j] - '0';
int t = sqrt(x); //从 size_t 转换成整型
if (x && t * t == x) res = min(res, n - (int)to_string(x).size());
} //减去的数字个数等于总的数字个数-添的数字个数
if (res == INF) res = -1;
cout << res << endl;
}
return 0;
}
