A.Ancient Distance

题意：

给定一个棵个点以点为根的树，在树上确定个关键点，每个点的权值为点到根节点路径上第一个关键点的距离(若路径上没有关键点, 那么权值为)，答案为所有点中最大权值的最小值。
现在求的答案之和

题解：

对于每个，可以每次贪心选择当前深度最深的点，将它的第个祖先设为关键点，并且删除这个关键点的子树，其中就为这个对应的最大权值。对于，可以二分来找，当时，的权值至少为，的权值至多为。为了保证能取到深度最深的，可以用序倒序遍历，每次删去已经确定了的子树。因此这题用二分+序+线段树来做

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
int a[maxn], dep[maxn], d[maxn], ans[maxn], v[maxn];
int n, cnt, mx, res;
vector<int> G[maxn];
void dfs(int u)
{
    mx = max(mx, dep[u]);
    d[++cnt] = u;
    for (auto v : G[u])
    {
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}
void build(int left, int right, int l, int r)
{
    if (left > right || l > r)
        return;
    if (l == r)
    {
        for (int i = left; i <= right; i++)
            ans[i] = l;
        return;
    }
    int mid = (left + right) / 2;
    ans[mid] = 0;
    for (int i = 1; i <= n; i++)
        v[i] = dep[i];
    for (int i = n; i >= 1; i--)
    {
        if (v[d[i]] == dep[d[i]] + mid || d[i] == 1)
        {
            ans[mid]++;
            v[d[i]] = -1;
        }
        int fa = a[d[i]];
        v[fa] = max(v[fa], v[d[i]]);
    }
    build(left, mid - 1, ans[mid], r);
    build(mid + 1, right, l, ans[mid]);
}
int main()
{
    while (scanf("%d", &n) != EOF)
    {
        memset(ans, 0, sizeof(ans));
        memset(dep, 0, sizeof(dep));
        dep[1] = cnt = mx = res = 0;
        for (int i = 1; i <= n; i++)
            G[i].clear();
        for (int i = 2; i <= n; i++)
        {
            scanf("%d", &a[i]);
            G[a[i]].push_back(i);
        }
        dfs(1);
        build(0, mx, 1, n);
        for (int i = 1; i <= mx; i++)
            res += i * (ans[i - 1] - ans[i]);
        printf("%d\n", res);
    }
}

B.Basic Gcd Problem

题意：

题解：

观察可以发现最终所求就是，其中为质因数分解后指数之和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n,c;
        scanf("%d%d", &n, &c);
        ll ans = 1;
        for (int i = 2; i * i <= n; ++i)
            while (n % i == 0)
            {
                n /= i;
                ans = ans * c % mod;
            }
        if (n > 1)
            ans = ans * c % mod;
        printf("%lld\n", ans);
    }
}

C.Count New String

题意：

给定一个字符串。并定义操作表示对于字符串，对区间内的每个字符都改为当前位置到的最大值。现在对于串，，求集合的大小

题解：

不会后缀自动机，找了一篇看得懂的题解戳我~

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
vector<pair<int, int>> vec;
map<int, vector<pair<int, int>>> mp; 
char s[maxn];
int len, dp[maxn][11]; 
int main()
{
    scanf("%s", s);
    len = strlen(s);
    for (int i = len - 1; i >= 0; i--)
    {
        int x = s[i] - 'a';
        dp[i][x]++;
        for (int j = 0; j <= x; j++)
            dp[i][x] += dp[i + 1][j];
        for (int j = x + 1; j < 10; j++)
            dp[i][j] = dp[i + 1][j];
    } 
    ll ans = 0;
    for (int i = 0; i < 10; i++)
        for (int j = i; j < 10; j++)
        { 
            mp.clear();
            for (int k = 0; k < len; k++)
                if (dp[k][i] && dp[k][j])
                {
                    int hash = 0;
                    for (int l = i + 1; l < j; l++)
                        hash = (1ll * hash * 233 + dp[k][l]) % mod;     
                    mp[hash].push_back(make_pair(dp[k][i], dp[k][j]));  
                }                                                       
            for (auto it:mp)
            {
                vec = it.second;
                sort(vec.begin(), vec.end()); 
                if (i == j)
                {
                    ans += vec[vec.size() - 1].first;
                    continue;
                } 
                int mx = 0;
                for (int k = vec.size() - 1; k >= 0; k--)
                {
                    mx = max(mx, vec[k].second);
                    if (k)
                        ans += 1ll * (vec[k].first - vec[k - 1].first) * mx;
                    else
                        ans += 1ll * vec[k].first * mx;
                } 
            }
        }
    printf("%lld\n", ans);
}

D.Dividing Strings

题意：

给定一段长度为的数字序列，要求将其分割成若干段（至少两段），询问各段数字中最大值与最小值的差值最小（每段数字要求都没有前导）

题解：

首先可以想到答案，因为最坏情况只需要全部拆成一位数。再考虑可能比这个小情况：

1. 同位数相减
2. 和

对于情况只需要找出的所有约数，先判断有没有前导，再判断最大值和最小值的差值
对于情况可以枚举相差一位的序列比较差值，对于每种长度只需，对所有的长度只需，只需枚举即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
char s[maxn];
int a[maxn], b[maxn], pre[maxn];  //pre前缀和，用于快速判断差1时的两种形式
void sub(int *a, int *b, int len) //同位高精减法
{
    for (int i = 1; i <= len; i++)
        a[i] -= b[i];
    for (int i = len; i >= 1; i--)
        if (a[i] < 0)
            a[i] += 10, a[i - 1]--;
}
bool cmp(int *a, int *b, int len) //比较大小，小返回1
{
    for (int i = 1; i <= len; i++)
        if (a[i] != b[i])
            return a[i] < b[i];
    return 0;
}

