广东这半个月疫情有点严重，学校基本封闭了，本来定好的西安邀请赛也退赛了，只能窝在学校里了，希望大家身体健康，瘟疫退散，广东加油！

A. Garland

题目链接： A. Garland

题意：

给定一个排列，有些位置是空的，要求将剩下的数放入空的位置上，使得相邻两个数奇偶性不同的情况最少。

解题思路：

定义 DP 数组为 $f[i,x,y,k]$ 为已经放了前 $i$ 个数，还有 $x$ 个奇数没放， $y$ 个偶数没放，且第 $i$ 个数的奇偶性为 $k$ 的所有方案，属性是最小值，转移、初始化以及结果应该都比较容易想到。

代码如下：

#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 105, INF = 0x3f3f3f3f;

int n;
int a[N];
int f[N][N][N][2];

int main()
{
    cin >> n;
    int odd = 0, even = 0;
    for (int i = 0; i < n; i ++ )
    {
        cin >> a[i];
        if (!a[i]) a[i] = -1;
        else if (a[i] & 1)
        {
            odd ++ ;
            a[i] = 1;
        }
        else
        {
            even ++ ;
            a[i] = 0;
        }
    }
    memset(f, 0x3f, sizeof f);
    odd = (n + 1) / 2 - odd;
    even = n / 2 - even;
    f[0][odd][even][0] = f[0][odd][even][1] = 0;
    for (int i = 0; i < n; i ++ )
        for (int x = odd; x >= 0; x -- )
            for (int y = even; y >= 0; y -- )
                for (int k = 0; k < 2; k ++ )
                {
                    int t = f[i][x][y][k];
                    if (a[i] != -1) f[i + 1][x][y][a[i]] = min(f[i + 1][x][y][a[i]], t + (int)(k ^ a[i]));
                    else
                    {
                        if (x) f[i + 1][x - 1][y][1] = min(f[i + 1][x - 1][y][1], t + (int)(1 ^ k));
                        if (y) f[i + 1][x][y - 1][0] = min(f[i + 1][x][y - 1][0], t + (int)(0 ^ k));
                    }
                }
    cout << min(f[n][0][0][0], f[n][0][0][1]) << '\n';
    return 0;
}

E. Partition Game

题目链接： E. Partition Game

题意：

建议直接看原题。

解题思路：

可以发现如果分割后的某一段，如果某个数出现了多次，比如在 $p_i,p_j,p_k$ 中出现，那么它贡献的花费应该是 $p_k-p_i=p_k-p_j+p_j-p_i$ ，因此可以分别计算相邻的两个相同数对哪些选法贡献了花费。

定义 DP 数组 $f[j][i]$ 为前 $i$ 个数，分成 $j$ 段的所有方案，属性是最小值。转移时，可以发现对于第 $i$ 个数，要寻找一个 $k$ ，使得 $[1,k]$ 分割了 $j-1$ 段，并将 $i$ 加到 $[k+1,i-1]$ 这一段中，然后如果 $a[i]$ 对花费有贡献的话，当且仅当上一个 $a[i]$ 出现在 $[k+1,i-1]$ 中，如果这个位置是 $pre[i]$ ，它的贡献是 $[i-pre[i]]$ ，如果 $k$ 取到 $[0,pre[i]-1]$ ，都会得到这部分的花费贡献。

分析到这里，就可以看出其实对于每个 $i$ ，首先要对当前这个数的花费贡献进行一次区间加法，然后要在 $[0,i-1]$ 中找一个 $k$ ，使得 $f[j-1][k]$ 最小，也就是找区间最小值，这两种操作都可以用线段树来完成，换句话说，就是将上一轮迭代的结果用线段树来维护，从而更新当前这一轮的结果。本题的定义和常规的顺序也是调换的，十分巧妙。

代码如下：

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 35010, INF = 0x3f3f3f3f;

int n, k;
int a[N];
int pre[N], last[N];
int f[N], g[N];
struct Node
{
    int l, r;
    int v, lazy;
} tr[N << 2];

#define lson (u << 1)
#define rson (u << 1 | 1)

void pushup(int u)
{
    tr[u].v = min(tr[lson].v, tr[rson].v);
}

void pushdown(int u)
{
    tr[lson].v += tr[u].lazy;
    tr[rson].v += tr[u].lazy;
    tr[lson].lazy += tr[u].lazy;
    tr[rson].lazy += tr[u].lazy;
    tr[u].lazy = 0;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l == r) tr[u].v = g[r];
    else
    {
        int mid = l + r >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int v)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].v += v;
        tr[u].lazy += v;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(lson, l, r, v);
        if (r > mid) modify(rson, l, r, v);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    else
    {
        pushdown(u);
        int res = INF;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) res = min(res, query(lson, l, r));
        if (r > mid) res = min(res, query(rson, l, r));
        return res;
    }
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        pre[i] = last[a[i]];
        last[a[i]] = i;
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int j = 0; j < k; j ++ )
    {
        memcpy(g, f, sizeof f);
        build(1, 0, n);
        for (int i = 1; i <= n; i ++ )
        {
            if (pre[i]) modify(1, 0, pre[i] - 1, i - pre[i]);
            f[i] = query(1, 0, i - 1);
        }
    }
    cout << f[n] << '\n';
    return 0;
}

E - Count Descendants

题目链接： E - Count Descendants

题意：

