题目大意
序列$A$由从$N$开始的连续$K$个数按顺序构成,现在将$A$中的每个数只保留某一个数码,记为序列$B$,给定$K$和$B$,求可能的最小的$N$。
题目分析
考虑从低位到高位确定每个数。
我们对每个数$a_i$维护一个集合$S_{a_i}$表示$a_i$数位中存在的数。
一开始的时候每个$S_{a_i}$中仅有$b_i$一个元素。
接下来我们枚举当前位$n$的取值，更新所有数的$S$，然后考虑下一位。
这样每次序列的规模以$\frac1{10}$的速度缩减，时间复杂度为：
注意特殊处理$n=2$的情况，当最后两位分别含有$9,0$时可能死递归。
细节较多，本代码暂时可通过目前所有hack数据。
Hack数据
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
#define bit bitset<10>
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
LL Solve(vector<bit> a,bool zero) {
int down=0,up=9;
if(a.size()==1) {
if(a[0].none()) {
if(zero)return 0;
down=1;
} else {
if(a[0].to_ulong()==1)return 10;
bool flag=0;
LL sum=0;
for(int i=1; i<=9; i++)
if(a[0].test(i)) {
sum=sum*10+i;
if(a[0].test(0)&&!flag)flag=1,sum*=10;
}
return sum;
}
} else if(a.size()==2&&!a[0].test(9)&&!a[1].test(0))up=8;
LL ans=LLONG_MAX/2;
for(int i=down; i<=up; i++) {
vector<bit> New;
bit v;
int now=i;
for(auto x:a) {
if(now==10) {
now=0;
New.push_back(v);
v.reset();
}
x.reset(now++);
v|=x;
}
New.push_back(v);
LL sum=Solve(New,!(i==0&&(a[0].test(0)||!zero)))*10+i;
ans=min(ans,sum);
}
return ans;
}
int n;
vector<bit> a;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
bit tmp;
tmp[Get_Int()]=1;
a.push_back(tmp);
}
LL ans=Solve(a,1);
printf("%lld\n",ans==0?10:ans);
return 0;
}
|
