凑平方
本文最后更新于 600 天前,其中的信息可能已经有所发展或是发生改变。

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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