25四川省赛

发表于 分类于 ， 阅读次数： 作者 Pomelorin ， Cool-breeze

F. Inversion Pairs

只含有 01? 三种字符的字符串，可以把 ? 变成 0 或 1，求逆序对最多为多少。

逆序对 贪心 填法一定是左边都填 1，右边都填 0，枚举这个分界点即可。

预处理前缀 1 个数与后缀 0 个数，先假设都填 0，之后从左向右开始填 1。贡献变化为加后面 0 的个数减前面 1 的个数。

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
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

void solve()
{
    ll n, ans = 0, cntq = 0, cur = 0;
    string s;
    cin >> n >> s;
    s = " " + s;
    ll pre1[n + 10] = {}, suc0[n + 10] = {}, preq[n + 10] = {};
    for (ll i = 1; i <= n; i++)
    {
        if (s[i] == '0')
        {
            suc0[i] = 1;
        }
        if (s[i] == '1')
        {
            pre1[i] = 1;
        }
        if (s[i] == '?')
        {
            preq[i] = 1;
            cntq++;
        }
    }
    for (ll i = 1; i <= n; i++)
    {
        pre1[i] += pre1[i - 1];
        preq[i] += preq[i - 1];
    }
    for (ll i = n; i >= 1; i--)
    {
        suc0[i] += suc0[i + 1];
    }
    for (ll i = 1; i <= n; i++)
    {
        if (s[i] != '1')
        {
            cur += pre1[i];
        }
    }
    for (ll i = 1; i <= n; i++)
    {
        if (s[i] == '?')
        {
            cur += (cntq - preq[i]) + suc0[i];
            cur -= (preq[i] - 1) + pre1[i];
        }
        ans = max(ans, cur);
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

H. Hututu

棋子每次可以走 \((x\pm1\text{or}2,y\pm1\text{or}2)\)，问最少走多少步从 \((x,y)\) 到 \((X,Y)\)。

考虑 x 和 y 轴分开来，每次最多走 2 格，然后结果就是 x 和 y 需要时间的最大值，特殊的，两格内的同行同列需要两步走到。

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
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int x, y, X, Y;
    cin >> x >> y >> X >> Y;
    if (x == X && y == Y) {
        cout << 0;
        return;
    }
    int dx = abs(x - X);
    int dy = abs(y - Y);
    int n1 = (dx + 1) / 2;
    int n2 = (dy + 1) / 2;
    int ans = max(n1, n2);
    if (ans == 1) {
        if (x == X || y == Y)
            cout << 2;
        else {
            cout << 1;
        }
        return;
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << endl;
    }
    return 0;
}

J. Sichuan Provincial Contest

给一棵树，每个节点都有一个大写字母，问长度为 5 且节点恰好组成 SCCPC 的简单路径个数。

计数题

思路 1：枚举每个 C 节点，计数 SC+C+PC，答案为 SC 乘 PC。

首先算出每个节点来自儿子方向的 S 个数，C 个数，SC 个数，PC 个数。之后将 S 个数与 C 个数加上来自父亲方向的个数，变为每个节点各个方向的 S 与 C 个数。最后枚举每个 C 节点，总 SC 个数为儿子方向 + 父亲为 C 时父亲各个方向的 S 个数。总 PC 个数类似，注意减掉当前节点的一个 C。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 1e6 + 10, inf = 1e17;

ll n, S[N], C[N], SC[N], PC[N], ans;
string a;
vector<ll> e[N];

void dfs(ll root, ll dad) {
    for (auto son: e[root]) {
        if (son == dad) {
            continue;
        }
        dfs(son, root);
        if (a[son] == 'S') {
            S[root]++;
        }
        if (a[son] == 'C') {
            C[root]++;
            SC[root] += S[son];
        }
        if (a[son] == 'P') {
            PC[root] += C[son];
        }
    }
}

void dfs2(ll root, ll dad) {
    for (auto son: e[root]) {
        if (son == dad) {
            if (a[dad] == 'C') {
                C[root]++;
            }
            if (a[dad] == 'S') {
                S[root]++;
            }
            continue;
        }
        dfs2(son, root);
    }
}

void dfs3(ll root, ll dad) {
    for (auto son: e[root]) {
        if (son == dad) {
            continue;
        }
        dfs3(son, root);
    }
    if (a[root] == 'C') {
        ll dSC = 0, dPC = 0;
        if (a[dad] == 'C') {
            dSC += S[dad];
        }
        if (a[dad] == 'P') {
            dPC += C[dad] - 1;
        }
        ans += (SC[root] + dSC) * (PC[root] + dPC);
    }
}

void solve() {
    cin >> n >> a;
    a = " " + a;
    ans = 0;
    for (ll i = 1; i <= n; i++) {
        e[i].clear();
        S[i] = C[i] = SC[i] = PC[i] = 0;
    }
    for (ll i = 1, u, v; i <= n - 1; i++) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    dfs2(1, 0);
    dfs3(1, 0);
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    // T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

思路 2：计算每个节点儿子方向的 C PC CPC CCPC 个数。

对于每个 S 节点，答案加上儿子方向 CCPC 个数，之后如果父亲为 C，向父亲走，答案加上儿子方向 CPC 个数……注意走到 P 时，儿子方向 C 个数减一。

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
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define int long long

vector<int> e[1000005];

int a[1000005];
int num[1000005][5]; // 1 21 121 1121

int fa[1000005];

void dfs(int x, int f)
{
    fa[x] = f;
    for (auto c : e[x])
    {
        if (c == f)
            continue;
        dfs(c, x);
        if (a[c] == 1) // C
        {
            num[x][1]++;
            num[x][3] += num[c][2];
            num[x][4] += num[c][3];
        }
        else if (a[c] == 2) // P
        {
            num[x][2] += num[c][1];
        }
    }
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char c;
        cin >> c;
        if (c == 'S')
            a[i] = 0;
        else if (c == 'C')
            a[i] = 1;
        else if (c == 'P')
            a[i] = 2;
        else
            a[i] = 114514;
    }
    for (int i = 1; i <= n; i++)
    {
        e[i].clear();
        num[i][0] = 0;
        num[i][1] = 0;
        num[i][2] = 0;
        num[i][3] = 0;
        num[i][4] = 0;
    }
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, -1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] != 0)
            continue;
        ans += num[i][4];
        int nex = fa[i];
        if (nex >= 1 && a[nex] == 1) // c
        {
            ans += num[nex][3];
            nex = fa[nex];
            if (nex >= 1 && a[nex] == 1) // c
            {
                ans += num[nex][2];
                nex = fa[nex];
                if (nex >= 1 && a[nex] == 2) // P
                {
                    ans += num[nex][1] - 1;
                    nex = fa[nex];
                    if (nex >= 1 && a[nex] == 1) // c
                    {
                        ans += 1;
                    }
                }
            }
        }
    }
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
    return 0;
}