程序员进阶之算法练习（七十二）
题目1
题目链接 题目大意： 给出一个字符串，由小写字母组成； 现在Alice和Bob在玩游戏，轮流从字符串中移除一个子串，Alice先操作； Alice允许移除偶数长度子串，Bob允许移除奇数长度子串；（也允许不移除） 最终看每个人移除子串的分数总和，字母a是1分，b是2分、、、z是26分； 问最终谁能赢得游戏，以及胜者领先的分数；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤5⋅1e4) 每个样例一行，字符串𝑠 (1≤|𝑠|≤2⋅1e5)
输出： 每个样例一行，胜者和胜者领先的分数；
Examples input 5 aba abc cba n codeforces output Alice 2 Alice 4 Alice 4 Bob 14 Alice 93
题目解析： Alice先手，并且可以移除偶数字符串，那么字符串如果是偶数，Alice会移除所有字符； 如果是奇数，Alice只会留下1个字符串，要么是最左边，要么是左右边的字符，选择一个较小值； Bob后手，只能选择alice剩下的字符串。
class Solution {
static const int N = 201010;
string str;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> str;
int sum = 0;
for (int i = 0; i < str.length(); ++i) {
sum += str[i] - 'a' + 1;
}
if (str.length() % 2) {
int bob = min(str[0], str[str.length() - 1]) - 'a' + 1;
int alice = sum - bob;
cout << (alice > bob ? "Alice" : "Bob") << " " << abs(alice - bob) << endl;
}
else {
cout << "Alice " << sum << endl;
}
}
}
}
ac;题目2
题目链接 题目大意： 给出一个字符串，由小写字母组成； 如果这个字符串的所有子串都满足，构成字符串的字符数相差不超过1，则称这个字符串为完美字符串，比如说：
现在给出一个字符串，询问是否为完美字符串；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤2⋅1e4) 每个样例一行，字符串𝑠 (1≤|𝑠|≤2⋅1e5)
输出： 每个样例一行，如果是完美字符串则输出YES；如果不是完美字符串则输出NO；
Examples input 5 aba abb abc aaaaa abcba codeforces output YES NO YES YES NO
题目解析： 根据题目的要求，任意子串的字符数相差要在1以内，假设一共有k个不同字符； 那么从字符串中任意截取k长度的字符串，必然会由不同的字符组成，否则就会出现重复字符数>1，然后没出现的字符数位0，那么就不符合题目的要求； 并且由于可以任取，我们在[1, k]是由k个不同的字符构成，[2, k+1]也是k个不同的字符构成，由此可以推导出str[k+1] = str[1]，并由此类推，完美字符串必然是abcd abcd abc 这样的重复构成； 这样只需要检测字符串是否满足这个特性即可。
class Solution {
static const int N = 201010;
string str;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> str;
int sum = 0, v[26] = {0};
for (int i = 0; i < str.length(); ++i) {
int index = str[i] - 'a';
if (!v[index]) {
v[index] = 1;
++sum;
}
}
bool ans = true;
memset(v, 0, sizeof(v));
for (int i = 0; i < sum; ++i) {
int index = str[i] - 'a';
if (!v[index]) {
v[index] = 1;
}
else {
ans = false;
break;
}
}
if (ans) {
int pos = sum;
while (pos < str.length() && ans) {
for (int i = pos; i < str.length() && i < (pos + sum); ++i) {
if (str[i] != str[i - sum]) {
ans = 0;
break;
}
}
pos += sum;
}
if (ans) {
cout << "YES" << endl;
}
}
if (!ans) {
cout << "NO" << endl;
}
}
}
}
ac;题目3
题目链接 题目大意： 给出一个数字n，将数字n可以拆分成若干个整数之和； 现在想知道，有多少种拆分方法，要求拆分出来的整数都是回文数； （拆分出来的数字至少有一个不同，才算不同组合）
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1e4) 每个样例一行，整数 𝑛 (1≤𝑛≤4⋅1e4)
输出： 每个样例一行，输出不同的组合数字；结果可以对1e9+7取模；
Examples input 2 5 12 output 7 74
题目解析： 首先，把1到40000的回文数全部列出来，得到若干个回文数； 题目的要求是计算数字n拆分有多少种组合，我们只看数字1和2，就是将数字n拆成1和2的和； 这个和动态规划的经典题目类似：上n个台阶，每次有1步或者2步，最后有多少走法；
但是这个题目有点不同，就是对不同走法的判断，这里只有新增不同数字的情况，才认为是不同的；（1+2和2+1是一样的） 那么我们将回文数数字从小到大排列，然后判断每次回文数是否可以替换已有数字即可。 比如说： 考虑数字1，有dp[1]=1，dp[2]=1, dp[3]=1, dp[4]=1;（dp[i]表示数字i有多少总走法） 考虑数字2，有dp[1]=1，dp[2]=2, dp[3]=2, dp[4]=3；对于dp[2]，引入2的时候多了2=2的选择，同时还有原来的2=1+1；对于dp[4]，可以在dp[2]的基础上+2（新增2种选择4=2+2, 4=1+1+2），也可以不使用2，保留原来的4=1+1+1+1；
按照这种思路分析，可以得到状态转移方程还是dp[i]=dp[i]+dp[i-k]；（k是回文数）
class Solution {
static const int N = 40100;
static const int MOD = 1e9 + 7;
int dp[N];
bool check(int k) {
vector<int> vec;
while (k) {
vec.push_back(k % 10);
k /= 10;
}
for (int i = 0; i < vec.size() / 2; ++i) {
if (vec[i] != vec[vec.size() - i - 1]) {
return false;
}
}
return true;
}
public:
void solve() {
vector<int> vec;
for (int i = 1; i < N; ++i) {
if (check(i)) {
vec.push_back(i);
}
}
dp[0] = 1;
for (int j = 0; j < vec.size(); ++j) {
for (int i = vec[j]; i < N; ++i) {
dp[i] = ((lld)dp[i] + dp[i - vec[j]]) % MOD;
}
}
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << dp[n] << endl;
}
}
}
ac;题目4
题目链接 题目大意： 给出n个数字𝑎1,𝑎2,⋯,𝑎𝑛 ，要求构造一个长度不超过300的整数数组b，要求： 数组b中没有重复的元素； 数组b包括了数组a的所有数字； 数组b任意两个数字的差，其绝对值可以在数组b中找到相同数字。
输入： 第一行是整数t，表示有t个样例 (1≤𝑡≤50 ). 每个样例第一行是整数𝑛 (2≤𝑛≤100)； 第二行是n个整数 𝑎1,𝑎2,⋯,𝑎𝑛 (−100≤𝑎𝑖≤100)
输出： 如果有解，先输出YES，再输出整数k，表示有k个整数； (𝑛≤𝑘≤300) 𝑏1,𝑏2,⋯,𝑏𝑘 (−1e9≤𝑏𝑖≤1e9) 如果无解则输出NO；
Examples input 4 3 3 0 9 2 3 4 5 -7 3 13 -2 8 4 4 8 12 6
output yes 4 6 0 3 9 yEs 5 5 3 1 2 4 NO Yes 6 8 12 6 2 4 10
题目解析： 构造出来的数组b中不会存在负数，证明： 假设a[i]-a[j]，a[j]小于零，则必然需要一个比a[i]的数字a[k]，但是a[k]-a[j]又会产生更大的数字；
所以数组a中存在负数无解； 其他的情况，就用1、2、3、4到max来填充即可。
class Solution {
static const int N = 200010;
public:
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int maxNum = 0, minNum = 200;
for (int i = 1; i <= n; ++i) {
int k;
cin >> k;
maxNum = max(maxNum, k);
minNum = min(minNum, k);
}
if (minNum < 0) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl;
cout << maxNum + 1 << endl;
for (int i = 0; i <= maxNum; ++i) {
cout << i << " ";
}
cout << endl;
}
}
}
}
ac;题目5
题目链接 题目大意： 给出n个整数的数组，从左到右可以依次选择若干个整数，要求累加和在过程中始终不能为负数。 已知初始数字和为0，想知道最多能选择多少个数字。
输入： 第一行是整数 𝑛 (1≤𝑛≤2000) 第二行是n个整数𝑎1 , 𝑎2, ... ,𝑎𝑛 (−1e9≤𝑎𝑖≤1e9) 输出： 输出能选择的最多整数。
Examples input 6 4 -4 1 -3 1 -3 output 5
题目解析： 一种简单的策略： 遇到正的就吃，遇到负的就看当前能否吃下，能够吃则直接吃； 如果不能吃，则考虑是否将吃过的负数吐出来，如果存在某个负数的绝对值 比这个数字的绝对值要大，则可以把原来的负数吐出来，把这个数字吃进去；
可以用优先队列来记录负数，复杂度O（NlogN）；
class Solution {
static const int N = 200010;
public:
int a[N];
priority_queue<int, vector<int>, greater<int> > q;
public:
void solve() {
int t = 1;
while (t--) {
int n;
cin >> n;
while (!q.empty()) {
q.pop();
}
lld sum = 0, ans = 0;
for (int i = 0; i < n; ++i) {
int tmp;
scanf("%d", &tmp);
if (sum + tmp >= 0) {
++ans;
sum += tmp;
if (tmp < 0) {
q.push(tmp);
}
}
else {
int top = 0;
if (!q.empty()) {
top = q.top();
}
if (top < tmp) {
q.pop();
q.push(tmp);
sum = sum - top + tmp;
}
}
}
cout << ans << endl;
}
}
}
ac;腾讯云开发者
