首页 题解

# A. Everybody Likes Good Arrays!

水题。

奇乘奇，偶乘偶的奇偶性都不变。数一下有多少段即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int T, n;
int a[N];

inline void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    int ans = 0;
    for(int i = 2; i <= n; ++i)
        if((a[i - 1] % 2) == (a[i] % 2)) ans++;
    cout << ans << '\n';
}

signed main(){
    ios :: sync_with_stdio(false);
    cin >> T;
    while(T--) solve();
    return 0;
}

# B. Emordnilap

看到题目让求 1∼n1 \sim n 的所有排列的 S(p)S(p) 的和，而且这只是道 B\text{B}。

大胆猜测所有排列的 S(p)S(p) 是有一定关系的，再自己推一推，模拟一下。

不难发现 S(p)S(p) 就是个定值（但是我忘了是多少了qwq）.

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

using namespace std;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int T, n, inv2;
int fac[N];

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}

inline void solve(){
    cin >> n;
    cout << 1ll * 2 * n * (n - 1) % mod * inv2 % mod * fac[n] % mod << '\n';
}

signed main(){
    ios :: sync_with_stdio(false);
    fac[0] = 1;
    for(int i = 1; i <= 1e5; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv2 = qpow(2, mod - 2);
    cin >> T;
    while(T--) solve();
    return 0;
}

# C. Quiz Master

看到极差最小，自然是要二分了。

现预处理出来所有 aia_i 包含的小于等于 mm 的因数有哪些。

二分判断的时候双指针扫，开个桶记录当前出现了多少个 mm 以内的不同的因数，如果等于 mm 就合法。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1e5 + 10;
int T, n, m;
int a[N], buk[N], vis[N];
vector <int> d[N];

inline bool chk(int mid){
    memset(buk, 0, sizeof(buk));
    int cnt = 0;
    for(int i = 1, j = 1; i <= n; ++i){
        for(auto x : d[a[i]])
            if((++buk[x]) == 1) cnt++;
        while(a[i] - a[j] > mid){
            for(auto x : d[a[j]])
                if((--buk[x]) == 0) cnt--;
            j++;
        }
        if(cnt == m) return 1;
    }
    return 0;
}

inline void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i], vis[a[i]] = 1, d[a[i]].clear();
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= m; ++i)
        for(int j = i; j <= a[n]; j += i)
            if(vis[j]) d[j].pb(i);
    int l = 0, r = a[n] - a[1] + 1, res = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(chk(mid)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << res << '\n';
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> T;
    while(T--) solve();
    return 0;
}

# D. Score of a Tree

感觉非常妙的一道题。

首先不难发现，节点 uu 在 tt 时刻的值为它的子树内所有深度为 depu+tdep_u + t 的点的异或和。

假设 uu 子树内深度为 depu+kdep_u + k 的点有 cntcnt 个。

我们考虑什么样的权值分配对 uu 是有贡献的，当且仅当异或和为 1，即有奇数个 1。

根据二项式基本功得出也就是 2cnt−12^{cnt - 1}。此时其他的点都可以随便选，也就是 2n−cnt2^{n - cnt}.

乘到一起就是 2n−12^{n - 1}。

dfs\text{dfs} 过程中对每个点都算一下答案即可。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int T, n;
vector <int> G[N];
int f[N];

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}

inline void dfs(int x, int fa){
    for(auto y : G[x])
        if(y != fa) dfs(y, x), f[x] = max(f[x], f[y] + 1);
}

inline void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i) G[i].clear(), f[i] = 1;
    for(int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        G[u].pb(v), G[v].pb(u);
    }
    dfs(1, 0);
    int ans = 0;
    for(int i = 1; i <= n; ++i) ans = (ans + f[i]) % mod;
    cout << 1ll * ans * qpow(2, n - 1) % mod << '\n';
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> T;
    while(T--) solve();
    return 0;
}

# E. Edge Reverse

感觉比上面那道题简单不少。

看到最大权值最小肯定是要二分的。

现在的问题就是如何快速 check\text{check}。

其实也很简单，我们把 w≤midw \leq mid 的边全都变成无向边，然后跑 tarjantarjan 缩个点看一看是不是只有一个入度为 0 的点即可。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 4e5 + 10;
int T, n, m;
struct node{
    int u, v, w, nxt;
}edge[N << 1];
int head[N], tot = 1;
bool vis[N];

inline void add(int x, int y, int z){
    edge[++tot] = (node){x, y, z, head[x]};
    head[x] = tot;
}

int dfn[N], low[N], tim;
int stk[N], top, t[N];
int scc[N], cnt, in[N];

