PAT 1049 Counting Ones

这一题要求从1到N所有数中有多少个1，可以直接暴力写,但这样不能满分。

#include <iostream>
#include <limits.h>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;long long N;
long long cnt;
// 1
// 20
// 300
// 4000
// 50000
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>N;string s=to_string(N);int wei=s.size()-1;long long ans=wei*pow(10,wei-1);long long start=1*pow(10,s.size()-1);for(long long i=start;i<=N;i++){long long x=i;while(x!=0){if(x%10==1){ans++;}x/=10;}}cout<<ans<<endl;return 0;} 

正确做法是数学题，
统计每一位中1出现的次数，然后把它们累加，就是最后的ans，
那么如何找到每一位出现的次数呢？
我们需要找到这一位高位high=？，当前位cut的数字是多少，还有低位low是多少，这些都是影响该位1出现的次数的因素
举一个例子： N=32516，我们找它百位上出现1的次数
cut=5,high=32,low=16,
首先考虑高位对cut的贡献，因为从0-32516，不考虑低位，只考虑高位，那么高位有0-31共32个选择，也即当high=0-31时，百位出现1的次数为32100,（因为有0-31,每一个数，对应百位及以下有100-199共100个)，又因为cut=5，所以当高位high=32，<32的情况已经讨论过了，存在32100-32199共100个，所以百位出现1的次数的结果就是high100+100。其他位是同理的，因此我们可以得出代码：

#include <iostream>
#include <limits.h>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;long long N;
int wei=1;//表示当前处于的位
int ans;
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>N;string s=to_string(N);for(int i=0;i<s.size();i++){int high=N/(wei*10);int cut=N/wei%10;int low=N%wei;if(cut==0){ans+=high*wei;} else if(cut==1){ans+=high*wei+low+1;}else{ans+=high*wei+wei;}wei*=10;} cout<<ans;return 0;} 

时间复杂度为 log2(n)n为数字的长度。
按位统计法值得掌握。