laoguo 题解分享 · 2024/4/22
数字诗意(编程题) - 题解
题意解析: 一个数如果可以表示为连续的自然数之和[订正:正整数](>=2个数字)称为诗意数字,问给n个数有几个不是诗意数字。 思路: 这个无需保存,即时读入即时处理即时记录。人话就是每读入一个数字就check一下是否是诗意数字,不是就ans++。判断的原理是奇数必定是诗意数字(1=0+1,3=1+2,5=2+3……)[订正:1不行,因为0不是正整数],偶数如果是可以表示为2的n次幂(例如2,4,8,16)则不是诗意数字,其余偶数都是诗意数字(笔者从1到32中抽了几个有代表性的数字试出来的结论,所以笔者也不知道为什么是这样)。 代码: ``` //万能头文件,涵盖了算竞用的大部分库 #include <bits/stdc++.h> //十年oi一场空,不开long long见祖宗 #define int long long //使用std命名空间 using namespace std; const int N = 2e5 + 10; int a[N]; //判断一下x是否是诗意数字 bool check(int x) { bool flag = false; //奇数是诗意数字,1不是 if (x == 1) return true; if (x % 2) return false; else { while (x) { //如果出现了非1的奇数说明该数不是2的n次幂,也就是诗意数字 if (x % 2 && x != 1) flag = true; x /= 2; } if (flag) return false; return true; } } void solve() { int ans = 0, n; cin >> n; for (int i = 1; i <= n; i ++ ) { int x; cin >> x; //如果x是不是诗意数字,ans累加1 if (check(x)) ans ++; } cout << ans; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t --) solve(); return 0; } ```
查看全文
0 0 1 6