Codeforces Round #383 (Div. 1)

Div. 2 的 AB 比较水就不记录了。

A - Arpa's loud Owf and Mehrdad's evil plan

如果不是排列寄。否则答案必须是奇环环长的倍数，偶环环长一半的倍数。

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;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}  

#define N 107

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

bool vis[N];

int a[N], deg[N];

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) ++deg[a[i] = rd()];
    ll ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (!deg[i]) {puts("-1"); return 0;}
        if (!vis[i]) {
            int len = 0;
            for (int p = i; !vis[p]; p = a[p], ++len) vis[p] = true;
            if (!(len & 1)) len /= 2; 
            ans = ans / gcd(ans, len) * len;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

B - Arpa's weak amphitheater and Mehrdad's valuable Hoses

并查集求出来每个小团体。对于每个小团体，可选的转移方式为单人/全选。

背包先用另一个数组 \(g\) 记录 \(f\) 经过所有可能的转移的 \(\max\) ，再赋值回 \(f\) 更新，复杂度 \(O(nw)\)。

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

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}  

#define N 1007

struct DSU {
    int f[N];
    inline void reset(int n) {for (int i = 1; i <= n; ++i) f[i] = i;}
    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
    inline bool merge(int x, int y) {
        x = find(x); y = find(y);
        return x == y ? false : (f[x] = y, true);
    }
} dsu;

int w[N], v[N], f[N], g[N];

vector<int> s[N];

int main() {
    int n = rd(), m = rd(), tot = rd();
    dsu.reset(n);
    for (int i = 1; i <= n; ++i) w[i] = rd();
    for (int i = 1; i <= n; ++i) v[i] = rd();
    for (int i = 1; i <= m; ++i) dsu.merge(rd(), rd());
    for (int i = 1; i <= n; ++i) s[dsu.find(i)].push_back(i);
    
    auto upd = [&](int W, int V) {
        for (int i = W; i <= tot; ++i) g[i] = max(g[i], f[i - W] + V);
    };

    for (int i = 1; i <= n; ++i) {
        if (s[i].empty()) continue;
        int sumw = 0, sumv = 0;
        for (auto x : s[i]) {
            sumw += w[x]; sumv += v[x]; upd(w[x], v[x]);
        }
        upd(sumw, sumv);
        for (int i = 1; i <= tot; ++i) f[i] = max(f[i], g[i]); 
    }
    printf("%d\n", f[tot]);
    return 0;  
}

C - Arpa’s overnight party and Mehrdad’s silent entering

\(2\times n\) 个人（ \(n\) 个情侣）坐成一个环，黑白染色，要求情侣颜色不同，相邻三个中至少有两个颜色。

有意思的构造题。看到黑白染色就两种可能，2-SAT 和 二分图，相邻三个的要求写不成 2-SAT 的约束。

所以就想办法构造二分图，即构造一个图没有奇环。

每个人只有一个固定的情侣，这启示我们也要找一类边，使得每个点只有一个这样的出边，这样一定是偶环（两类边交替）。

容易发现让 \(2i-1\) 和 \(2i\) 连边即可保证相邻三个颜色不都相同，且符合上述构造要求。二分图染色。

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

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}  

#define N 200007
#define pb push_back

int ty[N], a[N], b[N];

vector<int> e[N];

void dfs(int u) {
    for (auto v : e[u])
        if (!ty[v]){ty[v] = 3 - ty[u]; dfs(v);}
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); b[i] = rd();
        e[a[i]].pb(b[i]); e[b[i]].pb(a[i]);
        int u = i * 2, v = i * 2 - 1;
        e[u].pb(v); e[v].pb(u);
    }
    for (int i = 1; i <= n * 2; ++i)
        if (!ty[i]) {ty[i] = 1; dfs(i);}
    for (int i = 1; i <= n; ++i) printf("%d %d\n", ty[a[i]], ty[b[i]]);
    return 0;  
}

D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

一棵树每条边上有一个字符 (a - v) ，每次询问 \(u_i\) 子树内最长的简单路径，满足其上的字符重排可形成回文串。

\((u,v)\) 路径信息 \(=u\) 到根信息 \(+v\) 到根信息 \(-2*lca(u,v)\) 到根信息。

字符集只有 \(22\) ，状压 \(u\) 到根每个字符的奇偶性 \(s_u\) ，路径信息即为 \(s_u\oplus s_v\) （lca 信息因为异或两次消掉了）

考虑路径合并，每个点可能的配对方案只有 \(23\) 种（异或后为 \(0\) 或 \(2\) 的幂次，即最多允许一个字符出现奇数次）

DSU on Tree，统计此前子树的信息，维护每个状压值的最深深度，保证 lca 是当前点需整个子树先查询后插入。

坑：1. 子树内最长要和儿子的 ans 取 \(\max\) ；2.枚举配对的状态时，得保证存在再更新。

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

inline int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define pic       pair<int, char>
#define lowbit(x) ((x) & -(x))

#define N 500007

int ch[N], sta[N], mxd[1 << 22], ans[N], res;

int sz[N], mxs[N], dep[N];

vector<int> son[N];

void dfs(int u, int fa, int S) {
    sz[u] = 1; 
    dep[u] = dep[fa] + 1;
    if (u != 1) S ^= (1 << ch[u]);
    sta[u] = S;
    for (auto v : son[u]) {
            dfs(v, u, S); sz[u] += sz[v];
            if (sz[v] > sz[mxs[u]]) mxs[u] = v;
        }
}

inline void upd(int u) {
    // adding information of u into data structures
    mxd[sta[u]] = max(mxd[sta[u]], dep[u]);
}

inline void del(int u) {
    // deleting information of u from data structures
    mxd[sta[u]] = 0; res = 0;
}

void upd(int u, int fa) {
    upd(u);
    for (auto v : son[u]) if (v != fa) upd(v, u);
}

void del(int u, int fa) {
    del(u);
    for (auto v : son[u]) if (v != fa) del(v, u);
}

void updans(int u, int del) { 
  	// 枚举配对的状态需要保证存在！！！
    if (mxd[sta[u]]) res = max(res, dep[u] + mxd[sta[u]] - 2 * del);
    for (int i = 0; i < 22; ++i) 
        if (mxd[sta[u] ^ (1 << i)]) res = max(res, dep[u] + mxd[sta[u] ^ (1 << i)] - 2 * del);
}

void getans(int u, int del) {
    updans(u, del);
    for (auto v : son[u]) getans(v, del);
}

void dsu(int u, int fa) {
    for (auto v : son[u])
        if (v != fa && v != mxs[u]) {dsu(v, u); del(v, u);}
    if (mxs[u]) dsu(mxs[u], u);
    updans(u, dep[u]); upd(u); 
    for (auto v : son[u])
        if (v != fa && v != mxs[u]) {
            getans(v, dep[u]); 
            res = max(res, ans[v]);
            upd(v, u);
        }
    ans[u] = res;
}

int main() {
    int n = rd();
    for (int i = 2; i <= n; ++i) {
        son[rd()].pb(i);
        char c = getchar();
        while (!isalpha(c)) c = getchar();
        ch[i] = (c - 'a');
    }
    dfs(1, 1, 0); dsu(1, 1);
    for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    return 0;
}

E - Arpa’s abnormal DNA and Mehrdad’s deep interest