比赛入口

C

为了无后效性，我们对每一对可交换的数对，只计算交换对外层的影响(干扰度是否会减少)。而交换是相对的，所以对该层外层的操作与否也不会影响该层内层是否相对该层进行交换 (也就是说我们不需要真的去交换，只计数即可)。 所以做法即为贪心，我们如果发现交换可以使该层对外层的干扰数减少，那就使ans减去这个差值。任意次序遍历数组(比如说由外到内)均可，毕竟层与层之间没有影响。
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void solve()
{
    int n;
    cin >> n;
    vector<int>a(n + 2);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == a[i - 1])
            sum++;
    }

    vector<int>k(n + 1);
    for (int i = 1; i <= n / 2; i++) {
        int div = 0;
        if (a[i] == a[i - 1])
            div++;
        if (a[n - i + 1] == a[n - i + 2])
            div++;
        if (a[i] == a[n - i + 2])
            div--;
        if (a[n - i + 1] == a[i - 1])
            div--;
        sum -= max(0, div);
    }

    cout << sum << endl;
    return;
}

D

我的做法是前缀和+线性dp 当前缀和在i，j两处相等时，说明[i+1,j]这一段的和为0。 我们用map记录每个前缀和点值出现的位置，若前面已出现，我们就将这一段纳入答案中。 用线性dp计算答案。 设状态\(dp[i]\)为在\([1,i]\)段的答案，那么如果\(i\)是某一段美丽线段\([pre + 1,i]\)的右端点(记\(pre\)为上一个相同的presum点值下标)，那么它可以是\(pre\)处的答案再加上1，或者等于\(i-1\)处的答案。 若\(pre\)存在，状态转移方程： \[dp[i+1] = \max(dp[i],dp[pre]+1)\] 时间复杂度为\(O(n)\)
此外，需要注意的是，不能漏掉下标为0处的presum(这代表着从1开始的美丽线段)，而map的初始化值为0，所以我们判断presum是否在前面出现过，需要对presum为0的情况特殊处理一下。
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
    int n;
    cin >> n;
    vector<ll>a(n + 1);
    map<ll, ll>mp;
    vector<ll>dp(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
        if (mp[a[i]] != 0 || a[i] == 0) {
            dp[i] = dp[mp[a[i]]] + 1;
        }
        dp[i] = max(dp[i], dp[i - 1]);
        mp[a[i]] = i;
    }
    int ans = dp[n];
    cout << ans << endl;
    return;
}

E

感觉是比较典的题，类似的有：牛客多校2024第4场 Sort4

首先我们明确一个\(1 -n\)的排列\(p\)，由\(i\)向\(p[i]\)连边构成的有向图的结构：
1. 这个图只由若干个不相交的环构成(自环也算环)
2. 图中不存在链或者指向环的链(原因：\(p[i]\)的值不同)

再看题意，实际上就是需要我们通过若干次交换操作使这个图只由大小为1或者2的环组成。 我们观察swap操作,可以发现(这里推荐仔细思考一下)：
1. swap不同环上的点，将两个环合并成一个环。
2. swap相同环上的点，将一个环分裂成两个环。(可以想想是怎么分裂的)

所以最优操作即为：对每个点数\(n > 2\)的环，我们都不断地分裂出点数为2的环直到符合题意为止，操作数\(k = \left \lfloor\frac{n-1}{2} \right\rfloor\)

时间复杂度为\(O(n)\)
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int dfs(vector<int>& a, vector<int>& vs, int p) 
{
    if (vs[p])
        return 0;
    else {
        vs[p] = 1;
        return dfs(a, vs, a[p]) + 1;
    }
}
void solve()
{
    int n;
    cin >> n;
    vector<int>a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int>vs(n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int t = dfs(a,vs, i);
        ans += (t - 1) / 2;k
    }
    cout << ans << endl;
    return;
}

F

找规律题。具体证明实际上没有太懂。
打表可以发现n-th \(g(k) = n*g(k)\)
又由于k的总和不会很大，\(g(k)\)的上界不好估计， 但是常数\(t =\max(g(k)/k)\)应该不会过于大。所以对于每次询问，直接暴力解出第一个模\(k\)为0的位置，乘n即可 时间复杂度\(O(t\cdot \sum k)\)
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve()
{
    ll n, k;
    cin >> n >> k;
    ll f1 = 1, f2 = 1;
    ll cnt = 0;
    if (k == 1) {
        cout << n % mod << endl;
        return;
    }
    while(1){
        if (f2 % k == 0) {
            cout << (n % mod) * (cnt + 2) % mod << endl;
            return;
        }
        else {
            cnt++;
            int f = (f1 + f2) % k;
            f1 = f2;
            f2 = f;
        }
    }
    return;
}

