第七届蓝桥杯省赛 重现 解题报告

差F
问题 A: 煤球数目
注意是求总数目而不是每一层的数目

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7,mod=1e9+7;
int a[maxn],n;
int main(){
    int res=0;
    for(int i=1;i<=100;i++)
        for(int j=1;j<=i;j++)
            res+=j;
    cout<<res;
    return 0;
}

问题 B: 生日蜡烛

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7,mod=1e9+7;
int a[maxn],n;
int main(){
    int sum=0,x,s=0;
    for(int i=1;i<=100;i++){///枚举年龄起点
        sum=0;
        for(int j=i;j<=100;j++){
            sum+=j;
            if(sum==236){
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}

问题 C: 凑算式
美丽的for循环版

#include<bits/stdc++.h>
using namespace std;
int main(){
    int res=0;
    for(double a=1;a<10;a++)
        for(double b=1;b<10;b++)
            if(a!=b)
                for(double c=1;c<10;c++)
                    if(a!=c&&b!=c)
                        for(double d=1;d<10;d++)
                            if(a!=d&&b!=d&&c!=d)
                                for(double e=1;e<10;e++)
                                    if(a!=e&&b!=e&&c!=e&&d!=e)
                                        for(double f=1;f<10;f++)
                                            if(a!=f&&b!=f&&c!=f&&d!=f&&e!=f)
                                                for(double g=1;g<10;g++)
                                                    if(a!=g&&b!=g&&c!=g&&d!=g&&e!=g&&f!=g)
                                                        for(double h=1;h<10;h++)
                                                            if(a!=h&&b!=h&&c!=h&&d!=h&&e!=h&&f!=h&&g!=h)
                                                                for(double i=1;i<10;i++)
                                                                    if(a!=i&&b!=i&&c!=i&&d!=i&&e!=i&&f!=i&&g!=i&&h!=i)
                                                                        if(a+(b/c)+((d*100+e*10+f)/(g*100+h*10+i))==10)
                                                                            res++;
    cout<<res;

    return 0;
}

简洁的dfs版

#include<bits/stdc++.h>
using namespace std;
double a[10];
bool st[10];
int res=0;
void dfs(int u){
    if(u==10)
    if(a[1]+a[2]/a[3]+(a[4]*100+a[5]*10+a[6])/(a[7]*100+a[8]*10+a[9])==10){
        res++;
        return ;
    }
    for(int i=1;i<=9;i++)
        if(!st[i]){
            a[u]=i;
            st[i]=1;
            dfs(u+1);
            st[i]=0;
        }
    return ;
}
int main(){
    dfs(1);
    cout<<res;
    return 0;
}

C++ stl 的next_permutation()

#include <bits/stdc++.h>
using namespace std;
int main() {
	int a[10]={0,1,2,3,4,5,6,7,8,9};
	int sum=0;
	while(next_permutation(a+1,a+10))
	{		
 		double lala=(double)a[1]+(double)a[2]/a[3]+(double)(a[4]*100+a[5]*10+a[6])/(a[7]*100+a[8]*10+a[9]);
        if(lala==10.0)
            sum++;		
	}
	cout<<sum;
	return 0;
} 

问题 D: 抽签

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"f(a,k+1,m-i,b)"<<endl;
    ///cout<<"f(a,k+1,m-j,b)"<<endl;
    return 0;
}

问题 E: 方格填数
dfs版本

#include<bits/stdc++.h>
using namespace std;
bool st[10];
int a[4][5];
int res=0;
bool judge(){
    for(int i=0;i<3;i++)
        for(int j=0;j<4;j++)
            if(abs(a[i][j]-a[i][j+1])==1||abs(a[i][j]-a[i+1][j])==1||abs(a[i][j]-a[i+1][j-1])==1||abs(a[i][j]-a[i+1][j+1])==1) return 0;
    return 1;
}
void dfs(int u){
    if(u==11)
        if(judge()){
            res++;return ;
        }
    for(int i=0;i<10;i++)
        if(!st[i]){
            st[i]=1;
            a[u/4][u%4]=i;
            dfs(u+1);
            st[i]=0;
        }
}
void E(){
    memset(a,0x2f,sizeof a);
    dfs(1);
    cout<<res;
}
int main(){
    E();
    return 0;
}

全排列版本 传送门

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[12]={-2,0,1,2,3,4,5,6,7,8,9,-2};
int dx[8]={1,1,1,0,-1,-1,-1,0};
int dy[8]={-1,0,1,1,1,0,-1,-1};
int res;
bool judge()
{
    for(int i=1;i<=10;i++)
    {
        int y=i/4;
        int x=i%4;
        for(int k=0;k<8;k++)
        {
            int ny=y+dy[k];
            int nx=x+dx[k];
            int j=ny*4+nx;
            if(0<=ny&&ny<3&&0<=nx&&nx<4)
            {    
                if(abs(a[j]-a[i])==1)
                    return false;
            }
        }
    }
    return true;
}
int main()
{
    do{
        if(judge())
            res++;
    }while(next_permutation(a+1,a+11));
    
    printf("%d
",res);
    
    return 0;
}
/*
res:1580
*/
///出自:vCoders

问题 F: 剪邮票

问题 G: 四平方和
暴力解法（O（n^3））

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int a=0;a*a<=n;a++)
        for(int b=a;a*a+b*b<=n;b++)
            for(int c=b;a*a+b*b+c*c<=n;c++){
                int t=n-a*a-b*b-c*c;
                int d=sqrt(t);
                if(t==d*d){
                    printf("%d %d %d %d
",a,b,c,d);
                    goto A;
                }
            }
        A:continue;
    }

    return 0;
}

二分解法（O（n^2 logn））
待补
问题 H: 交换瓶子

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N],n,t;
 
int main(){
    while(cin>>n){
        for(int i=1;i<=n;i++)
        cin>>a[i];
     int ans=0;
    for(int i=1;i<=n;i++)
        if(a[i]!=i){
            for(int j=i+1;j<=n;j++)
              if(a[j]==i){
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                }
            ans++;
        }
        cout<<ans<<endl;
    }
      
    return 0;
}