C: Ranom Numbers
本题最暴力的方法就是将每一个位置都改变取最大值,此方法是 O(n2) 的。
考虑是否可以只改变几个位置,答案是可以的。
定义:一个字母小是字典序小,大同理。
先给结论:
- 一个字母若要变大,只需要改这个字母最左边的即可。
- 一个字母若要变小,只需要改这个字母最右边的即可。
结论证明:
严谨证明较复杂,不过思路很清晰,只证结论1(A1 那一列永远不劣于 A2 那一列),结论2同理可证。
证:
就以字母 A 为例:
设中间的字母的最大值为 X ,A1,A2 可以变为以下几种情况:
先证 A1 的情况1是是不优于情况2的(以下都是简单文字描述):首先明确一点:改变一个字母只会影响从第一个字母到其的贡献。不管 A 一开始对整个字符串的贡献是正是负,变为情况2贡献都是增加了,且左的贡献该是负还是负该是正还是正,所以 A1 的情况1不优于情况2,A2 同理。
现在我们只需要知道 A1,A2 的后两种情况的关系即可。
为了阅读的方便,以下的“优于”和“更优”都是“不劣于”的意思,除“一定优于”外。
先证 A1,A2 的情况2是优于 A2 的情况2的:很显然两个情况对左的贡献是相同的,并且两个 A 字母上升到 X 对整体的贡献也是相同的,意思只有中间是不同的,那么中间大于 A 小于 X 的字母的贡献就会变成负号,得证。A1 的情况3是优于 A2 的情况3同理。
再证如果 A1 的情况2是比 A1 的情况3更优的,那么 A2 的情况2也比 A2 的情况3更优:想象一下如果 A1 的情况2是比 A1 的情况3更优的,其实就是左中字母 X 较多(多多少?只需感性理解这个就行,其实就是从情况2到3多出来的 A1 自身上升的贡献比不上左中字母 X 提供的负贡献),同理若连 A1 和中间的区域的负贡献都不看,A2 的情况2也比 A2 的情况3更优。
最后证 A1 的情况3比 A2 的情况2更优(也是本题较难证明的一部分):首先证这个的条件是就 A1 的情况2,3而言3更优和 A2 的情况2,3而言2更优同时满足。由条件1可知(以下都是同上的感性理解):左中字母 X 提供的负贡献比不上(或者说不大于)从情况2到3多出来的 A1 自身上升的贡献。就先假设 X=B,则再假设 >X=C,你没看错就是 >X,易知 C=10B=B+9B ,B 是 情况2的贡献,9B 可以形象的成为 Δ 。由条件1可知左中的 B 的个数小于等于9,就设 A=1,B=10⋯ 以此类推。因此 A1 的情况3的贡献 ≥B−A=10−1=9。先在考虑 A2 的情况2,因为中间部分可能会有小于 B 的,所以 A2 的情况2的贡献 ≤B−A=10−1=9,X 为其他字母的时候也同理。所以 A1 的情况3比 A2 的情况2更优。
整理上述4个证明可知:A1,A2 的情况1是是不优于情况2的,所以只需要知道 A1,A2 的后两种情况的关系即可。又知道 A1,A2 的情况2和3是分别优于 A2 的情况2和3的,又知道了如果 A1 的情况2是比 A1 的情况3更优的,那么 A2 的情况2也比 A2 的情况3更优,最后知道了A1 的情况3比 A2 的情况2更优,就证毕了!
代码实现:
-
计算整个字符串的值,从后往前。
-
为了方便,因为已经知道了两条结论,所以直接对10个位置进行更换为 A 到 E 的暴力修改。
核心代码:
const int N = 2e5 + 10;
char str[N];
int ch[5] = {1, 10, 100, 1000, 10000};
int ans, L[5], R[5];
void init(){
ans = -inf;
mms(L, 0), mms(R, 0);
}
int calc(int len){
int res = 0;
char maxc = 'A';
pre(i, len, 1){
int c = str[i] - 'A';
if(maxc > str[i]) res += -ch[c];
else{
maxc = str[i];
res += ch[c];
}
}
return res;
}
int main(){
int T; rd(T);
while(T--){
sf("%s", str + 1);
int len = strlen(str + 1);
init();
rep(i, 1, len){
if(!L[str[i] - 'A']) L[str[i] - 'A'] = i;
R[str[i] - 'A'] = i;
}
rep(i, 0, 4){ //替换前
if(!R[i]) continue; //LR都行
rep(j, 0, 4){ //替换后
//替换L
char temp = str[L[i]];
str[L[i]] = 'A' + j;
ans = max(ans, calc(len));
str[L[i]] = temp;
//替换R
temp = str[R[i]];
str[R[i]] = 'A' + j;
ans = max(ans, calc(len));
str[R[i]] = temp;
}
}
prf("%d\n", ans);
}
return 0;
}
如有帮助点点赞关关注呗,谢谢啦!
求管理员大大给过/可怜。