G

树上问题，翻译一下题意，就是在一颗有根树上，多次询问一个节点v的k级祖先的子树上，距离v最远的节点的距离。

首先，求k级祖先，可以倍增法预处理(后面求lca也要用到这里的倍增)，\(O(\log k)\)查询。 那么，怎么求这颗子树上距离v最远的点的距离呢?

引理1： 在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端

那么就是说，树上任意点的距离最远点只能是树的直径端点。
所以我们把问题转化成求所有子树的直径问题。而一个树的直径可以由它的子树的直径信息合并而来。

引理2： 记\(diam(S)\)为树上点集\(S\)的最远点对，有： \[ \rm{diam}(S_1\cup S_2) = \rm{diam}(\rm{diam}(S_1) \cup \rm{diam}(S_2))\]

于是我们遍历子树直径和该树直径的点集和的所有点对组合，找出最大路径长的点对，即为该树的直径。通过dfs自底向上合并即可。 其中求点对之间的路径长，我们使用公式 \[pathlen(u,v) = deep(u)+deep(v) - 2deep(\rm{lca}(u,v))\]即可 求lca则利用前面预处理的倍增信息来求。
时间复杂度：\(O(n)\)

code： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
vector<vector<int>>g;
vector<vector<int>>fa;
vector<int>dep;
vector<pair<int, int>>dia;

void dfs(int p, int f)
{
    fa[p][0] = f;
    dep[p] = dep[f] + 1;
    for (auto s : g[p]) {
        if (s != f) {
            dfs(s, p);
        }
    }
    return;
}

int lca(int u, int v)
{
    if (dep[u] < dep[v])
        swap(u, v);
    int div = dep[u] - dep[v];
    for (int i = 0; div != 0; i++) {
        if (div >> i & 1) {
            u = fa[u][i];
            div -= (1 << i);
        }
    }
    if (u == v)
        return u;
    else {
        for (int j = 19; j >= 0; j--) {
            if (fa[u][j] != fa[v][j]) {
                u = fa[u][j];
                v = fa[v][j];
            }
        }
        return fa[u][0];
    }

}

int pathlen(int u, int v)
{
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void merge(pair<int, int>&p, pair<int, int>&s)
{
    pair<int, int>res;
    int len = 0;
    if (pathlen(p.first, p.second) >= pathlen(s.first, s.second)) {
        res = p;
        len = pathlen(p.first, p.second);
    }
    else {
        res = s;
        len = pathlen(s.first, s.second);
    }
    
    if (pathlen(p.first, s.first) > len) {
        res = { p.first,s.first };
        len = pathlen(p.first, s.first);
    }
    if (pathlen(p.first, s.second) > len) {
        res = { p.first,s.second };
        len = pathlen(p.first, s.second);
    }
    if (pathlen(p.second, s.first) > len) {
        res = { p.second,s.first };
        len = pathlen(p.second, s.first);
    }
    if (pathlen(p.second, s.second) > len) {
        res = { p.second,s.second };
        len = pathlen(p.second, s.second);
    }
    p = res;
    return;
}

void dfs2(int p, int f)
{
    for (auto s : g[p]) {
        if (s != f) {
            dfs2(s, p);
            merge(dia[p], dia[s]);
        }
    }
    return;
}

void solve()
{
    int n;
    cin >> n;
    g.clear();
    fa.clear();
    dep.clear();
    dia.clear();
    g.resize(n + 1, vector<int>(0));
    fa.resize(n + 1, vector<int>(30));
    dep.resize(n + 1, 0);
    dia.resize(n + 1, { 0,0 });
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1);
    for (int i = 1; i < 30; i++) {
        for (int j = 1; j <= n; j++) {
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        dia[i] = { i,i };
    }

    dfs2(1, 1);

    int q;
    cin >> q;
    while (q--) {
        int u, k;
        cin >> u >> k;
        int v = u;
        for (int i = 0; k != 0; i++) {
            if (k >> i & 1) {
                u = fa[u][i];
                k -= (1 << i);
            }
        }
        int ans = max(pathlen(v, dia[u].first), pathlen(v, dia[u].second));
        cout << ans << " ";
    }
    cout << endl;

    return;
}

ps:因为直径是diameter,所以封面就用Dia了