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

蓝桥杯 C++ 算法 竞赛 所有文稿

4.第几个幸运数

到x星球旅行的游客都被发给一个整数，作为游客编号。
x星的国王有个怪癖，他只喜欢数字3,5和7。
国王规定，游客的编号如果只含有因子：3,5,7,就可以获得一份奖品。

我们来看前10个幸运数字是：
3 5 7 9 15 21 25 27 35 45
因而第11个幸运数字是：49

小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。

请你帮小明计算一下，59084709587505是第几个幸运数字。

需要提交的是一个整数，请不要填写任何多余内容。

#include <iostream>
#include <queue>
#include <set>
using namespace std;
int main(){
    int yin[3]= {3,5,7};
    long long  t=59084709587505,n=0;
    priority_queue<long long ,vector<long long >,greater<long long >> pq;
    set<long long > num;
    for(int i=0;i<3;i++){
        num.insert(yin[i]);
        pq.push(yin[i]);
    }
    while(pq.top()<=t) {
        long long  x=pq.top();
        cout<<n<<" "<<x<<endl;
        pq.pop();
        n++;
        for(int i=0; i<3; i++){
            if (!num.count(x*yin[i])){
                pq.push(x*yin[i]);
                num.insert(x*yin[i]);
            }
        }
    }
    cout<<n<<endl;
    return 0;
}

注意点：

• 一开始队列和集合需要先插入3、5和7，第一次做的时候漏了插入，导致结果不正确
• 漏用set判重，导致无法运行（？）

全球变暖

两次dfs

/*16'34-17:02*/
#include <iostream>
#include <cmath>
#include <string.h>
using namespace std;
const int maxn=1010;
char island[maxn][maxn];
bool ma[maxn][maxn],m2[maxn][maxn]={false};
int n;
void dfs(int y,int x){
    for(int c=-1;c<=1;c++){
        for(int r=-1;r<=1;r++){
            if (r*c==0&&y+r>=0&&y+r<n&&x+c>=0&&x+c<n){
                if (island[y+r][x+c]=='#'&&!ma[y+r][x+c]){
                    ma[y+r][x+c]=true;
                    dfs(y+r,x+c);
                }
            }
        }
    }
    return;
}
int main(){
    cin>>n;
    memset(ma,false,sizeof(ma));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>island[i][j];
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if (island[i][j]=='#'&&!ma[i][j]){
                cnt++;
                ma[i][j]=true;
                dfs(i,j);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if (!ma[i][j]){
                    for(int c=-1;c<=1;c++){
                        for(int r=-1;r<=1;r++){
                            if (r*c==0&&i+r>=0&&i+r<n&&j+c>=0&&j+c<n){
                                island[i+r][j+c]='.';
                            }
                        }
                    }
                }
            }   
        }
    cnt=0;
    memset(ma,false,sizeof(ma));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if (island[i][j]=='#'&&!ma[i][j]){
                cnt++;
                ma[i][j]=true;
                dfs(i,j);
            }
        }
    }
    cout<<cnt;
    return 0;   
}

10.付账问题

/*16:13 start*/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=50000+10;
int a[maxn];
double b[maxn];
double bzc(int n){
    double tot_b=0.0,s0=0.0;
    for(int i=1;i<=n;i++){
        tot_b+=b[i];
    }
    tot_b=tot_b/(n*1.0);
    cout<<endl<<"tot_b="<<tot_b<<endl;
    for(int i=1;i<=n;i++){
        s0=s0+(b[i]-tot_b)*1.0*(b[i]-tot_b);
        cout<<"i="<<i<<" "<<(b[i]-tot_b)<<endl;
    }
    cout<<"s0="<<s0<<endl;
    return sqrt(s0/(1.0*n));
}
int main(){
    int n;
    double s;
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a,a+n);
    double aver=s*1.0/n;
    int i=1;
    while(s>0){
        if (a[i]<aver) b[i]=a[i]*1.0;
        else b[i]=aver;
        s-=b[i];
        if (n>i){
        aver=s*1.0/(n-i);
        i++;}
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++) cout<<b[i]<<" ";
    cout<<endl<<bzc(n)<<endl;
    double tot_b=0.0,s0=0.0;
    for(int i=1;i<=n;i++){
        tot_b+=b[i];
    }
    tot_b=tot_b/(n*1.0);
    cout<<endl<<"tot_b="<<tot_b<<endl;
    for(int i=1;i<=n;i++){
        s0=s0+(b[i]-tot_b)*1.0*(b[i]-tot_b);
        cout<<"i="<<i<<" "<<(b[i]-tot_b)<<endl;
    }
    cout<<"s0="<<sqrt(s0/(1.0*n))<<endl;
    system("pause");
    return 0;
}

出现了很神奇的输出结果

5 2333
666 666 666 666 666
666 666 666 666 666
466.6 466.6 466.6 466.6 466.6
tot_b=466.6
i=1 0
i=2 0
i=3 5.68434e-014
i=4 0
i=5 0
s0=3.23117e-027
2.54211e-014
tot_b=466.6
i=1 0
i=2 0
i=3 5.68434e-014
i=4 0
i=5 0
s0=2.54211e-014
请按任意键继续. . .

i=5时的5.68434e-014是怎么来的？？？

• 保留四位小数的输出方式

printf( "%.4lf", sqrt(r/n)); 

2019.3.23