第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。