2021组队训练赛第11场

我们的终极目标不是AC，而是获取经验

问题 A: ABB

题意

给定长度为n的字符串，在给定的字符串后面加上长度最短的字符串，使得到的字符串回文，求最少添加几个字符

考点

字符串哈希 or 马拉车算法（Manacher）

const ll inf = 1e15;
const ll INF = 0x3f3f3f3f;
const int MAXN = 410010;
char A[MAXN * 2];
int B[MAXN * 2];
 
void Manacher(char s[], int len)
{
    int l = 0;
    A[l++] = '$';//0下标存储为其他字符
    A[l++] = '#';
    for (int i = 0; i < len; i++)
    {
        A[l++] = s[i];
        A[l++] = '#';
    }
    A[l] = 0;//空字符
    int mx = 0;
    int id = 0;
    for (int i = 0; i < l; i++)
    {
        B[i] = mx > i ? min(B[2 * id - i], mx - i) : 1;
        while (A[i + B[i]] == A[i - B[i]])
        {
            B[i]++;
        }
        if (i + B[i] > mx)
        {
            mx = i + B[i];
            id = i;
        }
    }
    return;
}
int n;
char s[MAXN];
bool judge() {
    int l = 0, r = n - 1;
    int flag = 0;
    while (l <= r) {
        if (s[l] == s[r]) {
            l++;
            r--;
            continue;
        }
        else {
            flag = 1;
            break;
        }
        l++;
        r--;
        if (l == r) break;
    }
    if (flag) return false;
    return true;
}
int main()
{
    cin >> n;
    cin >> s;
    int len = (int)strlen(s);
    if (judge()) {
        puts("0");
        return 0;
    }
    Manacher(s, len);
    int ans = 0;
    int pos = 0;
    int siz = 2 * len + 1;
    for (int i = 0; i < 2 * len + 1; i++) {
        if (B[i] >= siz - i) {
            if (i % 2) {
                pos = max(pos, (B[i] - 1));
            }
            else
            {
                pos = max(pos, (B[i] - 1) / 2 * 2 + 1);
            }
        }
    }
    if (pos == 0) cout << n - 1 << endl;
    else cout << n - pos << endl;
    return 0;
}
/*
6
abcdcb
*/

问题 C: Bob in Wonderland

题意

将一个树形结构变成链，求出操作的次数(每次可以删除一条边)

考点

从度的角度可以很好的操作，代码很简短

const int N = 300010;
int d[N];
int main()
{
    int n; scanf("%d", &n);
    for (int i = 1;i < n;i++)
    {
        int x, y; scanf("%d%d", &x, &y);
        d[x]++, d[y]++;
    }
    int res = 0;
    for (int i = 1;i <= n;i++)
    {
        if(d[i] >= 2)
        res += d[i] - 2;
    }
    cout << res;
    return 0;
}
 
/**************************************************************
    Problem: 14241
    User: 我就不告诉你哈哈哈
    Language: C++
    Result: 正确
    Time:94 ms
    Memory:3196 kb
****************************************************************/

问题 F: Zeldain Garden

题意

考点

整数分块叭
计算出
x/1+x/2+x/3+x/4…+x/x即为答案，计算为下取整

typedef long long ll;
ll get(ll x)
{
    ll res = 0;
    for (ll l = 1, r;l <= x;l = r + 1) {
        r = x / (x / l);
        res += (r - l + 1) * (x / l);
    }
    return res;
}
int main()
{
    ll l, r; scanf("%lld%lld", &l, &r);
    ll ans = get(r) - get(l - 1);
    printf("%lld", ans);
    return 0;
}
 
/**************************************************************
    Problem: 14244
    User: 我就不告诉你哈哈哈
    Language: C++
    Result: 正确
    Time:119 ms
    Memory:2024 kb
****************************************************************/

问题 G: Light Emitting Hindenburg

题意

这个题不是我参与写的可以询问大佬

考点

据说是个贪心
代码仅从参考

虽然没代码，但是可以私信

问题 H: K == S

题意

考点

AC自动机 + 矩阵快速幂

问题 I: Ponk Warshall

/doge这个是我写的

题意

给出两个字符串，从上面字符中选取任意两个来进行交换，从上面的字符串得到下面的字符串，最少的操作步数是多少？

考点

思维 + 暴力

const ll inf = 1e15;
const ll INF = 0x3f3f3f3f;
string s, t;
map<char, int> mp;
int a[5][5];
int a1[1000007];
int a2[1000007];
int main()
{
    cin >> s;
    cin >> t;
    mp['A'] = 1, mp['C'] = 2, mp['G'] = 3, mp['T'] = 4;
    int len = s.size();
    for (int i = 0; i < len; i++) {
        a1[i] = mp[s[i]];
        a2[i] = mp[t[i]];
    }
    for (int i = 0; i < len; i++) {
        if (s[i] != t[i]) {
            a[a1[i]][a2[i]] += 1;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            int mini = min(a[i][j], a[j][i]);
            ans += mini;
            a[i][j] -= mini;
            a[j][i] -= mini;
        }
    }
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 4; k++) {
                int mini = min(a[i][j], min(a[j][k], a[k][i]));
                ans += 2 * mini;
                a[i][j] -= mini;
                a[j][k] -= mini;
                a[k][i] -= mini;
            }
        }
    }
    //方式1：
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 4; k++) {
                for (int t = 1; t <= 4; t++) {
                    int mini = min(a[i][j], min(min(a[j][k], a[k][t]), a[t][i]));
                    ans += 3 * mini;
                    a[i][j] -= mini;
                    a[j][k] -= mini;
                    a[k][t] -= mini;
                    a[t][i] -= mini;
                }
            }
        }
    }
    //方式2：
    for (int i = 1; i <= 4; i++) ans += 3 * a[i][2];
    //ps:a[i][x],1<=x<=4均可
    cout << ans << endl;
    return 0;
}
/*

*/
 
/**************************************************************
    Problem: 14247
    User: 我就不告诉你哈哈哈
    Language: C++
    Result: 正确
    Time:317 ms
    Memory:15700 kb
****************************************************************/