Codeforces Round #785 (Div. 2)

今天五一集训第一天，刚打完一场组队赛，晚上本来想摆了，但是刚好洗完澡就开始了，就顺手写一下

A. Subtle Substring Subtraction

题目大意：两人博弈，A只能删除偶数个字符的子串，B只能删除奇数个字符的子串，a-z 被删除的得分是 1-26，问最终的差值和获胜的人

先走的是偶数的，如果是偶数的直接删，如果是奇数的就考虑左右端点的两个，留一个分值最小的给后手

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <deque>
#include <stack>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
const ll maxn = 2e5 + 10;
const ll inf = 1e17 + 10;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        int len = s.length();
        int a = 0, b = 0;
        for(int i=0; i<len; i++) a += s[i] - 'a' + 1;
        if(len & 1)
            b += min(s[0], s[len-1]) - 'a' + 1;
        a -= b;
        if(a > b)
            cout << "Alice " << a - b << endl;
        else cout << "Bob " << b - a << endl;
    }

    return 0;
}

B. A Perfectly Balanced String?

题目大意：给出一个字符串，问是否保证所有的子串里，每个字母（原字符串中有的）出现的频率差值不大于1

因为是所有子串，所以这种字符串的构造方式只能是形如 AAAAA，这里的 A 指的是一个不出现重复字符的字符串，A作为循环节循环出现

因此只要判断：

1. 找出有多少种字母，假设找到了 x 种字母，然后判断字符串前 x 个是否能作为循环节

2. 判断字符串是否以循环节的形式不断地出现

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <deque>
#include <stack>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
const ll maxn = 2e5 + 10;
const ll inf = 1e17 + 10;
int alp[maxn];

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        int len = s.length();
        for(int i=0; i<300; i++) alp[i] = 0;
        int cnt = 0;
        for(int i=0; i<len; i++)
            if(++alp[s[i]] == 1) cnt++;
        for(int i=0; i<300; i++) alp[i] = 0;
        for(int i=0; i<cnt; i++)
            alp[s[i]]++;
        int f = 1;
        for(int i='a'; i<='z' && f; i++)
            if(alp[i] == 2) f = 0;
        for(int i=0; i<cnt && f; i++)
        {
            for(int j=i; j<len && f; j+=cnt)
            {
                if(s[j] != s[i]) f = 0;
            }
        }

        if(f) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

C. Palindrome Basis

题目大意：将一个数字拆成若干个无前导零的回文数字，且不重复（拆成的数字出现的频率不同）

无前导零的回文数字：将数字视为一个串，然后他是个回文串，还没有前导零

背包dp

先将所有无前导零的回文数字预处理出来（从小到大排列），发现只有500个左右，然后同时发现 n 的数据范围挺小，就考虑dp了

\(dp[i][j] = x\) 代表用前 i 种回文数字组合成 j 的方式有 x 种

状态转移：\(dp[i][j] = dp[i][j] + dp[i-1][j-f[i]]\)

发现dp的纬度可以压缩，所以直接变成 \(dp[i] = dp[i] + dp[j-f[i]]\)

注意上述 dp 过程直接预处理即可，不然会超时

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <deque>
#include <stack>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
const ll maxn = 2e5 + 10;
const ll inf = 1e17 + 10;
const ll mod = 1e9 + 7;
vector<int>f;
ll dp[maxn];

bool check(int x)
{
    string s = to_string(x);
    for(int i=0; i<s.length(); i++)
        if(s[i] != s[s.length() - i - 1]) return false;
    return true;
}

int main()
{
    int n = 4e4 + 10;
    for(int i=1; i<=n; i++)
    {
        if(check(i))
            f.push_back(i);
    }
    for(int i=0; i<=n; i++) dp[i] = 0;
    dp[0] = 1;
    for(int i=0; i<f.size() && f[i]<=n; i++)
    {
        for(int j=f[i]; j<=n; j++)
            dp[j] = (dp[j] + dp[j-f[i]]) % mod;
    }
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        cout << dp[n] << endl;
    }
    return 0;
}

D. Lost Arithmetic Progression

这题是个数学题，感觉从因数分解 或者 判断 C 数列的两端是否在 B 中来进行约束 的角度分析的话应该可以

但是还没做出来，坐等题解 + 补题