Educational Codeforces Round 150 (Rated for Div. 2) C题，记录一下解法

Codeforces Edu 150 的 c 题

本文章用于记录一下我的写法，代码苦手，大佬轻喷（拜托拜托）

题目链接
c题题面

本题我们先分析一下题意：给出的字符串中，每一位字符代表一定的数值，如A代表1，B代表100等，如果该字符后面有比他更大的字符，则，这一位数取负值，我们可以最多修改1次，将其中一个字符修改为其他字符，使其总和取最大值。
数据范围 2e5，但它里面只含有5种字符ABCDE，所以我们可以对这五种字符进行枚举：

1、修改某个字符变大让其数值增大，并且我们不想让增大的这个值影响到前面，让前面的的数变负，所以我们操作最早出现的该字符。
2、修改某个字符变小，让其之前的某些小数恢复正值，此时我们当然想让他扩大更多前面的数，所以此种情况我们操作最后一个该字符。

（哇，那不就可以暴力算总和了吗！–>计算一次总和跑一次2e5，最多进行10次修改，跑十次也不会超时）

详细细节在代码注释里（要是有哪一步错了欢迎斧正！）

#include
#include
using namespace std;
#define ll long long
#define endl '\n'
#define INF 0x3f3f3f3f
#define PII pair<int,int>
//#define int long longconst int N = 2e5 + 5;int jia[5] = { 1,10,100,1000,10000 };//每个字母对应的值
int la[5], ra[5];//每种字符第一次与最后一次的位置
int a[N];	//将原字符串转为数字串存起来
int n;int sum1() {//计算总和函数int lb[5] = { 0 }, rb[5] = { 0 };//每种字符第一次与最后一次的位置for (int i = 1; i <= n; i++) {//找到该字符串中每种字符的 lb 与 rbif (lb[a[i]] == 0) {lb[a[i]] = i;}rb[a[i]] = i;}int sum = 0;for (int i = n; i >= 1; i--) {int flag = 1;//在后面有没有比它更大的for (int j = 4; j > a[i]; j--) {if (rb[j] > i) {flag = 0;//有，该位取负值break;}}if (flag)sum += jia[a[i]];else sum -= jia[a[i]];}return sum;
}void solve() {string s;cin >> s;n = s.size();s = "?" + s;for (int i = 0; i < 5; i++) {//初始化la[i] = 0;ra[i] = 0;}for (int i = 1; i <= n; i++) {a[i] = s[i] - 'A';if (la[a[i]] == 0) {la[a[i]] = i;}ra[a[i]] = i;}int max1 = sum1();//不修改，计算sumfor (int i = 0; i < 5; i++) {//要修改哪个字符？if (la[i] == 0)continue;//原串不含该字符，那当然改不了啦//第一个字符改大int step1 = a[la[i]];int step2 = a[ra[i]];for (int j = i + 1; j < 5; j++) {//要改为哪个字符？a[la[i]] = j;max1 = max(max1, sum1());}a[la[i]] = step1;//回溯（千万别把原串改了啊！）//最后一个字符改小for (int j = 0; j < i; j++) {a[ra[i]] = j;max1 = max(max1, sum1());}a[ra[i]] = step2;}cout << max1 << endl;
}signed main() {ios::sync_with_stdio(false);//关流操作，不解释啦cin.tie(0), cout.tie(0);int tt;cin >> tt;while (tt--) {solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！