题目描述
给定一个不含前导 $0$ 的正整数 $n$。
你可以对 $n$ 进行删位操作。
每次操作,可以将 $n$ 的任意一位数字删去,但是需要保证每次操作完成后的数字仍然是不含前导 $0$ 的正整数。
如果想要使得 $n$ 可以成为某个正整数的平方,那么最少需要对 $n$ 进行多少次操作?
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据占一行,包含一个整数 $n$。
输出格式
每组数据输出一行结果,表示最少需要的操作次数,如果不可能使 $n$ 变为某个正整数的平方,则输出 $−1$。
数据范围
前三个测试点满足 $1≤n≤10000$。
所有测试点满足 $1≤T≤10,1≤n≤2×10^9$。
输入样例1:
1
8314
输出样例1:
2
输入样例2:
1
625
输出样例2:
0
输入样例3:
1
333
输出样例3:
-1
代码&思路
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int t;
cin>>t;
string s;
while(t--)
{
cin>>s;
int n=s.size();
int res=100;
for(int i=1;i<1<<n;i++)//枚举每一种方案
{
int x=0;
for(int j=0;j<n;j++)//枚举每一位
if(i>>j&1)//判断删去之后构成的数(i)是否包含原数的第j位
x=x*10+s[j]-'0';//如果是的话就存下来
int t=sqrt(x);//开个平方
if(x&&t*t==x)//如果是平方数
res=min(res,n-(int)to_string(x).size());//用原来的长度减去可以称为平方数的位数就是我们的最少操作数
}
if(res==100) res=-1;//如果说没有更新数值,则说明没有找到答案,按照题目要求换成-1
cout<<res<<endl;
}
return 0;
}
不过我感觉你的更厉害一点
您才是奆佬%%%Ors
这个题我是枚举的所有平方数,然后看 能不能操作成为这个数字 /xyx