第1章　枚舉與模擬

1.1　卡片(★)

題目信息

2021 年省賽 - 填空題

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

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

● Python 組第1題

【問題描述】

小藍(lán)有很多數(shù)字卡片，每張卡片上都是一個數(shù)字（0到9）。

小藍(lán)準(zhǔn)備用這些卡片來拼一些數(shù)，他想從 1 開始拼出正整數(shù)，每拼一個，就保存起來，卡片就不能用來拼其他數(shù)了。

小藍(lán)想知道自己能從1拼到多少。

例如，當(dāng)小藍(lán)有 30張卡片，其中 0 到 9 各 3 張，則小藍(lán)可以拼出 1 到 10，但是拼 11 時卡片 1 已經(jīng)只有一張了，不夠拼出 11。

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

提示：建議使用計(jì)算機(jī)編程解決問題。

【答案提交】

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

懶人速讀

小藍(lán)有很多數(shù)字卡片，每張卡片上都必然刻有 中的一個數(shù)字。

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

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

題目分析

核心考點(diǎn)

● 枚舉

● 模擬

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

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

參考代碼1-1-1

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

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

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

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

參考代碼1-1-2

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

至此，檢查的模塊就完成了。不過我們還可以進(jìn)行一點(diǎn)小小的優(yōu)化。

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

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

參考代碼1-1-3

  1   #include<bits/stdc++.h>
  2   using namespace std;
  3   int cnt[10];
  4   bool check(int x){  // x 表示當(dāng)前枚舉的數(shù)
  5       while(x){
  6           int b = x % 10; // 獲取十進(jìn)制下的每個數(shù)位
  7           if(b == 1) {
  8               if(cnt[1] == 0) return false;
  9               cnt[1] -- ;
 10           }
 11           x /= 10; // 將十位變?yōu)閭€位
 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。