题解 CF962C 【Make a Square】-白红宇

题解 CF962C 【Make a Square】

阅读量：4647 次

发布时间：2019-06-09

本文共 1940 字，大约阅读时间需要 6 分钟。

这是一个深搜的模板题。

首先，我们发现n的位数很小，只有9位。于是我们想到了深搜算法。

首先，把n拆分成数组，记n的数位个数位$|n|$。

枚举$|n|$个元素的全排列。

之后我们判定。

一个是完全平方数当且仅当

$\left\lfloor\sqrt(x)\right\rfloor$ = $\sqrt(x)$

于是对于每一个全排列，把他们拼起来，然后判定即可

注意要去除前导零和长度为0的情况。

代码中，存放排列使用$vector$实现的

// Author : harry// Language : C++ (GNU C++ 11)// Upload : CodeForces / luogu// Time : 2018.9// Problem : Make a Square// Tell Myself : Think Twice Code Once// All rights reserved#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std ;#define rep(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)#define Rep(i,a,b) for (int (i)=(a)-1;(i)<(b);(i)++)#define REP(i,a,b) for (int (i)=(a);(i)>=(b);(i)--)#define reg(i,x) for (int (i)=head[x];(i);i=e[i].next)#define ull unsigned long long#define ll long long#define ls ((x)<<1)#define rs ((x)<<1|1)#define mp make_pair#define pb push_back#define fi first#define se second#define endl '\n'#define Pii pair
                      
                       const int N = 100010 ;const int iinf = INT_MAX/2 ;const ll linf = LONG_MAX/2 ;const int MOD = 1e9+7 ;inline int read(){ int X=0,w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0');}int a[20] ;int n,ans=-1,x ;vector
                       
                         b ;void init(int x){ while(x) a[++n]=x%10,x/=10 ; reverse(a+1,a+n+1) ;}bool judge(int m){ //判定是不是完全平方数 double x=sqrt(m); if (floor(x)==x) return 1; return 0;}bool check(vector
                        
                          dig){ //判定 int tmp=0 ; for (int i=0;i

dig){ //深搜 if (k==n+1){ if (check(dig)) ans=max(ans,(int)dig.size()); return ; } dfs(k+1,dig); dig.pb(a[k]);dfs(k+1,dig) ;}int main(){ scanf("%d",&x) ; init(x) ; dfs(1,b) ; if (ans==-1) printf("-1\n") ; else printf("%d\n",n-ans) ;}