inline void tarjan(int x){
    dfn[x] = low[x] = ++tim;
    stk[++top] = x, t[x] = 1;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(!vis[i]) continue;
        int y = edge[i].v;
        if(!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
        else if(t[y]) low[x] = min(low[x], dfn[y]);
    }
    if(low[x] == dfn[x]){
        int k; cnt++;
        do{
            k = stk[top--], scc[k] = cnt, t[k] = 0;
        }while(x != k);
    }
}

inline bool chk(int mid){
    for(int i = 3; i <= tot; i += 2)
        if(edge[i].w <= mid) vis[i] = 1;
    for(int i = 1; i <= n; ++i) dfn[i] = low[i] = t[i] = scc[i] = in[i] = 0;
    tim = top = cnt = 0;
    for(int i = 1; i <= n; ++i)
        if(!dfn[i]) tarjan(i);

    for(int i = 2; i <= tot; ++i)
        if(vis[i] && scc[edge[i].u] != scc[edge[i].v]) in[scc[edge[i].v]]++;
    for(int i = 3; i <= tot; i += 2)
        if(edge[i].w <= mid) vis[i] = 0;

    int num = 0;
    for(int i = 1; i <= cnt; ++i)
        if(!in[i]) num++;
    return num <= 1;
}

inline void solve(){
    n = read(), m = read();
    for(int i = 1; i <= 2 * m + 2; ++i) head[i] = vis[i] = 0;
    tot = 1;
    int l = 0, r = 0, res = -1;
    for(int i = 1; i <= m; ++i){
        int u = read(), v = read(), w = read();
        add(u, v, w), vis[tot] = 1, add(v, u, w);
        r = max(r, w);
    }
    while(l <= r){
        int mid = (l + r) >> 1;
        if(chk(mid)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    write(res), puts("");
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    T = read();
    while(T--) solve();
    return 0;
}

# F. Comfortably Numb

肉眼可见的板子题。

al⊕al+1⊕⋯⊕ar−1⊕ara_l \oplus a_{l + 1} \oplus \cdots \oplus a_{r - 1} \oplus a_{r}：明显就是个可持久化 01trie\text{01trie} 板子啊。

max⁡{a[l⋯r]}\max\{a[l \cdots r] \}：明显就是笛卡尔树板子啊。

所以正确的做法就是先建出笛卡尔树，然后在 xx 较小的儿子里枚举一个边界，在另一个儿子里查询需要的异或最大值。

复杂度 2 只 log⁡\log。

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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
int T, n;
int a[N], s[N];
int stk[N], top, L[N], R[N];

int ch[N * 40][2], cnt[N * 40], tot;
int rt[N];

inline void ins(int &p, int q, int x){
    p = ++tot;
    for(int i = 31, u = p, v = q; i >= 0; --i){
        int t = (x >> i) & 1;
        ch[u][t] = ++tot, ch[u][t ^ 1] = ch[v][t ^ 1];
        u = ch[u][t], v = ch[v][t], cnt[u] = cnt[v] + 1;
    }
}

inline int qry(int u, int v, int x){
    int res = 0;
    for(int i = 31; i >= 0; --i){
        int t = (x >> i) & 1;
        if(cnt[ch[u][t ^ 1]] < cnt[ch[v][t ^ 1]]) res |= (1 << i), u = ch[u][t ^ 1], v = ch[v][t ^ 1];
        else u = ch[u][t], v = ch[v][t];
    }
    return res;
}

inline int dfs(int x, int l, int r){
    if(!x || l >= r) return 0;
    int ans = max(dfs(L[x], l, x - 1), dfs(R[x], x + 1, r));
    int l1 = x - l + 1, l2 = r - x + 1;
    if(l1 <= l2)
        for(int i = l; i <= x; ++i) ans = max(ans, qry(rt[x - 1], rt[r], a[x] ^ s[i - 1]));
    else
        for(int i = x; i <= r; ++i) ans = max(ans, qry(l == 1 ? 0 : rt[l - 2], rt[x - 1], a[x] ^ s[i]));
    return ans;
}

inline void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1, x = 0; i <= n; ++i){
        while(top && a[i] >= a[stk[top]]) x = stk[top], top--;
        if(x) L[i] = x, x = 0;
        R[stk[top]] = i, stk[++top] = i;
    }

    for(int i = 0; i <= n; ++i){
        if(i > 0) s[i] = s[i - 1] ^ a[i];
        ins(rt[i], i == 0 ? 0 : rt[i - 1], s[i]);
    }
    cout << dfs(stk[1], 1, n) << '\n';

    for(int i = 0; i <= tot; ++i) ch[i][0] = ch[i][1] = 0, cnt[i] = 0;
    for(int i = 1; i <= n; ++i) L[i] = R[i] = 0;
    top = tot = 0;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> T;
    while(T--) solve();
    return 0;
}