agc029C Lexicographic constraints 题解
题意
有$n$个字符串,分别为$S_1,S_2,\dots,S_n$,$S_i$的长度为$A_i(1\le i\le n)$。给定$n$和$A$,求用最少个数的字符组成$S_1,S_2,\dots,S_n$,使得$S_1<S_2<\dots<S_n$(字典序)。输出这个数。
题解
贪心。对于每一个字符串,必须选择可选字符串中字典序最小的一个。
反证法:如果不选字典序最小的一个,答案肯定不会更优。
设每个字符为$0\sim\inf$中的一个数字。
所以
已知$S_{i-1}$如何求$S_i(2\le i\le n)$呢。
- $A_i>A_{i-1}$时,
- $A_i\le A_{i-1}$时,$S_i=S_{i-1}$的前$A_i$位,且$S_i$的最后一位加$1$,然后“进位”(如果当前位的值超出字符集的大小,就把当前位设置位$0$,前一位加$1$)。
这里需要知道字符集大小。考虑二分,因为字符集大小是满足单调性的。check
函数:“进位”时如果进到$-1$位了,就不可行。
证明:如果字符集大小位$m$,则字符集大小为$m+1$一定可行,而字符集大小为$m-1$不一定可行。
问题:字符串长度最大为$10^9$,不能维护整个字符串。
解法$1$:用一个map<int,int>
表示第几位放的是什么字符。观察发现:字符串中大部分的字符为$0$,所以只维护字符不为$0$位就可以了。
Tip: 需要特判$A_1<A_2<\dots<A_n$的情况,否则前$3$个点会TLE
。
解法$2$:同样,字符串中大部分的字符为$0$,可以用一个vector<pair<int,int> >
维护,<a,b>
表示字符为a
,出现了b
次的字符串,存在vector
里即可表达整个字符串。这个方法写起来会更麻烦一点。
程序
解法$1$
1 | // #pragma GCC optimize(2) |
解法$2$
1 | // #pragma GCC optimize(2) |