A. Subtle Substring Subtraction
题意
Alice 和 Bob 轮流取字母,_Alice_先手,并且Alice只能取偶数个字母,求_Alice_的权值减去_Bob_的权值的最大值。
思路
贪心的去想,如果字母个数为偶数,那么全部取完,差值一定最大,如果字母个数为奇数, _Alice_取0-s.size() - 2之间的全部字符减去s[s.size() - 1],然后和1-s.size() - 1之间的全部字符减去s[0]取一个max
inline void solve() {
int ans = 0;
string s;
cin >> s;
if (s.size() % 2 == 0) {
for (auto x : s) ans += x - 'a' + 1;
cout << "Alice " << ans << endl;
}
else if (s.size() == 1){
ans = s[0] - 'a' + 1;
cout << "Bob " << ans << endl;
}
else {
for (int i = 1 ; i < s.size() - 1 ; i ++ ) ans += s[i] - 'a' + 1;
ans = max(ans + s[0] - s[s.size() - 1] , ans + s[s.size() - 1] - s[0]);
cout << "Alice " << ans << endl;
}
}
B. A Perfectly Balanced String?
题意
对于一个字符串,取出它的字串,对于这个字符串出现的字符,如果在字串里面的差值大于1就输出NO,否则输出YES
思路
先用set看一下有多少个不重复的字符,然后枚举长度为s.size()的区间,如果里面字符个数大于1则输出NO,否则输出YES
inline void solve() {
string str;
cin >> str;
set<char> S;
for (auto c : str) S.insert(c);
for (int i = 0 ; i + S.size() - 1 < str.size() ; i ++ ) {
map<char , int> hash;
for (int j = i ; j <= i + S.size() - 1 ; j ++ )
hash[str[j]] ++ ;
for (auto [_ , v] : hash)
if (v > 1) {
cout << "NO" << endl;
return ;
}
}
cout << "YES" << endl;
}
题意
给你一个n,求一下有多少个回文数字相加等于n的方案数。
思路
预处理一下回文数字,然后做一遍完全背包
bool check(int x) {
string s = to_string(x);
for (int i = 0 , j = s.size() - 1; i < j ; i ++ , j -- )
if (s[i] != s[j])
return false;
return true;
}
void init() {
for (int i = 1 ; i <= 9 ; i ++ ) v[ ++ idx] = i;
for (int i = 10 ; i <= N ; i ++ )
if (check(i))
v[ ++ idx] = i;
f[0] = 1;
for (int i = 1 ; i <= idx ; i ++ )
for (int j = v[i] ; j <= N ; j ++ )
f[j] = (f[j] % MOD + f[j - v[i]] % MOD) % MOD;
}
inline void solve() {
int n;
cin >> n;
cout << f[n] % MOD << endl;
}