平方数

平方数

时间： 1ms        内存：128M

描述：

您将获得一个正整数n，写入时不带前导零（例如，数字04不正确）。
在一个操作中，您可以删除给定整数的任何数字，以便结果保持正整数而不带前导零。
用最少的操作找到一个平方数(4,9,16,,,,,,) 如果找不到输出 -1
例如 ： 8314 最少的操作是删除3和4，得到81 ，需要两次操作。

输入：

第一行包含一个整数n（1 ≤ n ≤ 2 ⋅ 10^9）。给出的数字没有前导零。

输出：

输出执行此操作所需的最少操作数。如果无法从n得到一个平方数，则输出-1。

示例输入：

8314

示例输出：

2

提示：

参考答案（内存最优[1132]）：

#include<stdio.h>
#include<math.h>
int num[11],book[11],pre0[11];
int tot=0,mintot=1000;

int getnum(int lenth)
{
    int res=0;
    for(int i=lenth;i>=1;i--){
        if(!book[i]&&!pre0[i]){
            res*=10;
            res+=num[i];
        }
    }
    return res;
}

void solve(int lenth,int dep)
{
    if(dep==lenth+1){
        for(int i=lenth;i>=1;i--){
            if(!book[i]&&num[i])break;
            if(!book[i]&&!num[i]){
                pre0[i]=1;
                tot++;
            }
        }
        for(int i=lenth;i>=1;i--){
            if(book[i])tot++;
        }
        if(tot==lenth)return;
        double x=sqrt(getnum(lenth));
        for(int i=lenth;i>=1;i--)pre0[i]=0;
        if(x==(int)x){
            if(tot<mintot)mintot=tot;
        }
        tot=0;
        return;
    }
    book[dep]=1;
    solve(lenth,dep+1);
    book[dep]=0;
    solve(lenth,dep+1);
}

int main()
{
    //freopen("in.txt","r",stdin);
    int cnt=0,m=0;
    scanf("%d",&m);
    while(m){
        num[++cnt]=m%10;
        m/=10;
    }
    solve(cnt,1);
    if(mintot<1000)printf("%d\n",mintot);
    else printf("-1\n");
    return 0;
}

参考答案（时间最优[2]）：

#include <bits/stdc++.h>
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
char a[maxn];

bool judge(int x) {
    int sq = sqrt(x) + .5;
    return sq * sq == x;
}

void solve(int n) {
    int ans = INT_MAX;
    for (int i = 1; i < 1 << n; i++) {
        LL num = 0;
        int cnt = 0, idx = -1;
        for (int j = n - 1; j >= 0; j--) {
            if ((1 << j) & i) {
                num = num * 10;
                num += a[j] - '0';
                ++cnt;
                if (idx == -1)
                    idx = j;
            }
        }
        if (a[idx] == '0' && cnt > 1) {
            continue;
        }
        if (num > 0 && judge(num)) {
            // cout << num << " " << cnt << " " << i << endl;
            ans = min(ans, n - cnt);
        }
    }
    cout << (ans == INT_MAX ? -1 : ans) << endl;
}

int main() {
#ifdef LOCAL_IM0QIANQIAN
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    IO;
#endif // LOCAL_IM0QIANQIAN
    cin >> a;
    int len = strlen(a);
    reverse(a, a + len);
    solve(len);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。