題目1
題目鏈接
題目大意：
有3個(gè)字符a/b/c，排成一行；
現(xiàn)在可以選擇兩個(gè)字符，交換對(duì)應(yīng)的位置；
上述操作最多只能執(zhí)行一次，問能否得到abc的順序。
輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤6)
每個(gè)樣例一行，字符串a(chǎn)bc的隨機(jī)排列；
輸出：
每個(gè)樣例一行，如果有解則輸出YES，無解則輸出NO；
Examples
input
6
abc
acb
bac
bca
cab
cba
output
YES
YES
YES
NO
NO
YES
題目解析：
將字符串與abc進(jìn)行匹配，計(jì)算得到一共有x個(gè)位置的字符匹配；
如果x=3，則全部字符都匹配了，不需要操作；
如果x=1，則表示有2個(gè)字符不匹配，那么交換這兩個(gè)字符；
其他情況則直接輸出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
題目鏈接
題目大意：
給出一個(gè)字符串s，現(xiàn)在可以進(jìn)行以下操作：
1、將某個(gè)子串AB，替換成子串BC；
2、將某個(gè)子串BA，替換成子串CB；
現(xiàn)在想知道，最多可以對(duì)字符串進(jìn)行多少次操作。
輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤10000)
每個(gè)樣例一行，字符串?? ，只有字符A和B (1≤|??|≤2?1e5)
輸出：
每個(gè)樣例一行，輸出可以最多可以執(zhí)行的操作數(shù)。
Examples
input
8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA
output
2
1
3
1
6
2
0
0
題目解析：
假設(shè)原來字符串是xxxAByyy，進(jìn)行一次操作1之后，會(huì)變成xxxBCyyy；
容易知道，字符C會(huì)成為阻斷，yyy無法與C形成搭配，但是xxxB仍然可能會(huì)產(chǎn)生操作1，比如說AAAB這樣的字符串就可以連續(xù)執(zhí)行操作1；
同理，BAAA可以連續(xù)執(zhí)行操作2；
那么將連續(xù)的A聚合起來，題目的要求，就變成如何分配B給連續(xù)A，使得最終的結(jié)果最大；
對(duì)于 ABABABA的這樣字符，那么從中選擇一個(gè)最小的A即可。
但是對(duì)于BABA、ABBA這樣的字符呢？
為了方便計(jì)算，我們可以用字符B來分割原字符串。
如果遇到ABBA這樣的字符，我們假設(shè)在BB中間插入一個(gè)A(0)的字符，那么整個(gè)算法就完善起來：
整個(gè)字符串都可以抽象成這樣的的字符組合：Ax B Ax B Ax ..... （Ax表示有連續(xù)x個(gè)字符A）
比如說BAABA就可以表示為 [A0,B,A2,B,A1]，容易知道最終A0是最小，那么結(jié)果就是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個(gè)數(shù)字1，每次可以選擇2個(gè)或者以上相同的數(shù)字，將這些數(shù)字移除，然后添加這些數(shù)字的和；
比如說[1, 1, 1, 1]，可以選擇2個(gè)1合并，得到[2, 1, 1]；
現(xiàn)在Alice和Bob輪流進(jìn)行操作，Alice先手；
如果遇到?jīng)]有2個(gè)相同的數(shù)字，那么該輪選手獲勝。
輸入整數(shù)n，表示有n個(gè)數(shù)字1；
輸出Alice或者Bob，表示獲勝者；
輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤99)
每個(gè)樣例一行，整數(shù)?? (2≤??≤200)
輸出：
每個(gè)樣例一行，輸出獲勝者。
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
...
這里比較容易得到一個(gè)必勝策略，只需要拆分為 [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
題目鏈接
題目大意：
某個(gè)數(shù)組被定義為beautiful，只要滿足：
將數(shù)組前面連續(xù)的一段（長(zhǎng)度可以是0）切下來，拼接到數(shù)組最后面，數(shù)組最終是非遞減的，那么數(shù)組是beautiful。
現(xiàn)在有一個(gè)數(shù)組，初始化狀態(tài)為空；
依次給出n個(gè)整數(shù)，如果某個(gè)整數(shù)添加到數(shù)組末尾后數(shù)組是beautiful，那么該整數(shù)必須添加到數(shù)組末尾，否則放棄；
問最終由有哪些數(shù)字會(huì)添加到數(shù)組中。
輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤10000)
每個(gè)樣例2行
第一行，整數(shù)?? (1≤??≤2e5)
第二行，n個(gè)整數(shù)??1,??2,…???? (0≤????≤1e9 )
輸出：
每個(gè)樣例一行，由01組成長(zhǎng)度為n的字符串；第i個(gè)字符為1表示第i個(gè)字符會(huì)被添加到數(shù)組，為0則表示不會(huì)；
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
題目解析：
按照題目的要求，在過程中并沒有決策的空間，那么關(guān)鍵點(diǎn)就是如何快速得到這個(gè)結(jié)果。
1、當(dāng)a[i+1] >= a[i]，繼續(xù)保持；
2、當(dāng)a[i+1] < a[i]，首次出現(xiàn)就要進(jìn)行分割，a[i+1]要放在數(shù)組末尾，如果a[1] >= a[i]，那么a[i]可行；
接下來要滿足，所有數(shù)字大于等于a[i]并且小于等于a[1]；
這里犯了一次低級(jí)錯(cuò)誤 cur = a[i]寫成了cur = ans[i]；
導(dǎo)致出現(xiàn)幾次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
題目鏈接
題目大意：
有長(zhǎng)度為n的字符串s，由字符A/B/C/D/E組成；
現(xiàn)在將字符串按照下述規(guī)則轉(zhuǎn)成數(shù)字：
1、A、B、C、D、E分別代表數(shù)字1、10、100、1000、10000；
2、如果某個(gè)字符，右邊的位置存在一個(gè)字符比當(dāng)前字符更大，則添加負(fù)號(hào)；（比如說AB，A的右邊存在B比當(dāng)前字符A大，那么A代表-1）
將字符串每個(gè)位置數(shù)字累加，得到字符串的和；
比如說：
ABB = -1 + 10 + 10 = 19；
BBA = 10 + 10 + 1 = 21；
現(xiàn)在可以修改字符串s中的一個(gè)字符，替換為A~E中的任意一個(gè)字符；
問，字符串的和最大為多少？
輸入：
第一行，整數(shù)?? 表示t個(gè)樣例 ?? (1≤??≤10000)
每個(gè)樣例一行，字符串??(1≤|??|≤2?105)
輸出：
每個(gè)樣例一行，輸出修改后最大的字符串和；
Examples
input
4
DAAABDCA
AB
ABCDEEDCBA
DDDDAAADDABECD
output
11088
10010
31000
15886
題目解析：
還是從簡(jiǎn)單開始思考。
只有單個(gè)字母時(shí)，直接選擇替換為E，收益為E與當(dāng)前字母的差距；
當(dāng)有兩個(gè)字母時(shí)，就需要考慮特殊情況，正常AB這樣的組合，還是會(huì)選擇替換成EB；但是當(dāng)BA這樣的組合時(shí)，繼續(xù)選A就會(huì)導(dǎo)致B變成負(fù)數(shù)，此時(shí)除了正收益，還有額外的負(fù)收益；
那么就需要統(tǒng)一計(jì)算，負(fù)收益也比較容易計(jì)算：替換后，所在位置前，原來ABCD字母價(jià)值為正的部分；（注意，如果原來就為負(fù)，沒有負(fù)收益）
這樣從左到右枚舉整個(gè)數(shù)組即可得到最優(yōu)解。
但是，自己還是犯了一個(gè)錯(cuò)誤：主觀判斷，無法證明。
在分析樣例的時(shí)候，還是太過急，從兩個(gè)字母直接推出來最優(yōu)解，情況還是不夠豐富。
因?yàn)樾薷淖帜赋诵薷臑樽畲?，還可以修改為較小值。
這里既然要枚舉每個(gè)位置的值，是不是也可以考慮枚舉每個(gè)位置修改為A/B/C/D/E的值？
這樣可以解決DDDDDDDDDDDDDDE這樣的case，我們可以修改為DDDDDDDDDDDDDDD。
所以，更嚴(yán)謹(jǐn)?shù)淖龇?，我們?yīng)該枚舉每一個(gè)位置分別對(duì)應(yīng)修改為A/B/C/D/E的情況，但是這樣的復(fù)雜度是O(N^2），明顯超出題目限制；
但是分析其中冗余的部分，由貪心思想我們可以發(fā)現(xiàn)，假如一個(gè)字符D要修改，要么就是第一個(gè)D，要么是最后一個(gè)D；
為什么呢？
由最開始的替換為E的思路，這是從博取正收益的角度去出發(fā)，在這種情況下，假設(shè)要修改的是字符C，那么越往左的字符C，整體收益是越大的；
假如是我們從減少負(fù)收益的角度去出發(fā)，假設(shè)我們要修改是字符E，那么越往右的字符E，整體收益是越大的；
所以我們只要最開始出現(xiàn)和最后出現(xiàn)ABCDE位置，一共10個(gè)位置，每個(gè)位置再枚舉修改為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;
