题目1
题目链接
题目大意：
有3个字符a/b/c，排成一行；
现在可以选择两个字符，交换对应的位置；
上述操作最多只能执行一次，问能否得到abc的顺序。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤6)
每个样例一行，字符串abc的随机排列；
输出：
每个样例一行，如果有解则输出YES，无解则输出NO；
Examples
input
6
abc
acb
bac
bca
cab
cba
output
YES
YES
YES
NO
NO
YES
题目解析：
将字符串与abc进行匹配，计算得到一共有x个位置的字符匹配；
如果x=3，则全部字符都匹配了，不需要操作；
如果x=1，则表示有2个字符不匹配，那么交换这两个字符；
其他情况则直接输出NO；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
char s[10];
cin >> s;
int cnt = 0;
for (int i = 0; i < 3; ++i) if (s[i] == 'a' + i) ++cnt;
cout << ((cnt == 1 || cnt == 3) ? "YES":"NO") << endl;
}
}
}
ac;
题目2
题目链接
题目大意：
给出一个字符串s，现在可以进行以下操作：
1、将某个子串AB，替换成子串BC；
2、将某个子串BA，替换成子串CB；
现在想知道，最多可以对字符串进行多少次操作。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例一行，字符串𝑠 ，只有字符A和B (1≤|𝑠|≤2⋅1e5)
输出：
每个样例一行，输出可以最多可以执行的操作数。
Examples
input
8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA
output
2
1
3
1
6
2
0
0
题目解析：
假设原来字符串是xxxAByyy，进行一次操作1之后，会变成xxxBCyyy；
容易知道，字符C会成为阻断，yyy无法与C形成搭配，但是xxxB仍然可能会产生操作1，比如说AAAB这样的字符串就可以连续执行操作1；
同理，BAAA可以连续执行操作2；
那么将连续的A聚合起来，题目的要求，就变成如何分配B给连续A，使得最终的结果最大；
对于 ABABABA的这样字符，那么从中选择一个最小的A即可。
但是对于BABA、ABBA这样的字符呢？
为了方便计算，我们可以用字符B来分割原字符串。
如果遇到ABBA这样的字符，我们假设在BB中间插入一个A(0)的字符，那么整个算法就完善起来：
整个字符串都可以抽象成这样的的字符组合：Ax B Ax B Ax ..... （Ax表示有连续x个字符A）
比如说BAABA就可以表示为 [A0,B,A2,B,A1]，容易知道最终A0是最小，那么结果就是0+2+1-0=3；
class Solution {
static const int N = 201010;
string s;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> s;
int n = s.length();
int cur = 0;
vector<int> vec;
for (int i = 0; i < n; ++i) {
if (s[i] == 'B') {
vec.push_back(cur);
cur = 0;
}
else {
++cur;
}
}
if (cur != 0 || s[n - 1] == 'B') {
vec.push_back(cur);
}
sort(vec.begin(), vec.end());
int ans = 0;
for (int i = 0; i < vec.size(); ++i) {
ans += vec[i];
}
ans -= vec[0];
cout << ans << endl;
}
}
}
题目3
题目链接
题目大意：
Alice和Bob在玩游戏。
初始有n个数字1，每次可以选择2个或者以上相同的数字，将这些数字移除，然后添加这些数字的和；
比如说[1, 1, 1, 1]，可以选择2个1合并，得到[2, 1, 1]；
现在Alice和Bob轮流进行操作，Alice先手；
如果遇到没有2个相同的数字，那么该轮选手获胜。
输入整数n，表示有n个数字1；
输出Alice或者Bob，表示获胜者；
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤99)
每个样例一行，整数𝑛 (2≤𝑛≤200)
输出：
每个样例一行，输出获胜者。
Examples
input
2
3
6
output
Bob
Alice
题目解析：
先从小样例入手：
n=2，[1, 1] = B
n=3，1,1,1 = B
n=4，1,1,1,1 = B
n=5，1,1,1,1,1 = 1,1 + 3 = A
n=6，1,1,1,1,1,1 = 1,1 + 4 = A
...
这里比较容易得到一个必胜策略，只需要拆分为 [1,1] + (n-2) = A，并且n-2比2大即可。
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << (n > 4 ? "Alice" : "Bob") << endl;
}
}
}
ac;
题目4
题目链接
题目大意：
某个数组被定义为beautiful，只要满足：
将数组前面连续的一段（长度可以是0）切下来，拼接到数组最后面，数组最终是非递减的，那么数组是beautiful。
现在有一个数组，初始化状态为空；
依次给出n个整数，如果某个整数添加到数组末尾后数组是beautiful，那么该整数必须添加到数组末尾，否则放弃；
问最终由有哪些数字会添加到数组中。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行，整数𝑛 (1≤𝑛≤2e5)
第二行，n个整数𝑎1,𝑎2,…𝑎𝑛 (0≤𝑎𝑖≤1e9 )
输出：
每个样例一行，由01组成长度为n的字符串；第i个字符为1表示第i个字符会被添加到数组，为0则表示不会；
Examples
input
3
9
3 7 7 9 2 4 6 3 4
5
1 1 1 1 1
5
3 2 1 2 3
output
111110010
11111
11011
题目解析：
按照题目的要求，在过程中并没有决策的空间，那么关键点就是如何快速得到这个结果。
1、当a[i+1] >= a[i]，继续保持；
2、当a[i+1] < a[i]，首次出现就要进行分割，a[i+1]要放在数组末尾，如果a[1] >= a[i]，那么a[i]可行；
接下来要满足，所有数字大于等于a[i]并且小于等于a[1]；
这里犯了一次低级错误 cur = a[i]写成了cur = ans[i]；
导致出现几次Wrong Answer，后面名字要有差异。
class Solution {
static const int N = 201010;
int a[N], ans[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
bool rev = 0;
int cur = 0;
memset(ans, 0, sizeof(ans));
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (i == 0) {
ans[i] = 1;
cur = a[i];
}
else {
if (rev) {
if (a[i] >= cur && a[i] <= a[0]) {
cur = a[i];
ans[i] = 1;
}
}
else {
// 0 4 15 18 4 10 12 8 13 8 15 0 14 12 10 12 10 14 13
if (a[i] >= cur) {
ans[i] = 1;
cur = a[i];
}
else if (i == 1 || a[0] >= a[i]){
cur = a[i];
rev = 1;
ans[i] = 1;
}
}
}
}
for (int i = 0; i < n; ++i) putchar('0' + ans[i]);
puts("");
}
}
}
题目5
题目链接
题目大意：
有长度为n的字符串s，由字符A/B/C/D/E组成；
现在将字符串按照下述规则转成数字：
1、A、B、C、D、E分别代表数字1、10、100、1000、10000；
2、如果某个字符，右边的位置存在一个字符比当前字符更大，则添加负号；（比如说AB，A的右边存在B比当前字符A大，那么A代表-1）
将字符串每个位置数字累加，得到字符串的和；
比如说：
ABB = -1 + 10 + 10 = 19；
BBA = 10 + 10 + 1 = 21；
现在可以修改字符串s中的一个字符，替换为A~E中的任意一个字符；
问，字符串的和最大为多少？
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例一行，字符串𝑠(1≤|𝑠|≤2⋅105)
输出：
每个样例一行，输出修改后最大的字符串和；
Examples
input
4
DAAABDCA
AB
ABCDEEDCBA
DDDDAAADDABECD
output
11088
10010
31000
15886
题目解析：
还是从简单开始思考。
只有单个字母时，直接选择替换为E，收益为E与当前字母的差距；
当有两个字母时，就需要考虑特殊情况，正常AB这样的组合，还是会选择替换成EB；但是当BA这样的组合时，继续选A就会导致B变成负数，此时除了正收益，还有额外的负收益；
那么就需要统一计算，负收益也比较容易计算：替换后，所在位置前，原来ABCD字母价值为正的部分；（注意，如果原来就为负，没有负收益）
这样从左到右枚举整个数组即可得到最优解。
但是，自己还是犯了一个错误：主观判断，无法证明。
在分析样例的时候，还是太过急，从两个字母直接推出来最优解，情况还是不够丰富。
因为修改字母除了修改为最大，还可以修改为较小值。
这里既然要枚举每个位置的值，是不是也可以考虑枚举每个位置修改为A/B/C/D/E的值？
这样可以解决DDDDDDDDDDDDDDE这样的case，我们可以修改为DDDDDDDDDDDDDDD。
所以，更严谨的做法，我们应该枚举每一个位置分别对应修改为A/B/C/D/E的情况，但是这样的复杂度是O(N^2），明显超出题目限制；
但是分析其中冗余的部分，由贪心思想我们可以发现，假如一个字符D要修改，要么就是第一个D，要么是最后一个D；
为什么呢？
由最开始的替换为E的思路，这是从博取正收益的角度去出发，在这种情况下，假设要修改的是字符C，那么越往左的字符C，整体收益是越大的；
假如是我们从减少负收益的角度去出发，假设我们要修改是字符E，那么越往右的字符E，整体收益是越大的；
所以我们只要最开始出现和最后出现ABCDE位置，一共10个位置，每个位置再枚举修改为A/B/C/D/E的最大收益即可。
class Solution {
static const int N = 201010;
lld a[N];
char s[N];
lld val[5] = {1, 10, 100, 1000, 10000};
lld getSum(int n) {
lld ret = 0;
char cur = 0;
for (int i = n; i > 0; --i) {
a[i] = val[s[i] - 'A'];
if (s[i] < cur) a[i] *= -1;
cur = max(cur, s[i]);
ret += a[i];
}
return ret;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
scanf("%s", s+1);
int n = strlen(s+1);
int posFirst[5] = {0}, posLast[5] = {0};
for (int i = 1; i <= n; ++i) {
int idx = s[i] - 'A';
if (!posFirst[idx]) posFirst[idx] = i;
posLast[idx] = i;
}
lld ans = -0xfffffffffff;
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
if (!posFirst[i]) continue;;
char c = 'A' + j;
char tmp = s[posFirst[i]];
s[posFirst[i]] = c;
ans = max(ans, getSum(n));
s[posFirst[i]] = tmp;
}
}
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
if (!posLast[i]) continue;;
char c = 'A' + j;
char tmp = s[posLast[i]];
s[posLast[i]] = c;
ans = max(ans, getSum(n));
s[posLast[i]] = tmp;
}
}
cout << ans << endl;
}
}
}
ac;
