Codeforces Round #482 (Div. 2)

注意：long long

注意：第五个样例(aaaaa，n==1)的情况要先处理一下。

感受：还是读题的问题，and the ribbon abcdabc has the beauty of $2$ （误导信息一），题目没要求是最大的连续子串。还有就是只能修改一个位置，记得给的单词是segment（一段同颜色的），后来题面好像改了。

#pragma warning(disable:4996)
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mem(arr,in) memset(arr,in,sizeof(arr))
using namespace std;

const int maxn = 100005;

int n;

void change(string s, string& ss) {
    ss += s[0];
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == s[i - 1]) continue;
        else ss += s[i];
    }
}

int getmax(string s) {
    int p[30], q[30];
    mem(p, 0);
    mem(q, 0);

    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= 'a' && s[i] <= 'z') p[s[i] - 'a']++;
        else q[s[i] - 'A']++;
    }

    int res = 0;
    for (int i = 0; i < 26; i++) {
        res = max(res, p[i]);
        res = max(res, q[i]);
    }
    return res;
}

int main()
{
    while (cin >> n) {
        string a, b, c;
        cin >> a >> b >> c;

        int p[3];
        p[0] = a.size() - getmax(a);
        p[1] = b.size() - getmax(b);
        p[2] = c.size() - getmax(c);

        int x, y, z;
        int m = a.size();
　　　　　//n==1的情况有点特殊
        if (p[0] == 0) {
            if (n == 1) x = a.size() - 1;
            else x = a.size();
        }
        else x = min(m, getmax(a) + n);

        if (p[1] == 0) {
            if (n == 1) y = b.size() - 1;
            else y = b.size();
        }
        else y = min(m, getmax(b) + n);

        if (p[2] == 0) {
            if (n == 1) z = c.size() - 1;
            else z = c.size();
        }
        else z = min(m, getmax(c) + n);
    
        int cnt = 0, d = max(x, max(y, z));
        if (x == d) cnt++;
        if (y == d) cnt++;
        if (z == d) cnt++;

        if (cnt > 1) {
            cout << "Draw" << endl;
        }
        else {
            if (x==d) {
                cout << "Kuro" << endl;
            }
            else if (y==d) {
                cout << "Shiro" << endl;
            }
            else cout << "Katie" << endl;
        }

        /*  //修改连续同颜色的一段！！！
        string sa, sb, sc;
        change(a, sa);
        change(b, sb);
        change(c, sc);

        int p[3];
        p[0] = sa.size() - getmax(sa);
        p[1] = sb.size() - getmax(sb);
        p[2] = sc.size() - getmax(sc);

        int cnt = 0, res = maxn;
        for (int i = 0; i < 3; i++) {
            if (n >= p[i]) cnt++;
            res = min(res, p[i]);
        }

        if (cnt > 1) {
            cout << "Draw" << endl;
        }
        else {
            if (res == p[0]) {
                cout << "Kuro" << endl;
            }
            else if (res == p[1]) {
                cout << "Shiro" << endl;
            }
            else cout << "Katie" << endl;
        }
        */
    }
    return 0;
}

C. Kuro and Walking Route

题解：计数问题，两次DFS即可。

注意：可能爆int。

#pragma warning(disable:4996)
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn = 300005;

vector<int> G[maxn];

int n, x, y;
int dp[maxn];
bool use[maxn];

void DFS(int u) {
    use[u] = 1;
    dp[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!use[v]) {
            DFS(v);
            dp[u] += dp[v];
        }
    }
}

int main()
{
    while (scanf("%d%d%d", &n, &x, &y) != EOF) {
        
        for (int i = 1; i <= n; i++) G[i].clear();
        for (int i = 2; i <= n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }

        memset(use, 0, sizeof(use));
        memset(dp, 0, sizeof(dp));

        DFS(x);
        int ans1 = dp[y];

        memset(use, 0, sizeof(use));
        memset(dp, 0, sizeof(dp));

        DFS(y);
        int ans2 = dp[x];
    
        ll p = (ll)n * (ll)(n - 1);
        ll q = (ll)ans2 *(ll) ans1;
    
        cout << p - q << endl;
    }
    return 0;
}