首页 模拟赛

数论, 树的直径 + 优化建图, 01trie及其特殊操作

# A. 常中20181205T1-Simple

刚开始以为是扩展欧几里得定理然后乱搞，然后去测了一发大样例，结果挂了……

于是重新观察题目，原式：nx+my=cnx + my = c，假设有一条数轴。

  • 当 y=0y = 0 时，可以覆盖 n,2n,3n...n, 2n, 3n...

  • 当 y=1y = 1 时，可以覆盖 n+m,2n+m,3n+m...n + m, 2n + m, 3n + m...

不难发现，覆盖的点中一定会有重复的，那么哪些重复了呢？

当 an=bman = bm 时会重复，此时 b=anmb = a\frac nm。

由于 bb 为整数，且 aa 要尽量小，所以 a=mgcd⁡(n,m)a = \frac{m}{\gcd(n, m)}，暴力枚举 aa 即可。

codecode

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>
#define ll long long

using namespace std;

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

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

int T;
ll n, m, q;

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

int main(){
    T = read();
    while(T--){
        n = read(), m = read(), q = read();
        ll d = n / gcd(n, m), ans = 0;
        for(ll i = 0; i < d && q - i * m >= 0; ++i) ans += (q - i * m) / n + 1;
        write(q - ans + 1), puts("");
    }
    return 0;
}

# B. 常中20181205T2-Walk

考虑枚举权值 ii，计算权值为 ii（或 ii 的倍数）的路径中最长的长度是多少,计算最长长度直接跑个树的直径就完了。

但是如果每次都枚举所有边建图的话复杂度是过不去的，所以我们考虑优化建图过程。

类似于前向星的思想，我们用 h[i]h[i] 记录是 ii 倍数的边，然后建图的时候直接跑 h[i]h[i] 即可。

codecode

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

using namespace std;

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

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

const int N = 1e6 + 10;
const int M = 1e6;
int n, m;
struct node{
    int u, v, nxt;
}edge[N << 1], e[N << 1];
int head[N], tot, h[N], cnt;
int stk[N << 1], top;

inline void Add(int x, int y, int z){
    e[++cnt] = (node){x, y, h[z]};
    h[z] = cnt;
}

inline void add(int x, int y){
    edge[++tot].v = y, edge[tot].nxt = head[x];
    head[x] = tot;
    stk[++top] = x;
}

int maxl, tim = 1, vis[N];

int dfs(int u) {
    int maxc = 0;
    vis[u] = tim;
    for (int v, j = head[u]; j; j = edge[j].nxt)
        if (vis[v = edge[j].v] != tim) {
            int tmpc = dfs(v);
            maxl = max(maxl, maxc + tmpc + 1);
            maxc = max(maxc, tmpc + 1);
        }
    return maxc;
}

int ans[N];

inline void solve(int val){
    for(int i = 1; i <= top; ++i)
        if(vis[stk[i]] != tim) dfs(stk[i]);
    ans[maxl] = val;
}

inline void clear(){
    for(int j = 1; j <= top; ++j) head[stk[j]] = 0;
    tot = maxl = top = tot = 0;
}

signed main(){
    // freopen("B.in", "r", stdin);
    // freopen("B.out", "w", stdout);
    n = read();
    for(int i = 1; i < n; ++i){
        int u = read(), v = read(), w = read();
        Add(u, v, w), m = max(m, w);
    }
    for (int i = 1; i <= M; i++, tim++) {
        for (int j = i; j <= M; j += i)
            for (int k = h[j]; k; k = e[k].nxt)
                add(e[k].u, e[k].v), add(e[k].v, e[k].u);
        for (int j = 1; j <= top; j++)
            if (vis[stk[j]] != tim) dfs(stk[j]);
        ans[maxl] = i;
        clear();
    }
    for(int i = n - 1; i > 0; --i) ans[i] = max(ans[i], ans[i + 1]);
    for(int i = 1; i <= n; ++i) write(ans[i]), puts("");
    return 0;
}

# C. 树

这题就比较有意思了。

看到求异或和，肯定想到要用 01trie01trie，我们需要支持子树加 1，合并 01trie01trie，求区间异或和。

  • valval：表示权值。

  • cntcnt：表示从当前点到根的 1 的个数的奇偶性。

# 子树加 1

左子树会变成右子树，右子树变成左子树，所以就交换一下即可。

如果交换之后左子树还有值，相当于需要进位，继续加即可。

# 合并 01trie

类似于线段树合并（甚至更简单）。

直接合并即可。

# 区间异或和

01trie 基操，不多说了吧。

codecode

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
#include <bits/stdc++.h>
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
#define ll long long

using namespace std;

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

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

const int N = 6e5 + 10;
int n, cnt;
int a[N];
vector <int> g[N];

struct Trie{
    int val, cnt, ch[2];
}t[N * 27];
int rt[N];

void update(int x) {
    t[x].cnt = t[x].val = 0;
    if(ls(x)) t[x].cnt ^= t[ls(x)].cnt, t[x].val ^= (t[ls(x)].val << 1);
    if(rs(x)) t[x].cnt ^= t[rs(x)].cnt, t[x].val ^= (t[rs(x)].val << 1) | t[rs(x)].cnt;
}

inline void insert(int &x, int val, int dep){
    if(!x) x = ++cnt;
    if(dep > 20) return t[x].cnt ^= 1, void();
    insert(t[x].ch[val & 1], val>> 1, dep + 1), update(x);
}

inline void add(int x){
    swap(ls(x), rs(x));
    if(ls(x)) add(ls(x));
    update(x);
}

inline int merge(int x, int y){
    if(!x || !y) return x | y;
    t[x].val ^= t[y].val, t[x].cnt ^= t[y].cnt;
    ls(x) = merge(ls(x), ls(y));
    rs(x) = merge(rs(x), rs(y));
    return x;
}

ll ans;

inline void dfs(int x){
    for(auto y : g[x]) dfs(y), rt[x] = merge(rt[x], rt[y]);
    add(rt[x]), insert(rt[x], a[x], 0);
    ans += 1ll * t[rt[x]].val;
}

signed main(){
    // freopen("P6623.in","r",stdin);
    // freopen("P6623.out","w",stdout);
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 2; i <= n; ++i) g[read()].push_back(i);
    dfs(1);
    write(ans), puts("");
    return 0;
}

更新于 阅读次数 次