给定一棵树， $1$ 为根，多次询问，每次询问给定两个数 $u,d$ ，输出有多少个点在 $u$ 到根的路径上且这个点到根的距离恰好为 $d$ 。

解题思路：

做一次深搜，维护进出节点的时间戳以及每个节点的深度，根节点的深度为 $0$ 。然后把每个节点按照深度分组，现在问题就变成了在深度为 $d$ 的一堆节点里面统计有多少个节点的祖先是 $u$ 。

在树中，如果 $v$ 是 $u$ 的后代，那么 $in[v]\geq in[u]$ 且 $out[v]\leq in[u]$ 。

注意事项：

代码如下：

#include <vector>
#include <iostream>
#include <functional>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i ++ )
    {
        int p;
        cin >> p;
        g[p - 1].emplace_back(i);
    }
    vector<int> in(n), out(n), d(n);
    vector<vector<int>> cnt(n);
    int timestamp = 0;
    function<void(int, int)> dfs = [&](int u, int depth)
    {
        in[u] = ++ timestamp;
        d[u] = depth;
        cnt[d[u]].emplace_back(in[u]);
        for (auto &v : g[u]) dfs(v, depth + 1);
        out[u] = ++ timestamp;
    };
    dfs(0, 0);
    int q;
    cin >> q;
    while (q -- )
    {
        int u, d;
        cin >> u >> d;
        u -- ;
        auto R = lower_bound(cnt[d].begin(), cnt[d].end(), out[u]);
        auto L = lower_bound(cnt[d].begin(), cnt[d].end(), in[u]);
        cout << (int)(R - L) << '\n';
    }
    return 0;
}

C - Swaps 2

题目链接： C - Swaps 2

题意：

给定两个数组 $a$ 和 $b$ ，每次操作可以将 $a[i]$ 和 $a[i+1]$ 交换，交换后将 $a[i]$ 加上 $1$ ，将 $a[i+1]$ 减去 $1$ ，问是否能够使得两个数组相等。

解题思路：

这里要理解操作的本质是什么，可以发现两个位置的数比较，下标较大的数，会“占有更多资源”，因为如果将下标较大的数移动到较小的位置，它会加上下标的差值。因此可以发现如果一开始将两个数组的每个数都加上它的下标，如果可以满足题目的要求，当且仅当这两个数组拥有的数是相同的。

此时问题就变成了交换相邻两个数使得一个数组与另一个数组相同，需要交换多少次，就是要求逆序对了。这个问题挺常见的，这里也记录一下比较常规的做法。

代码如下：

#include <vector>
#include <iostream>
#include <algorithm>

#define lowbit(x) (x & -x)

using namespace std;

const int N = 200010;

long long tr[N];

void add(int x, int c)
{
    x ++ ;
    for (int i = x; i < N; i += lowbit(i)) tr[i] += c;
}

long long get(int x)
{
    long long res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i]; 
    return res;
}

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i ++ )
    {
        cin >> a[i].first;
        a[i].first += i;
        a[i].second = i;
    }
    vector<pair<int, int>> b(n);
    for (int i = 0; i < n; i ++ )
    {
        cin >> b[i].first;
        b[i].first += i;
        b[i].second = i;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    bool flag = true;
    vector<int> p(n);
    for (int i = 0; i < n; i ++ )
    {
        flag &= (a[i].first == b[i].first);
        p[b[i].second] = a[i].second;
    }
    if (!flag)
    {
        cout << "-1\n";
        return 0;
    }
    long long res = 0;
    for (int i = n - 1; i >= 0; i -- )
    {
        // 由于数组下标从 0 开始
        // 但树状数组模板下标是从 1 开始
        // 这里手动加 1 即可
        res += get(p[i] + 1);
        add(p[i] + 1, 1);
    }
    cout << res << '\n';
    return 0;
}

B - Sports Festival

题目链接： B - Sports Festival

题意：

一共有 $n$ 个人， $m$ 种活动，每个人对于每个活动有个优先级，每个人会参加优先级最高的、举行的活动，选择举行若干种活动，使得参与同一种活动的人数尽量小。

解题思路：

答案的范围是 $[m,1]$ ，思路就是枚举。首先一开始假设全部活动都举行，那么找参与人数最多的活动，删掉，然后参加这项活动的人会往后找第一个举行的活动来参加，最多删掉 $m-1$ 种活动，找最小值即可，主要是实现的方法比较巧妙。

代码如下：

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            cin >> a[i][j];
            a[i][j] -- ;
        }
    // ptr[] 是指针数组，记录每个人选择哪项活动
    vector<int> ptr(n), cnt(m);
    for (int i = 0; i < n; i ++ ) cnt[a[i][ptr[i]]] ++ ;
    vector<bool> st(m);
    int res = 2e9;
    for (int it = 0; it < m; it ++ )
    {
        int id = -1;
        for (int i = 0; i < m; i ++ )
            if (id == -1 || cnt[i] > cnt[id])
                id = i;
        res = min(res, cnt[id]);
        if (it == m - 1) break;
        st[id] = true;
        for (int i = 0; i < n; i ++ )
        {
            cnt[a[i][ptr[i]]] -- ;
            while (st[a[i][ptr[i]]]) ptr[i] ++ ;
            cnt[a[i][ptr[i]]] ++ ;
        }
    }
    cout << res << '\n';
    return 0;
}