凑平方

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 转换为 string 类型，便于后续枚举位来比较
    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;
}