【无标题】

A. 幸运数字

题目描述

如果把一个数字十进制表示的奇数位和偶数位分别相加得到的和相同，小小就认为它是一个幸运的数字。例如：

• 12345 奇数位相加 1 + 3 + 5 = 9、偶数位相加 2 + 4 = 6，因此 12345 不是幸运数字；
• 2332 奇数位相加 2 + 3 = 5、偶数位相加 3 + 2 = 5，因此 2332 是幸运数字。

对于给定的 a 和 b，小小希望你求出 a, a + 1, a + 2, …, b 中幸运数字的数量。

输入格式

输入数据仅一行，包含空格分隔的两个整数 a 和 b。

输出格式

输出一行一个整数，代表 a, a + 1, a + 2, …, b 中幸运数字的数量。

样例

样例输入 1

复制1 100

样例输出 1

复制9

样例输入 2

复制4096 65536

样例输出 2

复制3454

数据范围与提示

• 对于 100% 的数据，满足 1 ≤ a ≤ b ≤ 1, 000, 000。

思路

首先观察一下数据，a<=b<=1'000'000。

假设以暴力的思想解决，枚举a到b需要写一重1'000'000的循环，每一个数字最多有7位，判断是否是“幸运数字”需要7次，所以总复杂度（O）就是1'000'000 * 7 * 7 = 49'000'000，不超时。

以下是代码：

#include <bits/stdc++.h>
using namespace std;
int a,b;
int sum=0;
int c[8];//记录数位
int s=0;
void deal(int sum){
	int i=0;
	while(sum>0){
		i++;
		c[i]=sum%10;
		sum/=10;
	}
	s=i;
	return ;
}
bool judge(){
	int suma,sumb;
	suma=sumb=0;
	for(int i=1;i<=s;i++){
		if(i%2==1){
			suma+=c[i];
		}
		else{
			sumb+=c[i];
		}
	}
	if(suma==sumb){
		return true;
	}
	return false;
}
int main(){
	cin>>a>>b;
	for(int i=a;i<=b;i++){
		s=0;
        memset(c,0,sizeof(c));
        deal(i);
		if(judge()){
			sum++;
		}
	}
	cout<<sum<<endl;
	return 0;
}