第1章　枚舉與模擬

1.1　卡片(★)

題目信息

2021 年省賽 - 填空題

● C/C++ A組第1題；C/C++ B組第2題

● Java B組第2題；Java C組第3題

● Python 組第1題

【問題描述】

小藍有很多數字卡片，每張卡片上都是一個數字（0到9）。

小藍準備用這些卡片來拼一些數，他想從 1 開始拼出正整數，每拼一個，就保存起來，卡片就不能用來拼其他數了。

小藍想知道自己能從1拼到多少。

例如，當小藍有 30張卡片，其中 0 到 9 各 3 張，則小藍可以拼出 1 到 10，但是拼 11 時卡片 1 已經只有一張了，不夠拼出 11。

現在小藍手里有 0 到 9 的卡片各 2021 張，共 20210 張，請問小藍可以從 1拼到多少?

提示：建議使用計算機編程解決問題。

【答案提交】

這是一道結果填空題，你只需要算出結果后提交即可。本題的結果作為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

懶人速讀

小藍有很多數字卡片，每張卡片上都必然刻有 中的一個數字。

卡片可以用來拼湊數字，假設小藍擁有刻有數字 和數字 的卡片各一張，那么他可以利用這兩張卡片拼湊出數字 這4個正整數。

現給定刻有數字 的卡片各 張，小藍將利用這些卡片從 1 開始連續拼湊數字，請問他最大能拼到數字幾（注意：每張卡片只能利用一次）?

題目分析

核心考點

● 枚舉

● 模擬

本題思路較為簡單，可直接從數字 1 開始往后枚舉，枚舉的同時檢查剩下的卡片能不能拼出當前枚舉到的數字即可。

定義 表示刻有數字 的卡片張數。那么按照題目的意思，初始化 ，參考代碼1-1-1如下。

參考代碼1-1-1

 1   int cnt[10];
2   for(int i = 0 ; i <= 9 ; i ++) cnt[i] = 2021;

若我們將步驟拆分為兩步，則可分為枚舉、檢查。枚舉沒什么問題，寫個循環即可，但該怎么檢查呢?

首先就需要把一個數在十進制下的每一位數字求出來。怎么求呢?可以將該數對 10 取模，這樣就得到了個位上的數字；再除以 10，這樣原本十位上的數字就跑到了個位上；然后再對 10 取模 ...... 反復這個過程，就可以得到這個數在十進制下所有數位上的數字了。

得到數位上的所有數字后再看看這些數字對應的卡片夠不夠，不夠的話就說明這個數拼不了，就停止枚舉，這樣答案就為上一個枚舉的數。

參考代碼1-1-2

 1   bool check(int x){  // x 表示當前枚舉的數
 2       while(x){
 3           int b = x % 10; // 獲取十進制下的每個數位
 4           if(cnt[b] > 0) cnt[b] --; //  這個數位對應的卡片個數 - 1
 5           else return false; // 如果卡片不夠了，則無法拼湊出該數
 6           x /= 10; // 將十位變為個位
 7       }
 8       return true;
9   }

至此，檢查的模塊就完成了。不過我們還可以進行一點小小的優化。

我們的枚舉是從 1 開始的，如果分別看枚舉數的個位、十位......上的數字，那么會得到如下的內容。

顯然，個、十、百、千、萬......每一數位的變化都是有周期性的。每個周期中各個數字出現的次數都是相同的，且每一數位都是從 1 開始變化的。因此，刻有數字 1的卡片一定會被最早使用完，我們只需要對該卡片的張數作判斷就好，具體代碼可見參考代碼第 行。

參考代碼1-1-3

  1   #include<bits/stdc++.h>
  2   using namespace std;
  3   int cnt[10];
  4   bool check(int x){  // x 表示當前枚舉的數
  5       while(x){
  6           int b = x % 10; // 獲取十進制下的每個數位
  7           if(b == 1) {
  8               if(cnt[1] == 0) return false;
  9               cnt[1] -- ;
 10           }
 11           x /= 10; // 將十位變為個位
 12       }
 13       return true;
 14   }
 15   signed main(){
 16       for(int i = 0 ; i <= 9 ; i ++) cnt[i] = 2021;
 17       for(int i = 1 ; ; i ++){
 18           if(!check(i)) return cout << i - 1 << '\n' , 0;
 19       }
 20       return 0;
21   }

最終答案為3181。