目录
A. Subtle Substring Subtraction
?B. A Perfectly Balanced String?
A. Subtle Substring Subtraction
题目链接：
https://codeforces.com/contest/1673/problem/A
题面：
题意：
给定一个字符串，Alice可以选择长度为偶数的字串进行删除(可以为空)，Bob可以选择长度为奇数的字串进行删除，删除一个字串可以获得的分数为s[i] - 'a' + 1，Alice先手，不会有平局情况，最后输出谁分数高已经最大得分差
思路：
Alice先手并且可以选择偶数长度，那么Alice最多只会留下1个字符给Bob，而且要么是最后一个，要么是第一个。我们可以先求出总得分，然后判断总串的长度的奇偶性，如果是偶数就是总分：0，否则就是求min(第一个的得分，最后一个的得分)，sum - min : min
代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
string s;
cin >> s;
int sum = 0;
int len = s.length();
for(int i = 0; i < len; i++){
sum += s[i] - 'a' + 1;
}
int num = 0;
if(len & 1){
num = min(s[0] - 'a' + 1, s[len - 1] - 'a' + 1);
sum -= num;
}
if(sum > num){
cout << "Alice ";
}else{
cout << "Bob ";
}
cout << abs(sum - num) << endl;
}
return 0;
}?B. A Perfectly Balanced String?
题目链接：
题面：
?题意：
用自己的话写不出来，看翻译好了
思路：
如果一个字串里面包含两个相同的字母，那么这两个相同字母之间一定要包含总串里面所有的字符
abb：bb之间没有a就不可以，
abcba：bcb这段没有a也不可以?
代码：
#include <bits/stdc++.h>
using namespace std;
vector<int> ve[30];
bool check(){
for(int i = 0; i < 26; i++){
if(ve[i].size() >= 2){
for(int j = 0; j < ve[i].size() - 1; j++){
for(int k = 0; k < 26; k++){
if(k != i && ve[k].size() != 0){
int ans = lower_bound(ve[k].begin(), ve[k].end(), ve[i][j]) - ve[k].begin();
if(ans == ve[k].size()){
return false;
}
if(ve[i][j + 1] < ve[k][ans]){
return false;
}
}
}
}
}
}
return true;
}
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
string s;
cin >> s;
for(int i = 0; i < 26; i++){
ve[i].clear();
}
for(int i = 0; i < s.length(); i++){
ve[s[i] - 'a'].push_back(i);
}
if(check()){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
return 0;
}?C. Palindrome Basis
题目链接：
题面：
?题意：
如果一个数字正序和反转后是同一个数字，那么这个数字就是回文数字
如果两个组成方法种的元素比例不同，那么这两个组成方法是不同的组成方法
现给定一个数字，问有这个数字有多少个只用回文数字的组成方法
思路：
动态规划，dp[j]表示总和为j一共有多少种组合方式
我们可以先预处理出每个回文数字，然后枚举每个回文数字
dp[j] = dp[j] + dp[j - ve[i]];
代码：
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define mod 1000000007
ll dp[40004];
vector<int> ve;
bool check(int x){
string s = "";
while(x){
s += x % 10 + '0';
x /= 10;
}
string ss = s;
reverse(s.begin(), s.end());
if(s == ss){
return true;
}
return false;
}
int main(){
ios::sync_with_stdio(false);
for(int i = 1; i <= 40000; i++){
if(check(i)){
ve.push_back(i);
}
}
dp[0] = 1;
for(int i = 0; i < ve.size(); i++){
for(int j = ve[i]; j <= 40000; j++){
dp[j] = dp[j] + dp[j - ve[i]];
dp[j] %= mod;
}
}
int t;
cin >> t;
while(t--){
int n;
cin >> n;
cout << dp[n] << endl;
}
return 0;
}
