#C241108A. A
标签（Label）
- 思维
网址（Website）
题目（Problem）
数据规模与约定
对于 $100%$ 的数据满足：
$0 < n \leq 185$，$0 \leq S_i \leq 9$；
测试点 $1, 2, 3, 4$ 满足 $n \leq 18$；
测试点 $5, 6$ 满足字符串 $a$ 随机；
测试点 $8, 9$ 满足 $n \leq 100$；
测试点 $9, 10$ 满足 $n \leq 185$。
题解（Solution）
$\qquad$这道题就是纯纯的找规律，全靠模拟操作来处理。
$\qquad$有一个基本的思路就是先把 $0\sim 9$ 枚举了，然后枚举 $10\sim 99,100\sim 999\cdots $
$\qquad$那我为什么没想出来呢？
$\qquad$首先，位数越小，肯定答案更优，这就鼓励我们每次都去找位数更小的数，那么对于一个位置 $i$ ，什么地方最小呢？肯定是前面所有能接的数中 最小的的那个，很容易发现，如果该数后面 $0\sim 9$ 所有数都出现了 $1$ 次，那么这个数就不能作为个位出现了，这个时候只能接在当前已经有的数的前面（作为十位），而肯定这个时候接上 $1$ 是最优的。
$\qquad$模拟一下，如果后面出现了 $0\sim 9$ ，当前数为 $2$ ，那么这个时候不仅所有的个位都不会成为最后的答案，所有二十开头的数字也不会成为最后的答案，那么如果当前数为 $1\sim 9$ 都出现过了，就意味着 $0\sim 99$ 的数字都不会成为最后的答案了，那么我们就有一个小思路：记录这些在个位上的数字深度为 $1$ ，在十位上的深度为 $2$ ，对于百位，我们就会发现，当且仅当所有后面的数的深度不存在 $1$ 的时候这个数才可以接到百位上，否则答案一定是一个两位数。
$\qquad$这启迪我们有一个新的思路，倒序找到后面出现位数最少的那个，如果出现相同，那就尽量接上更小的那个，并且把当前数接上去，更新作为这个数的最小位数。
$\qquad$时间复杂度 $O(n\times 10)$ ，可能因为出题者不会使用数组来存储，这道题没什么时间复杂度。
出题者题解
算法分析
$n \leq 20$
枚举所有的子序列，在所有可以被表示出的数中找出 $\text{mex}$ 即可。
数据随机
注意到随机情况下这个 $\text{mex}$ 并不会太大，只需要从小到大枚举 $\text{mex}$，然后 $O(n)$ 的 $\text{check}$ 一下是否能被表示出来即可。
正解
考虑从小到大枚举答案的位数 $t$，那么如果要扩展到 $t+1$ 位，需要目前 $[0,10^t)$ 中的每一个数在其前面找一个 $1,2,\cdots,9$，如果找不到说明存在一个 $t+1$ 位的数无法被表示。贪心的想，我们只需要对于每个数 $i$ 记录能表示出其的最短后缀 $g_i$，由于答案是要求 $\text{mex}$，因此只需要对于每个后缀 $i$ 维护 $f_i = \min_{g_j=i} j$ 即可。 复杂度是很充裕的，不然需要用高精度，记得开 $\text{_int128}$。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 256;
bool ST;
char a[N];
int n;
int nxt[N][10],dep[N];
void Solve(){
n=rd();scanf("%s",a+1);
Rof(i,n,1){
For(j,0,9) nxt[i-1][j] = nxt[i][j];
nxt[i-1][a[i]-'0'] = i;
dep[i] = inf;
For(j,0,9) dep[i] = min(dep[nxt[i][j]]+1, dep[i]);
}
if(nxt[0][0] == 0) return printf("0\n"),void();
int mn = inf, x = 0, ans = 0;
For(j,1,9) if(mn > dep[nxt[0][j]])
mn=dep[ nxt[0][j] ], x=nxt[0][j], ans=j;
while(x){
For(j,0,9){
if(dep[x] == dep[nxt[x][j]]+1){
ans = ans*10 + j;
x=nxt[x][j];
break;
}
}
}printf("%lld\n",ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("mex.in","r",stdin);
freopen("mex.out","w",stdout);
int Tt=1;double Tim=clock();
while(Tt--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
