Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324) T4 题解

· · 题解

前言

CSP 前最后一场 ABC，想要 AT 绿名，却没能成功。（但是我是卡在 T3 和 T5 上面的！！！！！）

题意

思路

首先，枚举全排列复杂度太高 O(N!)，不可取。

考虑枚举每一个自然数的平方。

其实，最多从 \color{red}0 枚举到 \sqrt{10^{13}} 就可以了。也可以通过检测自然数的平方的位数是否超过了 N 来决定是否结束枚举。

枚举每一个数的平方，然后用前导零补全位数，然后判断这个数的平方的数码是否与给出的数字串一致即可。

坑点

一定要从 \color{red}0 开始枚举！！！！！（蒟蒻在这里卡了 \color{red}25 分钟，交了 \color{red}8 次错误代码，加罚了 \color{red}40 分钟的时间）

代码

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

int N;
string s;
int ans[12];
int b[12];
int final;
signed main(){
    cin>>N;
    cin>>s;
    for(int i=0;i<N;i++){
        ans[s[i]-'0']++;
    }
    for(int i=0;i<=3162300;i++){
        int o=0;
        int k=1ll*i*i;
        memset(b,0,sizeof(b));
        while(k>0){
            b[k%10]++;
            k/=10;
            o++;
        }
        bool flag=true;
        if(o>N){
//          cout<<i<<endl;
            cout<<final<<endl;
            return 0; 
        }
        if(ans[0]<b[0]) flag=false;
        for(int j=1;j<=9;j++){
            if(ans[j]!=b[j])    flag=false;
        } 
        if(flag==true)  final++;
    }
    cout<<final<<endl;
    return 0;
}

结语

正如这道题一样，在一条路走不通的情况下，可以试试其他的路走不走得通。

最后的最后，也祝大家 CSP-J/S 2023 第二轮 RP++！