题目1
一个子序列的消除规则如下:
- 在某一个子序列中，如果'1'的左边有'0'，那么这两个字符 -> "01"可以消除
- 在某一个子序列中，如果'3'的左边有'2'，那么这两个字符 -> "23"可以消除
- 当这个子序列的某个部分消除之后，认为其他字符会自动贴在一起，可以继续寻找消除的机会
比如，某个子序列"0231"，先消除掉"23"，那么剩下的字符贴在一起变成"01"，继续消除就没有字符了
如果某个子序列通过最优良的方式，可以都消掉，那么这样的子序列叫做“全消子序列”
一个只由'0'、'1'、'2'、'3' 四种字符组成的字符串str，可以生成很多子序列，返回“全消子序列”的最大长度
字符串str长度 <= 200
思路
范围尝试模型。L到R上，返回全消子序列的最大长度。那这个函数就是f(L, R)的形式。两种可能，一种是不考虑L上的字符，一种是必须考虑L上的字符。
先说不考虑：不考虑的话就是返回f(L + 1, R)
考虑：首先看L位置上是否是'1'或者'3'，如果是，因为必须考虑那么这种情况下全消子序列的长度就是0。如果L位置上是否是'0'或者'2'，那么L+1 ~ R范围上有若干个跟L位置字符配对的字符，假设这些位置是i，每一个这样的字符都可能消掉，所以都调一次递归：f(L + 1, i - 1) + 2(L与i位置可以消掉，所以+2) + f(i + 1, R) ，拿到最大的结果，与第一种不考虑L位置对比，返回最大的。
代码：
int process(string &str, int L, int R)
{
if (L >= R)
{
return 0;
}
if (L + 1 == R)
{
return (str[L] == '0' && str[R] == '1') || (str[L] == '2' && str[R] == '3') ? 2 : 0;
}
int p1 = process(str, L + 1, R);
if (str[L] == '1' || str[L] == '3')
{
return p1;
}
char find = str[L] == '0' ? '1' : '3';
int p2 = 0;
for (int i = L + 1; i <= R; i++)
{
if (str[i] == find)
{
p2 = max(p2, process(str, L + 1, i - 1) + 2 + process(str, i + 1, R));
}
}
return max(p1, p2);
}
int main()
{
string str;
cin >> str;
cout << process(str, 0, str.size() - 1) << endl;
return 0;
}
题目2
给定一个只由0和1组成的字符串S，假设下标从1开始，规定i位置的字符价值V[i]订计算方式如下:
- i == 1时，V[i]=1
- i > 1时，如果S[i] != S[i-1]，V[i] = 1
- i > 1时，如果S[i] == S[i-1]，V[i] = V[i-1] + 1
你可以随意删除S中的字符，返回整个S的最大价值
字符串长度<=5000
思路
从左到右的尝试模型，当前位置有两种可能性，保留当前位置和删除当前位置。将上一个位置的数字和之前积累的价值传给当前位置。
保留当前位置：当前位置的价值就是，如果上一个位置的数字与当前位置数字一样，则当前数字的价值为V[i-1] + 1，否则就为1
删除当前位置：当前位置的价值就是V[i-1]
两种可能性取最大
代码
int process(string str, int index, char lastNum, int lastValue)
{
if (index == str.size())
{
return 0;
}
int curValue = str[index] == lastNum ? lastValue + 1 : 1;
int p1 = process(str, index + 1, str[index], curValue);
int p2 = process(str, index + 1, lastNum, lastValue);
return max(p1, p2);
}
int main()
{
string str;
cin >> str;
cout << process(str, 0, '0', 0);
return 0;
}
题目3
给定一个字符串str，和一个正数k
返回长度为k的所有子序列中，字典序最大的子序列
思路
单调栈。从左到右依次进单调栈，当前字符的字典序小于等于栈顶字符的字典序才能进栈，否则一直弹出到栈空或能进栈为止。下面就会出现两种可能性：
- 遍历完后栈内字符数量大于等于k个，那么从栈底开始往上数k个字符，这k个就是最后的答案。
- 遍历到i位置，单调栈的size() + str.size() - i + 1 的结果等于k了，那证明如果再遍历下去可能最后遍历完的时候，单调栈内的字符数量会小于k，此时不再弹出或遍历了，直接将栈内所有字符与包括i位置往后的所有字符(加起来刚好等于k个)返回即可。
代码
int main()
{
string str;
int k;
cin >> str;
cin >> k;
vector<char> stack(str.size());
int size = 0;
for (int i = 0; i < str.size(); i++)
{
while (size > 0 && stack[size - 1] < str[i] && size + str.size() - i> k)
{
size--;
}
if (size + str.size() - i == k)
{
string ans = "";
for (int j = 0; j < size; j++)
{
ans += stack[j];
}
ans += str.substr(i, str.size() - i);
cout << ans << endl;
return 0;
}
stack[size++] = str[i];
}
string ans = "";
for (int i = 0; i < k; i++)
{
ans += stack[i];
}
cout << ans << endl;
return 0;
}
题目4
给定一个数组arr，当拿走某个数a的时候，其他所有的数都+a
请返回最终所有数都拿走的最大分数
比如: [2, 3, 1]
当拿走3时，获得3分，数组变成[5, 4]
当拿走5时，获得5分，数组变成[9]
当拿走9时，获得9分，数组变成[ ]
这是最大的拿取方式，返回总分17
思路
从大到小拿即可
代码
int main()
{
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr.begin(), arr.end());
int ans = 0;
for (int i = arr.size() - 1; i >= 0; i--)
{
ans += (ans * 2) + arr[i]; //总结出的公式
}
cout << ans << endl;
return 0;
}
题目5
把一个01字符串切成多个部分，要求每一部分的0和1比例一样，同时要求尽可能多的划分
比如：01010101
01、01、01、01 这是一种切法，0和1比例为1 : 1
0101、0101 也是一种切法，0和1比例为1 : 1
两种切法都符合要求，但是那么尽可能多的划分为第一种切法，部分数为4
比如：00001111
只有一种切法就是00001111整体作为一块，那么尽可能多的划分，部分数为1
给定一个01字符串str，假设长度为N，要求返回一个长度为N的数组ans
其中ans[i] = str[0...i]这个前缀串，要求每一部分的0和1比例一样，同时要求尽可能多的划分下，部分数是多少
输入：str = "010100001"
输出：ans = [1, 1, 1, 2, 1, 2, 1, 1, 3]
思路
假设当前前缀0和1的比例为a : b，那么它分的的最多的份数的每一份的0和1的比例都为a : b。假设当前前缀是下标为0 ~ j，之前的某个前缀的0和1的比例也为a : b，它的下标是0 ~ i，那么i + 1 ~ j的比例也一定是a : b(数学方法可以证明)，那么如果前面有n个前缀拥有a : b的比例，当前前缀最多能分到的份数就是n + 1份，所以就看当前前缀的a : b，在之前的前缀中出现过多少次。可以利用哈希表，每到一个前缀，就储存这个前缀的0 1比。
代码
int gcd(int a, int b)
{
if (a < b)
{
int tmp = a;
a = b;
b = tmp;
}
if (b == 0)
{
return a;
}
return gcd(b, a % b);
}
int main()
{
string str;
cin >> str;
int zeros = 0;
int ones = 0;
unordered_map<int, unordered_map<int, int>> pre;
vector<int> ans(str.size());
for (int i = 0; i < str.size(); i++)
{
if (str[i] == '0')
{
zeros++;
}
else
{
ones++;
}
if (zeros == 0 || ones == 0)
{
ans[i] == i + 1; //当前前缀全是1或全是0，那么每个字符分成一份就是答案
}
else
{
int g = gcd(zeros, ones); //得到a与b的最大公因数
int a = zeros / g; //分子
int b = ones / g; //分母
if (pre.count(a) == 0)
{
pre[a][0];
}
if (pre[a].count(b) == 0)
{
pre[a][b] = 1;
}
else
{
pre[a][b]++;
}
ans[i] = pre[a][b];
}
}
for (int i = 0; i < ans.size(); i++)
{
cout << ans[i] << endl;
}
return 0;
}
题目6
[0, 4, 7]：0表示这里石头没有颜色，如果变红代价是4，如果变蓝代价是7
[1, X, X]：1表示这里石头已经是红，而且不能改颜色，所以后两个数X无意义
[2, X, X]：2表示这里石头已经是蓝，而且不能改颜色，所以后两个数X无意义
颜色只可能是0、1、2，代价一定 >= 0
给你一批这样的小数组，要求最后必须所有石头都有颜色，且红色和蓝色一样多，返回最小代价
如果怎么都无法做到所有石头都有颜色、且红色和蓝色一样多，返回-1
思路
首先如果小数组的数量是奇数个，则返回-1。然后遍历所有数组，找到红色石头、蓝色石头和没有颜色石头的个数，就可以确定没有颜色的石头多少个需要分配给红色，多少个需要分配给蓝色。假设a个石头需要变成红色，b个需要变成蓝色。先把所有无色石头都变成红色(或者蓝色)，然后统计代价，这时候看其中哪b个石头变成蓝色减少的代价最多，即数组下标1减去下标2的值最大的b个，把它们变成蓝色再统计新的代价即可。
代码
int main()
{
int n;
cin >> n;
vector<vector<int>> arr(n, vector<int>(3));
int red = 0;
int blue = 0;
int sum = n;
int ans = 0;
vector<int> redToBlue(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 3; j++)
{
cin >> arr[i][j];
if (j == 0)
{
if (arr[i][j] == 1)
{
red++;
}
else if (arr[i][j] == 2)
{
blue++;
}
}
if (j == 1)
{
ans += arr[i][1];
}
if (j == 2)
{
redToBlue[i] = arr[i][1] - arr[i][2];
}
}
}
if ((sum & 1) != 0 || blue > (sum / 2) || red > (sum / 2))
{
cout << -1 << endl;
return 0;
}
sort(redToBlue.begin(), redToBlue.end());
int needs = sum / 2 - blue;
for (int i = redToBlue.size() - 1; i >= redToBlue.size() - needs; i--)
{
ans -= redToBlue[i];
}
cout << ans << endl;
return 0;
}