程序员进阶之算法练习（九十三）
题目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;