int sol_xd(int p, int len) //第一种情况
{
    if (p > 1 && !a[1])
        return 9; //前导0存在的话就直接不行了，位数不一样了
    int *mx = a, *mn = a;
    for (int i = 0; i < len; i += p)
    {
        if (p > 1 && !a[i + 1])
            return 9; //前导0
        if (cmp(a + i, mn, p))
            mn = a + i;
        if (cmp(mx, a + i, p))
            mx = a + i; //更新最值
    }
    memcpy(b, mx, sizeof(int) * (p + 10)); //+10防止减成负数，cpy一份是因为指针会导致原来的数组也改变
    sub(b, mn, p);                         //求差值
    for (int i = 1; i < p; i++)
        if (b[i])
            return 9; //如果减出来不是一位数，那么也是不对的
    return b[p];
}
int sol_cha1(int p, int len) //第二种情况
{
    int pos = 1, z_last = 0, n_last = 9;
    while (pos <= len)
    {
        if (a[pos] == 1)
        {
            if (pos + p > len || pre[pos + p - 1] - pre[pos] > 0)
                return 9; //快速判断是否全0
            z_last = max(z_last, a[pos + p]);
            pos += p + 1;
        }
        else
        {
            if (pos + p - 1 > len || pre[pos + p - 2] - pre[pos - 1] != p * 9 - 9)
                return 9; //快速判断是否全9
            n_last = min(n_last, a[pos + p - 1]);
            pos += p;
        } //这里的最大和最小要想清楚
    }
    return 10 - n_last + z_last;
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while (t--)
    {
        int ans = 9;
        scanf("%d", &n);
        scanf("%s", s + 1);
        for (int i = 1; i <= n; i++)
            a[i] = s[i] - '0';
        for (int i = 1; i <= n; i++)
            pre[i] = pre[i - 1] + a[i]; //求前缀和
        for (int i = 1; i <= n / 2; i++)
        {
            ans = min(ans, sol_cha1(i, n)); //第二种每个长度都求
            if (n % i == 0)
                ans = min(ans, sol_xd(i, n)); //第一种是因子才求
        }
        printf("%d\n", ans);
    }
}

F.Finding the Order

题意：

有两条平行的直线和。给出四个距离，问是 还是 。

题解：

只需要比较和的大小即可

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        puts(b + c > a + d ? "AB//CD" : "AB//DC");
    }
}

H.Harder Gcd Problem

题意：

把到总共个数两两组合，要求组数尽可能多并且每组的都大于。

题解：

先把所有的素数筛出来，然后先去除所有大于的素数。对于剩下来的素数对于他所有的倍数且尚未匹配的进行任意匹配，若个数为奇数，则留下他的倍用作后续匹配，最后会剩下一堆偶数，会算在的倍数中，进行任意匹配即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int prime[maxn];
bool vis[maxn];
int ans[maxn << 1];
int cnt, num;
int init()
{
    for (int i = 2; i < maxn; i++)
    {
        if (!vis[i])
            prime[++cnt] = i;
        for (int j = 1; j <= cnt && prime[j] * i < maxn; j++)
        {
            vis[prime[j] * i] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
    return 0;
}
void solve()
{
    int n;
    scanf("%d", &n);
    num = 0;
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    int mx = upper_bound(prime + 1, prime + cnt + 1, n / 2) - prime - 1;
    for (int i = mx; i; i--)
    {
        int pp = prime[i];
        for (int j = pp; j <= n; j += pp)
        {
            if (vis[j])
                continue;
            if (j == pp * 2)
                continue;
            ans[++num] = j;
            vis[j] = 1;
        }
        if (num & 1)
            ans[++num] = pp * 2, vis[pp * 2] = 1;
    }
    printf("%d\n", num >> 1);
    for (int i = 1; i <= num; i += 2)
        printf("%d %d\n", ans[i], ans[i + 1]);
}
int main()
{
    init();
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

I.Investigating Legions

题意：

有支军队和个军团，现在有一份这支军队两两间是否属于同一个军团的情报，但每对关系都有的概率出错，且两两之间的概率独立。现在给出和他们的关系，要求还原和各支军队属于哪个军团

题解：

一道乱搞题。遍历所有军队，如果当前军队没有确定就将与它属于同一个军团的所有军队都统计出来，对于统计出的每个属于同一个军团的所有军队都进行逐一判断，对每支军队都判断与其他军队是否属于同个军团，如果超过统计总数的一半就认为属于同一个军团。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 305;
const int maxp = maxn * 32;
const ll mod = 1e9 + 7;
int mp[maxn][maxn], a[maxn];
char s[maxn * maxn];
vector<int> vec;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,c;
        scanf("%d%d%s", &n, &c, s);
        int cnt = 0, num = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
                mp[i][j] = mp[j][i] = s[cnt++] - '0';
            mp[i][i] = 1;
        }
        cnt = 0;
        fill(a, a + 1 + n, -1);
        for (int i = 0; i < n; i++)
        {
            vec.clear();
            if (a[i] != -1)
                continue;
            for (int j = 0; j < n; j++)
                if (mp[i][j] && a[j] == -1)
                    vec.push_back(j);
            for (int j = 0; j < n; j++)
                if (a[j] == -1)
                {
                    num = 0;
                    for (int k = 0; k < vec.size(); k++)
                        if (mp[vec[k]][j])
                            num++;
                    if (num >= vec.size() / 2)
                        a[j] = cnt;
                }
            cnt++;
        }
        for (int i = 0; i < n; i++)
            printf("%d ", a[i]);
        puts("");
    }
}

官方题解