返回题解分享
讨论 / 题解分享/ 帖子详情

数字诗意(编程题) - 题解

题意解析:

一个数如果可以表示为连续的自然数之和[订正:正整数](>=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 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!