解题过程的小记录，如有错误欢迎指出。

难度：四星（找规律题，宛若奥赛，找到规律后程序倒是很简短）

小导航~

题目分析注意点 我的解题过程思路bug代码 dalao的代码借鉴点

题目分析

给出一个数，找出<=这个数的所有含有1的数，并且计算出现的1的次数

注意点

11是含有1的数，且含有2个1，需要在结果中累加2，并不是找出所有含有1的数字的个数

我的解题过程

思路

给出一个数n，例30710，按照从高位到低位对其进行编号（3-1号，0-2号，7-3号，1-4号，0-5号），找出不同号上的位数对结果的影响，设now表示当前指向的号码对应的数字，left表示所指向数字左边的数字，right表示所指向的数字右边的数字，并设置一个变量 a（初始化为1，每次向高一位递增时a累乘10）

当指向1号时 1号所对应的数字是0，当它为1时，left的范围必须是0000~3070（共计3071个），若为3071则生成的数字为30711，超过了n的范围当指向2号时 2号所对应的数字是1，此时a为10，left=307，right=0，当now取1时，left可以取000 ~ 306对应right取0 ~ 9（10个）,当left取307时，right只能取0当指向3号时 3号所对应的数字是7，此时a为100，left=30，right=10，当now取1时，left可以取00 ~ 30，对应right取00 ~ 99（100个）当指向4号时 4号所对应的数字是0，此时a=1000，left=3，right=710,当now取1时，left可以取0 ~ 2，对应right取000 ~ 999（1000个），right取3时，now就不可能为1所以没用当指向5号时 5号所对应的数字是3，此时a=10000，left=0710，当now取1时，left可以取0000 ~ 9999（10000个）

通过以上可以看出当now指向0/1时与其他状态不同，所以要特殊讨论，通过数字看出now，left，right和a的关系，得出 当now=0时，ans += left * a, 当now=1时，ans += left * a + right +1, 当now>=2时，ans += (left + 1)*a

bug

要考虑边界点的输出，如1,7

代码

#include<iostream> #include<string> using namespace std; int main() { long long n, left, right, a = 1, ans = 0; int now; string n_str; cin >> n_str; for (int i = n_str.size() - 1; i >= 0; i--) { now = stoi(n_str.substr(i, 1)); if (i != 0) left = stoll(n_str.substr(0, i)); else left = 0; if (i != n_str.size() - 1) right = stoll(n_str.substr(i + 1)); else right = 0; if (now == 0) { ans += left*a; } else if (now == 1) { ans += left*a + right + 1; } else { ans += (left + 1)*a; } a *= 10; //cout << n_str.substr(i, 1) << " 加了" << ans << endl; } cout << ans; return 0; }

dalao的代码

全部代码因版权原因不放出来，大家可以自行去柳神博客购买或者参考晴神的上机笔记~

借鉴点

还可以通过a来除和求余n来得到now，left和right

left = n / (a * 10), now = n / a % 10, right = n % a;