Ranom Numbers

题面翻译

Ranom Number 是一个字符串，这个字符串只含字母 $\texttt A \sim \texttt E$。$\texttt{A}$ 的值是 $1$，$\texttt{B}$ 的值是 $10$，$\texttt{C}$ 的值是 $100$，$\texttt{D}$ 的值是 $1000$，$\texttt{E}$ 的值是 $10000$。

这个串的值按如下规则计算：如果一个字母的右侧没有值严格大于它的字母，那么它对串的值贡献为正的该字母的值，否则贡献为负的该字母的值。一个串的值就是把所有字母的贡献加起来。

例如，$\texttt{DAAABDCA}$ 的值是 $ 1000 - 1 - 1 - 1 - 10 + 1000 + 100 + 1 = 2088 $。

现在，给定一个 Ranom Number，你可以把它的不超过一个的字符改为其它的 $\texttt A \sim \texttt E$ 之间的字符，求你能得到的新 Ranom Number 的值最大可能是多少。

多组数据，输入串的总长度不超过 $2 \times 10^5$。

translated by 一扶苏一

题目描述

No, not "random" numbers.

Ranom digits are denoted by uppercase Latin letters from A to E. Moreover, the value of the letter A is $ 1 $ , B is $ 10 $ , C is $ 100 $ , D is $ 1000 $ , E is $ 10000 $ .

A Ranom number is a sequence of Ranom digits. The value of the Ranom number is calculated as follows: the values of all digits are summed up, but some digits are taken with negative signs: a digit is taken with negative sign if there is a digit with a strictly greater value to the right of it (not necessarily immediately after it); otherwise, that digit is taken with a positive sign.

For example, the value of the Ranom number DAAABDCA is $ 1000 - 1 - 1 - 1 - 10 + 1000 + 100 + 1 = 2088 $ .

You are given a Ranom number. You can change no more than one digit in it. Calculate the maximum possible value of the resulting number.

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The only line of each test case contains a string $ s $ ( $ 1 \le |s| \le 2 \cdot 10^5 $ ) consisting of uppercase Latin letters from A to E — the Ranom number you are given.

The sum of the string lengths over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single integer — the maximum possible value of the number, if you can change no more than one digit in it.

样例 #1

样例输入 #1

4
DAAABDCA
AB
ABCDEEDCBA
DDDDAAADDABECD

样例输出 #1

分析

写一下错误解法的经过

刚开始我的做法是, 维护一个前缀和, 表示从1到位置x内有多少个A, B...., 然后又因为一个数右边有比他大的数, 那这个数就负贡献, 那就可以用dp的方式 $O(n)$ 求出每个位置右边的最大值, 然后先求出初始字符串的值, 具体就是根据每个位置右边最大值就可以得知是正还是负贡献. 然后我们枚举每一个位置, 将它换成其他四种字母, 我一开始想到一个数变大会让左边一些数字变负, 反之就会让左边一些数字变正, 刚好符合前缀和的性质,

错就错在这里: 前缀和代表是位置1到x有多少个字母, 比如说左边有很多个C, 但是假设你把这个位置变小了, 假设从D变成C, 那之前的那些C就一定全部变正贡献吗? 要是这个位置的左边还有D, 还有E呢?

所以这个是错误的方法, 希望我可以从中学到一些经验, 下次不要再花这么多时间找bug

以下是正确解法

贪心, 感性理解

首先我们要明确, 修改某个位置只可能对这个位置的左边有影响, 对右边是没有影响的

设要修改的字母种类是 $P$

如果要把一个 $P$ 变大, 那么修改最左边的 $P$, 简单理解就是他所能影响的左区间最短, 因为变大肯定会让左边一些数由正变负, 我们肯定希望变负的数越少越好
如果要把 $P$ 变小, 那么修改最右边的 $P$, 因为 $P$ 变小肯定会让做左边的一些数由负变正, 我们肯定希望这样的数多一点, 就要让左区间尽可能大

那我们就可以只修改每种字母的这两个位置, 暴力枚举一下把这两个位置换成别的字母的时候的得分, 最后求最大值就可以了

一共5种字母, 每种字母可以换成其他的4种字母, 求每种情况的得分需要 $O(n)$, 总共也就是 $O(5\times4\times n)$

注意: 多例要清空

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll fp[5], la[5];
ll sta[5] = {1, 10, 100, 1000, 10000};

ll cal(string s)	//计算字符串代表的值
{
	ll maxn = 0, sum = 0;	//maxn是随着遍历的最大值值, 大于等于它就是正, 小于他就是负 
	for(int i = s.size() - 1; i >= 0; i--)
	{
		if(s[i] - 'A' >= maxn) sum += sta[s[i] - 'A'], maxn = s[i] - 'A';
		else sum -= sta[s[i] - 'A'];
	}
	return sum;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while(t--)
	{
		memset(fp, -1, sizeof fp), memset(la, -1, sizeof la);	//-1表示还没出现
		string s; cin >> s; 

		for(int i = 0; s[i]; i++)
		{
			if(fp[s[i] - 'A'] == -1) fp[s[i] - 'A'] = i;
			la[s[i] - 'A'] = i;
		}
		//暴力枚举即可
		ll ans = -3e9;
		for(int i = 0; i < 5; i++)	//i代表要改的字母种类 
		{
			for(int j = 0; j < 5; j ++)	//j代表要改成什么 
			{
				if(fp[i] != -1)
				{
					string tmp = s;
					tmp[fp[i]] = 'A' + j;
					ans = max(ans, cal(tmp));
				}
				if(la[i] != -1)
				{
					string tmp = s;
					tmp[la[i]] = 'A' + j;
					ans = max(ans, cal(tmp));
				}
			}
		}
		cout << ans << endl; 
	}
}

JZTXT

CF1841C