Original Link

思想：

• 贪心，枚举。
• 对于满足条件最大的数，我们枚举其因子 $i$：
  • 保证 $i$ 从 $\sqrt{n}$ 开始递减枚举；
  • 得到 $st = i \times i$，判断 $st$ 是否可由删除 $n$ 的某些位得到。
• 若首次找到符合条件的数，即为所求；
• 否则，直到 $i = 1$ 还未找到满足条件的数，说明不存在。

代码：

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
 
string s;
 
bool check(LL x){
    string st = to_string(x);  // 得到 st = i * i
    int idx = 0;  // 遍历 st 的下标
    for(int i = 0; i < s.size(); i ++){
        if(idx < st.size() && st[idx] == s[i]) idx ++;  // st[idx] == s[i] 说明当前位照应，则 idx 后移
    }                                               // 否则说明应当删除当前位
    if(idx == st.size()) return 1;  // 若 idx 遍历完了 st , 说明可以经过操作得到 st
    return 0;
}
 
void solve(){
    LL n; cin >> n;
    s = to_string(n);  // 将 n 转换为 strintg 类型，便于后续枚举位来比较
    for(LL i = sqrtl(n); i >= 1; i --){  // i 从 sqrtl(n) 开始递减枚举
        if(check(i * i)){  // 判断是否满足
            string st = to_string(i * i);  // 得到 st = i * i
            cout << s.size() - st.size() << endl;  // 输出操作次数，即为长度的差值
            return ;
        }
    }
    cout << -1 << endl;
}
 
int main(){
    int _; cin >> _;
    while(_ --) solve();
    return 0;
}