首页 > 代码库 > UVA11038- How Many O's?(组合数学)
UVA11038- How Many O's?(组合数学)
题目链接
题意:求出在a到b之间的数中,有多少个0。
思路:组合数学问题。能够枚举每一个位置上的数i,如果i之前的数为left,后面的为right,后面有num位数。当i != 0时,将i置为0,所以组合数为left * 10^num(后面的位数,每一位有10种选择),当i = 0时,当前面取[1, left - 1]时,保证组合的数一定小于原来的数,所以后面的能够取10^num,当取left时,后面的数仅仅能取不大于right的数,所以组合数为(left - 1) * (10 ^ num) + right + 1;
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; ll a, b; ll solve(ll left) { ll ans = 0, num = 1, right = 0, mid; while (left >= 10) { mid = left % 10; left /= 10; if (mid) ans += left * num; else ans += (left - 1) * num + right + 1; right += mid * num; num *= 10; } return ans; } int main() { while (scanf("%lld%lld", &a, &b)) { if (a == -1 && b == -1) break; ll ans = solve(b) - solve(a - 1); if (a == 0) ans++; printf("%lld\n", ans); } return 0; }
UVA11038- How Many O's?(组合数学)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。