第七届蓝桥杯C/C++A组省赛

蓝桥杯 编程 C++ 竞赛 所有文稿

7.剪邮票

DFS+全排列

/*16:26*/
/*16:52 输出296*/
/*16:59 debug完成 输出116*/
#include <iostream>
#include <cmath>
using namespace std;
int a[5][5],path[5],cnt=0,x[10][10];
void dfs(int m,int n,int inx){
    if (x[m+1][n]==1){
        x[m+1][n]=0;
        dfs(m+1,n,inx);
    }
    if (x[m-1][n]==1){
        x[m-1][n]=0;
        dfs(m-1,n,inx);
    }
    if (x[m][n+1]==1){
        x[m][n+1]=0;
        dfs(m,n+1,inx);
    }
    if (x[m][n-1]==1){
        x[m][n-1]=0;
        dfs(m,n-1,inx);
    }
}
bool yes(){
    memset(x,0,sizeof(x));
    for(int i=0;i<5;i++){
        x[(path[i]-1)/4][(path[i]-1)%4]=1;//一开始写成了path[i]%4-1，很快debug完成
    }
    int tot=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<4;j++){
            if (x[i][j]==1) dfs(i,j,++tot);
        }
    }
    if (tot==1) return true;
    else return false;
}
void solve(int cur){
    if (cur>=5){
        if (yes()){
            cnt++;
            for(int i=0;i<5;i++) cout<<path[i]<<" ";
            cout<<endl;
        }
        return;
    }
    else{
        for(int i=1;i<=12;i++){
            bool ok=true;
            if (cur==0||i>path[cur-1]){
                for(int j=0;j<cur;j++){
                    if (path[j]==i){
                        ok=false;
                        break;
                    }
                }
                if (ok){
                    path[cur]=i;
                    solve(cur+1);
                }
            }
        }
    }
}
int main(){
    int temp=1;
    for(int i=0;i<3;i++){
        for(int j=0;j<4;j++){
            a[i][j]=temp++;
        }
    }
    solve(0);
    cout<<cnt<<endl;
    return 0;
}

8.四平方和

这届蓝桥杯怎么这么难呢……

思路：枚举，设一个该数平方根为上线以提高运算速度。

对如何退出递归不熟练，参考了紫书上困难的串的代码才写出来

/*17:02*/
/*17:35 已完成 但复杂度太高 只能通过部分案例*/
#include <iostream>
#include <cmath>
using namespace std;
long long n,a[5],x;
int solve(int cur,long long ctot){
    //printf("\ncur=%d ctot=%d\n",cur,ctot);
    if (cur>=4){
        if (ctot==n) return 0;//已经找到解
        else return 1;
    }
    for(long long i=0;i<=sqrt(n*1.0);i++){
        long long ttot=ctot+i*i;
        //printf("ctot=%d\n",ttot);
        if (ttot<=n){
            a[cur]=i;
            //printf("i=%d cur=%d ctot=%d\n",i,cur,ttot);
            if (!solve(cur+1,ttot)) {
                return 0;//已找到解
            }
        }
    }
    return 1;
}
int main(){
    cin>>n;
    solve(0,0);
    for(int i=0;i<4;i++){
        cout<<a[i]<<" ";}
    system("pause");
    return 0;
}

运行时间还是太长了，参考网上的做法，进行数据重复利用，用一个数组存放运算过的数，代码略。

效率似乎还是不够

2019.3.10