文章目錄

• • 題目分析
  • 題目鏈接

題目分析

來源：PAT網站

分析：

以數字abcdefg這個7位數字為例，說一下本題的思路。

1）數字1在每一位出現的次數。
2）以第d位為例，第d位的取值可以分為3種情況，d=0 、d=1和d＞1。 在這些情況下，_ _ _ 1 _ _ _ 這樣的數總共有多少個呢？比如d=0時，如下圖情況1，為了不超過abc0efg這個數，并且滿足_ _ _ 1 _ _ _ ，那么前三位就不能是abc，而只能取000~abc-1，后三位可以取000 ~ 999隨便取。
用變量left與right來記錄d左邊的數和右邊的數等于多少，然后用變量power來表示這1位的權值，比如下面power =1000.

AC代碼

#include<bits/stdc++.h> using namespace std; const int N = 1e9; int n;int calc(int n){vector<int> nums;//把n放到nums中，低位在前while(n) nums.push_back(n%10), n/=10;int res = 0;//從最高位開始枚舉for(int i =nums.size()-1 ;i >=0 ;i--){int d = nums[i]; // 第d位//第d位左邊的數left，第d位右邊的數right，power 表示權值int left = 0 ,right = 0, power =1;//計算左邊的值，高位for(int j =nums.size()-1; j > i; j--) left = left * 10 + nums[j];//計算右邊的值，低位for( int j = i -1; j >= 0; j--){right = right * 10 + nums[j];power *= 10; //權值}//如果d ==0if( d ==0) res += left * power;//如果 d ==1 else if (d == 1) res += left * power + right +1;//如果 d >1 else res += (left + 1) * power;}return res; } int main (){cin >> n;cout<<calc(n)<<endl;}

題目鏈接

PAT甲級1049 Counting Ones (30 分)

https://www.acwing.com/problem/content/1535/

總結

以上是生活随笔為你收集整理的PAT甲级1049 Counting Ones (30 分)：[C++题解]统计1的个数、数位统计的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。