学习和成长|蓝桥杯历届真题 # 数字诗意(C++,Java)

文章目录

题目解读
[蓝桥杯 2024 省 C] 数字诗意
思路
完整代码

题目解读

[蓝桥杯 2024 省 C] 数字诗意

题目描述

在诗人的眼中，数字是生活的韵律，也是诗意的表达。

小蓝，当代顶级诗人与数学家，被赋予了“数学诗人” 的美誉。他擅长将冰冷的数字与抽象的诗意相融合，并用优雅的文字将数学之美展现于纸上。

某日，小蓝静坐书桌前，目光所及，展现着 $n$ 个数字，它们依次为 $a_1, a_2, \cdots, a_n$ ，熠熠生辉。小蓝悟到，如果一个数能够以若干个（至少两个）连续的正整数相加表示，那么它就蕴含诗意。例如，数字 $6$ 就蕴含诗意，因为
它可以表示为 $1 + 2 + 3$ 。而 $8$ 则缺乏诗意，因为它无法用连续的正整数相加表示。

小蓝希望他面前的所有数字都蕴含诗意，为此，他决定从这 $n$ 个数字中删除一部分。请问，小蓝需要删除多少个数字，才能使剩下的数字全部蕴含诗意？

输入格式

输入的第一行包含一个整数 $n$ ，表示展示的数字个数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ，相邻整数之间使用一个空格分隔，表示展示的数字。

输出格式

输出一行包含一个整数，表示小蓝需要删除的数字个数，以使剩下的数字全部蕴含诗意。

样例 #1

样例输入 #1

3
3 6 8

样例输出 #1

提示

【样例说明】

在样例中，数字 $3$ 可以表示为 $1 + 2$ ，数字 $6$ 可以表示为 $1 + 2 + 3$ ，数字 $8$ 无法表示为连续的正整数相加，因此，需要删除的数字个数为 $1$ 。

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $\le n \le 10^3$ ， $\le a_i \le 10^3$ 。
对于所有评测用例， $\le n \le 2 \times 10^5$ ， $\le a_i \le 10^{16}$ 。

思路

观察管理发现,只有2的次方不满足要求
转化为二进制表示,该数字中只有1个1的数字不满足要求
因此题目转化为把数字转为二进制后求起1的个数
若1的个数为1那么就不满足要求

完整代码

#include

using namespace std;

//num的二进制表示中若只有1个1,那么肯定是2的次方
bool check(long long num){
    int cnt=0;
    while(num){
        int left=num%2;
        if(left)cnt++;
        num/=2;
    }
    if(cnt==1)return true;
    else return false;
}

int main(){
    int res=0;
    int n;
    cin>>n;
    while(n--){
        long long num;
        cin>>num;
        if(check(num))res++;
    }
    
    cout<<res;
}

import java.util.Scanner;

class Main{
    static Scanner sc =new Scanner(System.in);
    static int res;
    public static void main(String[] args) {
        int n=sc.nextInt();

        while(n-->0){
            long num=sc.nextLong();
            if(check(num))res++;
        }

        System.out.println(res);
    }

    static boolean check(long num){
        int cnt=0;
        while(num>0){
            long left=num%2;
            if(left>0)cnt++;
            num/=2;
        }
        if(cnt==1)return true;
        else return false;
    }
}

?编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴?

? 如果本篇文章对你有帮助的话那就点个赞吧??

? 本篇文章可能存在多处不足，如有修改意见，可以私信或者评论我哦 ?

在这里插入图片描述