Happier233的博客

发表于 分类于

为什么要优化

如果一个算法的复杂度是 f(n)f(n) ，那么实际耗时往往是 T(n)=k×f(n)T(n)=k \times f(n), kk 就是代码的常数，但常数过大的时候就有可能超时。有些出题人会有意无意地卡常数，这时候不会代码优化技巧，则有可能被卡常错失AC。另外有可能因为对底层机制的了解不够，而踩坑，导致非常数因素的大幅耗时，最终TLE。

有些出题人对算法是有要求的，那么有可能会刻意卡掉一些空间需求高的算法，那么需要学会计算内存空间和空间优化。

时间优化技巧

IO优化

从最基本的算法无关的优化点开始，IO优化。在输入输出的时候，底层都是会涉及IO，那么有IO操作的地方，必定有IO耗时，这个是操作系统的知识，这里不展开。

如果全代码都只用到了scanf, printf, gets, putchar这一系列的C语言函数，则不需要考虑IO优化。

如果使用到了C++的cin/cout，则有几个点需要注意。

  1. 在输入或输出上不可以将C和C++的IO库混用。例如：在输入上不可scanf, getchar 和 cin 混用；在输出上不可printf 和 cout 混用；但 scanf 和 cout 是可以混用的。
  2. 若使用到了C++的IO库，则需要在代码中添加以下3行代码。但由于添加这3行代码后，输出结果不会立刻出现在控制台，会导致本地调试的时候困难，所以推荐在本地编译的时候增加宏定义，来区分是否是本地环境。切记这个宏定义不可和OJ添加的宏定义重名。
1
2
3
ios_base::sync_with_stdio(false); // 关闭c和c++的同步流
cin.tie(0); // 关闭cin的缓存流绑定
cout.tie(0); // 关闭cout的缓存流绑定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
#ifdef ACM_LOCAL
    freopen("./data/std.in", "r", stdin);
    // freopen("./data/std.out", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif

#ifdef ACM_LOCAL
    auto start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    auto end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}
  1. 由于C++的endl包含了flush，会导致输出流刷新。但由于内部机制，会使得输入流也发生同步行为，会导致IO耗时暴增，所以可以参考第二条，在非本地情况下将endl通过宏定义的方式，替换成 '\n'。
1
2
3
#ifndef ACM_LOCAL
#define endl '\n'
#endif

完整代码基础样板可以参考 https://github.com/happier233/ACM-Code/blob/master/00_头文件/00_Header.cpp

不建议在平时做题的时候经常使用快读模板，会养成坏习惯，在现场赛的时候往往没有时间去敲一份快读模板。正常情况下出题人不会硬卡IO的耗时，所以如果用快读模板过了题，但有可能去除快读还是会TLE，这说明你的算法没有达到正确的耗时要求。

在开启IO优化的情况下，可以完全保证C++的cin, cout耗时和C的scanf, printf的耗时持平。

内存访问优化

介绍

内存访问优化在于每次去读取特大的数组的时候，尽量保持连续的内存空间访问。
先举个代码例子，用来求一个二维矩阵上的一个问题的代码，为了防止逻辑过于简单导致编译器优化，所以采取了一些方法屏蔽了编译器优化。

测试代码

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
const int N = 10000;

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

int sum1() {
    int s = 0;
    for (int i = 0; i < N; i++) {
        s += a[i][0];
        for (int j = 1; j < N; j++) {
            a[i][j] += a[i][j - 1];
            s += a[i][j];
        }
    }
    return s;
}

int sum2() {
    int s = 0;
    for (int i = 0; i < N; i++) {
        s += a[0][i];
        for (int j = 1; j < N; j++) {
            a[j][i] += a[j - 1][i];
            s += a[j][i];
        }
    }
    return s;
}

void rnd() {
    srand(0);
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            b[i][j] = rand();
            b[j][i] = b[i][j];
        }
    }
}

void clone() {
    memcpy(b[0], a[0], N * N * sizeof(int));
}

void solve() {
    rnd();

    clock_t s, t;

    clone();
    s = clock();
    printf("sum1: %d\n", sum1());
    t = clock();
    printf("sum1 clock delte: %lld\n", ll(t - s));

    clone();
    s = clock();
    printf("sum2: %d\n", sum2());
    t = clock();
    printf("sum2 clock delte: %lld\n", ll(t - s));
}

输出结果

1
2
3
4
sum1: -682505014
sum1 clock delte: 90491
sum2: -682505014
sum2 clock delte: 782007

分析

最终的输出结果可见产生了近10倍的耗时差距，这个耗时差距随着第二维增大而增大。接下来分析一下产生的原因。
由于同一个数组的内存是连续的，不论是一维还是二维还是三维。

为了便于计算，对int a[1024][1024]，进行讨论那么如果a[0][0]是在地址0x0000，那么a[1][0]的内存地址是0x1000（1024∗41024*4，一个int是4字节)，a[2][0]的内存地址是0x2000。

因为CPU是有Cache机制的，为了降低访问内存的延时造成CPU空等，这个知识可以在计组和体系结构学到。所以在每次计算一次，需要访问4Kb的内存。CPU每次不是只读取一个int的内存，而是读取几百字节或者几k字节的，那么Cache命中率会大幅下降。但在 sum1 的写法中，CPU读取一次内存，可以进行几百次操作，可以大幅提高处理效率。

这个现象在写 dp 算法的时候尤其需要注意。不只是二维，在一维或者当维度变多的时候都适用。原则就是尽量访问靠近的内存。但不要刻意为了这个优化让代码变得过于复杂。

空间大小对时间的优化

先给出测试代码和输出结果，就是一个简单的对数组求和。在数组的计算过程中，由于可能会爆int，所以有人干脆会把数组开成long long，但这在复杂数据结构中会产生巨大的耗时常数影响。

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
const int N = int(1e7);
const int MOD = int(1e9 + 7);

ll a[N];
int b[N];

void init() {
    a[0] = 1;
    for (int i = 1; i < N; i++) b[i] = a[i] = a[i - 1] * i % MOD;
}

void solve() {
    init();
    clock_t s, t;

    s = clock();
    printf("sum1: %d\n", accumulate(a, a + N, 0));
    t = clock();
    printf("sum1 clock delte: %lld\n", ll(t - s));

    s = clock();
    printf("sum2: %d\n", accumulate(b, b + N, 0));
    t = clock();
    printf("sum2 clock delte: %lld\n", ll(t - s));
}
1
2
3
4
sum1: -1246626476
sum1 clock delte: 8125
sum2: -1246626477
sum2 clock delte: 3392

可见，对a的求和时间是b的两倍多，这就直接让常数产生了翻倍，虽然实际算法中，对单个数组的访问不会占到大比例，但确实会产生影响，如果数据的结果是不会超出int的，并且对自己代码的耗时不确定能否通过的，建议修改成int进行存储。

小技巧

这些小技巧优化有限，虽然不知道具体导致这些代码编译后的差异何在，但实测的确有效果，主要受到编译器优化影响。

取模连写

1
2
3
4
5
6
7
int a, b, c, mod; // 假设a, b, mod都已经有实际值，这里不写具体值

a = a * b % mod; // 基础写法
(a *= b) %= mod; // 技巧

a = ((a * b) % mod) + c) % mod; // 基础写法
((a *= b) %= mod) += c) %= mod; // 技巧

减少取模次数

假设 mod=109+7mod=10^9+7, 有2个二维非负整数矩阵 a,ba, b，都是 n×mn \times m 大小， n,m∈[1,104]n, m \in [1, 10^4]，其中所有值都有 aij,bij∈[0,104]a_{ij}, b_{ij} \in [0, 10^4]，求 $ \sum_{i=1}^n ((\sum_{j=1}^m {a_{ij}}) \times (\sum_{j=1}^m {b_{ij}})) \bmod MOD $

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
typedef long long ll;

const int N = 10005;
const int MOD = 1000000007;
const ll MOD2 = 1ll * MOD * MOD;
int a[N][N], b[N][N];

// 常规写法
int calc1(int n, int m) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        int sa = 0, sb = 0;
        for (int j = 0; j < m; j++) {
            (sa += a[i][j]) %= MOD;
            (sb += a[i][j]) %= MOD;
        }
        int si = (1ll * sa * sb) % MOD;
        (s += si) %= MOD;
    }
    return s;
}

// 一次优化写法
int calc2(int n, int m) {
    ll s = 0;
    for (int i = 0; i < n; i++) {
        ll sa = 0, sb = 0;
        for (int j = 0; j < m; j++) {
            sa += a[i][j];
            sb += b[i][j];
        }
        ll si = sa * sb;
        (s += si) %= MOD;
    }
    return s;
}

// 二次优化写法
int calc3(int n, int m) {
    ll s = 0;
    for (int i = 0; i < n; i++) {
        ll sa = 0, sb = 0;
        for (int j = 0; j < m; j++) {
            sa += a[i][j];
            sb += b[i][j];
        }
        ll si = sa * sb;
        s += si;
        if (s >= MOD2) s -= MOD2;
    }
    return s % MOD;
}

// 二次优化+偷懒写法
int calc4(int n, int m) {
    ll s = 0;
    for (int i = 0; i < n; i++) {
        ll sa = accumulate(a[i], a[i] + m, 0ll);
        ll sb = accumulate(b[i], b[i] + m, 0ll);
        ll si = sa * sb;
        s += si;
        if (s >= MOD2) s -= MOD2;
    }
    return s % MOD;
}

可以看得出，在每层for里，calc1一共有4次取模，calc2只有1次取模。通过在线编译查看编译后的汇编代码，https://gcc.godbolt.org/，对比这2个代码的汇编，也可以确认calc1执行了4次取模。由于CPU对于取模的运算耗时是巨大的，所以降低取模次数，可以很好的降低常数。

一次优化原理如下，由于 $\sum_{j=1}^m {a_{ij}} $ 和 $ \sum_{j=1}^m {b_{ij}}$ 都在 [0,108][0, 10^{8}] 范围内，所以可以用 long long 存下，所以 si=(∑j=1maij)×(∑j=1mbij)∈[0,1016]s_i = (\sum_{j=1}^m {a_{ij}}) \times (\sum_{j=1}^m {b_{ij}}) \in [0, 10^{16}] 也可以用 long long 存下，但由于最终的 ss 是在 [0,1020][0, 10^{20}] 超出了 long long的表达范围，所以需要对 ss 的加法结果进行取模。

二次优化原理如下，由于实际long long可以表达到 [−263,263−1][-2^{63}, 2^{63}-1] 范围，2632^{63} 约等于 9∗10189*10^{18}。我们可以使用 MOD2MOD^2 作为 ss 的模数，最终返回的时候再对 MOD 取模一次，正确性可以通过数论证明，这里不做展开，那么 ss 只有大约 1100\frac{1}{100} 的概率实际需要进行取模，在平时题目中，这个概率是不确定的但往往是比较小的一个概率，那么使用 if 来判定然后做减法，往往会比取模效率提高非常多。

二次优化+偷懒原理如下，由于这种求和操作非常普通，但往往写起来需要时间，赛场上的任何一秒钟都是重要的，而且为了防止自己写错，可以使用C++ algorithm 中的 accumulate 函数来进行求和操作。accumulate 函数具体用法参考以下手册链接。
https://zh.cppreference.com/w/cpp/algorithm/accumulate

gcc内置函数

使用gcc编译器作为本地编译器的时候，可以考虑使用gcc内置函数解决一些小问题。https://www.cnblogs.com/liuzhanshan/p/6861596.html

另外gcc还有一个内置的扩展stl库，叫pb_ds，里面的rbtree可以解决stl中set无法解决的一些问题，在不需要刻意降低常数的情况下使用，避免自己需要额外编写数据结构的时间。

空间优化技巧

2倍空间线段树

在普通的线段树写法中，线段树空间都是需要开4倍才能保证正确性的，这里我不做展开证明。
但如果4倍空间开不下怎么办，那么我有一个2倍空间的线段树写法，并且可以数学证明正确性。
这种写法会带来 %5 ~ %10的性能损耗，但却可以有一个全新的方法访问线段树中的任意一个[l, r]节点，前提该线段树中存在该区间的节点。例如可以方便的访问叶子节点，具体有什么用途未知，但可以发挥想象，万一哪天就用到了呢。

传统线段树中用 k 作为当前节点的下标，线段树的根节点为1。
在优化后的线段树中，对于每个覆盖了[l, r]的区间来说，他的下标是 (l + r) | (l != r) 。**所以这种线段树覆盖的区间最左值必须是非负整数。**最好的覆盖区间是 [0, n] 或者 [1, n]。
这种情况下，下标最大的节点必定是最右端的叶子节点，也就是n的2倍。那么接下来证明线段树中的任意一个节点不可能发生seg1 [l, r]算出来的下标和 seg2 [x, y]重复。

分几种情况进行讨论：

  1. 若 r<xr < x，说明 seg1在seg2的左侧。那么seg1的最大ID就是当 $ l=r $ 或 l+1=rl + 1 = r的时候，ID1=2∗rID_1=2*r。那么seg2的最小ID就是当x=yx=y的时候，ID2=2∗xID_2=2*x，由于r<xr<x，所以ID1<ID2ID_1<ID_2。不重复
  2. 若 y<ly < l，说明恰好与情况1相反，不再论证。
  3. 由于线段树的性质，2个线段树的节点覆盖的区间不可能相交，要么没有交集，要么是包含关系。这里就讨论seg1包含seg2的情况。若seg1包含seg2，则l≤x≤y≤rl \le x \le y \le r，并且线段树具有2分的性质，要么seg2在seg1的左半区间，要么在seg1的右半区间。后面2种情况分别列举左右区间问题。
  4. 若seg2在seg1的左半区间，则max(ID2)=2∗ymax(ID_2)=2*y，y≤⌊l+r2⌋y \le \lfloor \frac{l + r}{2} \rfloor。当 l+rl + r是偶数的时候，ID1=l+r+1，ID2=2∗y=l+r，ID1>ID2ID_1=l+r+1，ID_2=2*y=l+r，ID_1>ID_2；当 l+rl + r 是奇数的时候，ID1=l+r，ID2=2∗y=l+r−1，ID1>ID2ID_1=l+r，ID_2=2*y=l+r-1，ID_1>ID_2。
  5. 若seg2在seg1的右半区间，则min(ID2)=2∗xmin(ID_2)=2*x，x>⌊l+r2⌋x > \lfloor \frac{l + r}{2} \rfloor。当 l+rl + r是偶数的时候，ID1=l+r+1，ID2=2∗x=l+r+2，ID1<ID2ID_1=l+r+1，ID_2=2*x=l+r+2，ID_1<ID_2；当 l+rl + r 是奇数的时候，ID1=l+r，ID2=2∗x=l+r+1，ID1<ID2ID_1=l+r，ID_2=2*x=l+r+1，ID_1<ID_2。

所以不论什么情况下，都不可能出现 IDID 重复，由于线段树的性质，当覆盖的区间长度为n，那么实际节点为2∗n−12*n-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
69
70
71
72
73
74
75
76
77
const int N = 100005;

int a[N];

struct SegTree {
    ll sum[N << 1], laz[N << 1];

    int get(int l, int r) {
        return (l + r) | (l != r);
    }

    void up(int l, int r) {
        int mid = (l + r) >> 1;
        sum[get(l, r)] = sum[get(l, mid)] + sum[get(mid + 1, r)];
    }

    void push(int l, int r) {
        if (laz[get(l, r)] == 0) return;
        int mid = (l + r) >> 1;

        laz[get(l, mid)] += laz[get(l, r)];
        sum[get(l, mid)] += laz[get(l, r)] * (mid - l + 1);

        laz[get(mid + 1, r)] += laz[get(l, r)];
        sum[get(mid + 1, r)] += laz[get(l, r)] * (r - mid);

        laz[get(l, r)] = 0;
    }

    void build(int l, int r) {
        laz[get(l, r)] = 0;
        if (l == r) {
            a[get(l, r)] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid);
        build(mid + 1, r);
        up(l, r);
    }

    // 区间更新, a[i] += w
    void update(int l, int r, int x, int y, ll w) {
        if (l == x && r == y) {
            sum[get(l, r)] += (l - r + 1) * w;
            laz[get(l, r)] += w;
            return;
        }
        push(l, r);
        int mid = (l + r) >> 1;
        if (y <= mid) {
            update(l, mid, x, y, w);
        } else if (x >= mid) {
            update(mid + 1, r, x, y, w);
        } else {
            update(l, mid, x, mid, w);
            update(mid + 1, r, mid + 1, y, w);
        }
        up(l, r);
    }

    // 区间求和
    ll query(int l, int r, int x, int y) {
        if (l == x && r == y) {
            return sum[get(l, r)];
        }
        push(l, r);
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return query(l, mid, x, y);
        } else if (x >= mid) {
            return query(mid + 1, r, x, y);
        } else {
            return query(l, mid, x, mid) + query(mid + 1, r, mid + 1, 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
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
const int N = 100005;

int a[N];

struct SegTree {
#define smid ((l + r) >> 1)
#define self get(l, r)
#define lson get(l, smid)
#define rson get(smid + 1, r)

    ll sum[N << 1], laz[N << 1];

    int get(int l, int r) {
        return (l + r) | (l != r);
    }

    void up(int l, int r) {
        sum[self] = sum[lson] + sum[rson];
    }

    void push(int l, int r) {
        if (laz[self] == 0) return;
        int mid = (l + r) >> 1;
        
        laz[lson] += laz[self];
        sum[lson] += laz[self] * (mid - l + 1);

        laz[rson] += laz[self];
        sum[rson] += laz[self] * (r - mid);

        laz[self] = 0;
    }

    void build(int l, int r) {
        laz[self] = 0;
        if (l == r) {
            a[self] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid);
        build(mid + 1, r);
        up(l, r);
    }

    // 区间更新, a[i] += w
    void update(int l, int r, int x, int y, ll w) {
        if (l == x && r == y) {
            sum[self] += (l - r + 1) * w;
            laz[self] += w;
            return;
        }
        push(l, r);
        int mid = (l + r) >> 1;
        if (y <= mid) {
            update(l, mid, x, y, w);
        } else if (x >= mid) {
            update(mid + 1, r, x, y, w);
        } else {
            update(l, mid, x, mid, w);
            update(mid + 1, r, mid + 1, y, w);
        }
        up(l, r);
    }

    // 区间求和
    ll query(int l, int r, int x, int y) {
        if (l == x && r == y) {
            return sum[self];
        }
        push(l, r);
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return query(l, mid, x, y);
        } else if (x >= mid) {
            return query(mid + 1, r, x, y);
        } else {
            return query(l, mid, x, mid) + query(mid + 1, r, mid + 1, y);
        }
    }
};

发表于 更新于 分类于

奖项列表

在5月30日的下午，在北京CCPC Final的现场，我终于退役啦，结束了大学四年的XCPC生涯。
先总结一下四年打过的比赛和奖项吧。

序号 日期 名称 奖项 队友 备注
1 2018/01 2017 浙江工商大学新生赛 第一 进入ZJGSU ACM实验室
2 2018/04 2018 浙江工商大学校赛 第四
3 2018/04 2018 浙江省大学生程序设计竞赛 铁牌
4 2018/06 2018 ICPC 上海邀请赛 铜牌 黄队，蛋神 第一次拿牌
5 2018/10 2018 ICPC 南京区域赛 铁牌 噗噗，老板
6 2019/04 2019 浙江工商大学校赛 第二
7 2019/04 2019 浙江省大学生程序设计竞赛 铜牌
8 2019/05 2019 CCPC 湘潭邀请赛 铜牌 缪少爷，龙神 全新组队
9 2019/06 2019 ICPC 南昌邀请赛 银牌 缪少爷，龙神
10 2019/09 2019 CCPC 秦皇岛区域赛 银牌 缪少爷，龙神
11 2019/11 2019 ICPC 南昌区域赛 银牌 缪少爷，龙神
12 2019/12 2019 ICPC EC-Final 西安 铁牌 缪少爷，龙神
13 2019/11 2019 CCPC Final 北京 铁牌 经理，噗噗
14 2020/10 2020 浙江省大学生程序设计竞赛 银牌 徐总，缪少爷 退役后重新再战
15 2020/11 2020 CCPC 威海区域赛 银牌 徐总，缪少爷
16 2021/04 2020 ICPC 昆明区域赛 银牌 徐总，缪少爷
17 2021/04 2020 ICPC EC-Final 西安 银牌 徐总，缪少爷
18 2021/05 2020 ICPC 银川区域赛 金牌 徐总，缪少爷 第一次金牌
19 2021/06 2020 CCPC Final 北京 铁牌 徐总，缪少爷 退役之战

组队过程

除去非常规组队，一共经历3次组队。

第一次加入实验室后的第一个暑期集训，与室友和好朋友一起组了第一个队伍，最后打铁与南京站。

第二次加入实验室后的第二个暑期集训，与实验室的大佬缪少爷（保研浙大）和我的学弟龙神（安徽OI爷）。这期间一路从铜牌开始打到银牌，其实本来有希望在2020年上半年就获得第一个金牌，但可惜2020年疫情打破了一切计划。2020年初正值我ACM生涯巅峰时间，CF首次达到紫名，可惜疫情导致整个上半年赛季全部暂缓和取消，最终我和缪少爷进入了原地退役模式。

第三次在2020年9月，得知下半年赛站将以线上赛模式进行，比赛恢复常态化，当时我还在实习，和两位队友讨论后，决定再次组队，圆一下大学的梦，一直维持到毕业。

总结

这四年，我一共有3年半的时间付出在了ACM竞赛上，最终也算是没有遗憾的毕业了。这四年从来没有后悔过大一选择了ACM，或许说这个竞赛并不是适合所有人，但至少我在这个竞赛上得到了我想要的。

虽然曾一度想要靠ACM的奖项保研，但由于在2020年7月之前，没有得到那个梦寐以求的金牌，外加绩点排名没有其他人那么亮眼，所以我在申请了保研之后处于一种放弃的状态。2020年上半年退役后，有学长帮我内推了蚂蚁，我也是非常幸运的拿到了实习Offer。当时我没有Java基础，完全是在学长的鼓励下，抱着试试看的心态，几天时间突击了一波面经。最后在10月的时候通过了转正答辩，得到了我人生的第一份工作。

如果要说ACM给我带来了什么，那我的答案有几项内容：

  • 大学四年有了一项可以一直坚持下去事情，没有荒废这四年时光。
  • 让我认识了一群努力的人，每年暑假只有两周，每年寒假都是坚持到封校，都在为了自己想要的在奋斗。
  • 让我的付出成为了一个个奖牌，让我无数次跌倒，又能让我无数次在AC后呐喊，那种喜悦和成就感是可以一直去回忆的。

虽然说弱校打ACM出不了成绩，但在那么多届学长的铺垫下，但至少我做到了，我的学弟们也都做到了。强校很多选手都是OI出身的，有着多年的算法竞赛经验，这是他们的绝对优势，但并不是真的无法追赶，无非是自己愿不愿意，能不能看得到希望罢了。希望ZJGSU ACM越来越好，希望实验室的柜子能有一天金牌多到放不下。

最后感谢 MS教练 ，我们亲爱的老大！

发表于 更新于 分类于 ， ，

开篇

首先很感谢各位新生们的参与

题目难度

题目列表

ID Title Ratio
0 站神的 A+B problem 3.84% (27/704)
1 站神与最简单的语言 9.09% (1/11)
2 站神和一笔画圆 9.11% (38/417)
3 站神打包快递 3.33% (7/210)
4 站神的梦 0.00% (0/12)
5 站神数颜色 5.62% (9/160)
6 站神与肃正协议 14.29% (79/553)
7 站神的演讲 26.77% (106/396)
8 打破复读机 26.84% (142/529)
9 吃米饭的站神 24.31% (115/473)

预计难度
8<6<7<9<0<2<5<3<1<48 < 6 < 7 < 9 < 0 < 2 < 5 < 3 < 1 < 4
实际过题排序
8<9<7<6<2<0<5<3<1<48 < 9 < 7 < 6 < 2 < 0 < 5 < 3 < 1 < 4

评价

今年难度比往年普遍大幅降低，原计划是3+3+3+1的难度区分，3个基础题，3个需要一些数学能力的题目，3个需要一些代码能力的题目，还有一道防AK题。但防AK题并不是刻意让你们做不出来的题，只不过考虑到选手的实力，会选择需要一定思考深度和能力要求的题目。

所以最后的过体量大致还是符合出题组预想的结果的，而且大部分选手都留到了最后，不知道参赛选手们的参赛体验如何，如果有更好的建议和批评都欢迎提出来呀

题解链接们

括号内为题号
龙神的题解[2,3,5]：https://blog.csdn.net/panggeQAQ/article/details/111460746
老会长的题解[1,6,9]：https://blog.csdn.net/m0_43448982/article/details/111460449
林大佬的题解[0,7,8]：https://blog.csdn.net/weixin_44282912/article/details/111460476
开心点的题解[4]: https://happier233.github.io/2020/12/20/contest/2019-ec-final/

发表于 更新于 分类于 ， ， ，

题解

M

牛客题目链接

题目描述

Pang believes that one cannot make an omelet without breaking eggs.

For a subset AA of {1,2,…,n}\{1,2,\ldots,n\}, we calculate the score of AA as follows:

  1. Initialize the score as {0}0.
  2. For any i∈Ai \in A, add aia_i to the score.
  3. For any pair of integers (i,j)(i, j) satisfying i≥2i \ge 2, j≥2j \ge 2, i∈Ai \in A, if there exists positive integer k>1k \gt 1 such that ik=ji^k=j, subtract bjb_j from the score.

Find the maximum possible score over the choice of AA.

思考

我任意选择一个子集AA，只考虑条件2，可以得到的分值为∑i∈Aai\sum_{i\in{A}}{a_i}
如果需要扣除bjb_j的得分，必定存在某个ik=ji^k=j
那么就可以反过来思考，我枚举所有的iki^k，k≥1k \ge 1，ik≤ni^k \le n，例如：

  • {2,4,8,16,32,…}\{2,4,8,16,32,\ldots\}
  • {3,9,27,91,…}\{3,9,27,91,\ldots\}
  • {5,25,125,625,…}\{5,25,125,625,\ldots\}
  • {6,36,…}\{6,36,\ldots\}
  • …\ldots

对于以上每个集合，分别考虑里面的数字选与不选，比如第一个2k2^k的集合，当我没有选择2但选择了4的时候，所有bj(j∈A&j=4k)b_j(j \in A \And j=4^k)都需要扣除，那么对于单个集合计算的复杂度就是log⁡in×2log⁡in\log_{i}{n} \times 2^{\log_{i}{n}}，那么总体复杂度的上界就是∑inlog⁡in×2log⁡in\sum_i^n{\log_{i}{n} \times 2^{\log_{i}{n}}}，用起算器算一下当n=100000n=100000的时候，上界不超过20000002000000的

代码

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
// 巨菜的ACMer-Happier233

#include <bits/stdc++.h>

using namespace std;

//-----
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pw(x) (1ll << (x))
#define bt(x, k) (((x) >> k) & 1)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i, l, r) for(int i=(l);i<(r);++i)
#define per(i, l, r) for(int i=(r)-1;i>=(l);--i)
#define mst(t, v, n) memset(t, v, sizeof(decltype(*(t))) * (n))
#define sf(x) scanf("%d", &(x))
#if (not defined(ACM_LOCAL) || defined(ACM_TEST))
#define endl '\n'
#endif

const int N = 1e5 + 10;
const int MOD = 998244353;

const int M = 30;

int n, m;
// a表示题目输入的a,b，b来存放当前i的i^k的所有数字的a,b组合
pii a[N], b[N];
// c表示当前枚举集合的第j个=数字要选的时候需要被减去几次
int c[N] = {0};
// 表示当前i是否被访问过，比如需要跳过4,8,9之类的数字
bool vis[N];
ll rst;

void dfs(int k, ll w) {
    if (k > m) {
        rst = max(rst, w);
        return;
    }
    dfs(k + 1, w);
    w += b[k].first;
    w -= 1ll * b[k].second * c[k];
    for (int i = k; i <= m; i += k) {
        c[i]++;
    }
    dfs(k + 1, w);
    for (int i = k; i <= m; i += k) {
        c[i]--;
    }
}

void solve() {
    while (cin >> n) {
        memset(vis, false, sizeof(vis));
        for (int i = 1; i <= n; i++) cin >> a[i].first;
        for (int i = 1; i <= n; i++) cin >> a[i].second;

        ll ans = a[1].first;
        for (int i = 2; i <= n; i++) {
            if (vis[i]) continue;
            m = 0;
            for (ll k = i; k <= n; k *= i) {
                vis[k] = true;
                b[++m] = a[k];
            }
            rst = 0;
            dfs(1, 0);
            ans += rst;
        }
        cout << ans << endl;
    }
}

int main() {
#ifdef ACM_LOCAL
    freopen("./data/std.in", "r", stdin);
//    freopen("./data/std.out", "w", stdout);
#endif
#if (not defined(ACM_LOCAL) || defined(ACM_TEST))
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif

#ifdef ACM_LOCAL
    clock_t start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    clock_t end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}

发表于 更新于

概述

mysql 8 新特性

MySQL 8增加了 Locking Read Concurrency with NOWAIT and SKIP LOCKED 的实现
官方文档：mysql8 15.7.2.4 Locking Reads

消息队列

  普通的消息队列就是由生产者与消费者组成，多数场景下数据都会先落库然后将消息发送到消息队列，等待消费者进行消费。消费者在消费的时候往往需要保证执行的成功性，如果失败则需要进行n次重试。在某些场景下还需要事务消息的存在，需要保证消息与数据库写入同时成功。
  在一些小型项目内完全没有必要引入体量巨大的消息队列中间件，但多数项目都有数据库的依赖。所以直接使用mysql进行消息队列实现可以简化某些项目的体量。

实现

原理

使用单表记录存放消息
结构：

字段 类型 用途
id int(11) 主键
topic varchar(64) 主题
key varchar(64) 消息唯一性
status int(11) 消费状态
retry int(11) 剩余重试次数
start_time bigint(20) 任务最小开始执行的时间
exception varchar(11) 错误内容
msg varchar(256) 消息主体

建立唯一索引1(topic, key, retry)，建立普通索引2(topic, status, start_time)
状态分为：0（未消费），1（消费失败），2（消费成功）

处理逻辑

查找可以消费的消息

先开启事务，查找可以消费的消息，指定Topic，指定状态是待消费，开始时间小于等于当前时间

1
SELECT * FROM task WHERE topic='topic1' status=0 AND start_time<=1608212942 LIMIT 1 FOR UPDATE SKIP LOCKED;

消费成功

更新状态为3，表示消费成功

1
UPDATE task SET status=3 WHERE id=1000;

消费失败

更新状态为2，表示当前消息消费失败
检查当前retry是否大于0，若大于0，则插入一条新的消息，状态为0，retry-1

1
UPDATE task SET status=2 WHERE id=1000;

异常退出

若消费者在消费期间异常退出，则事务会被rollback，那么最多当前消费行为被当做无效行为，但可以保证会被下一个消费者重试，但无法保证重试次数是有效的。但异常退出本身就是少数情况，正常情况下的代码逻辑异常都会被捕获，不会导致该情况发生。

注意点

由于是通过事务来进行的行锁，所以在逻辑调用的时候要防止内部逻辑中有数据库操作导致的关联rollback，最好开启多个session进行数据库操作

性能问题

消息拉取的SQL会走索引2，所以在mysql8的innodb引擎中，会命中行锁，所以不会产生并发问题，但由于整个消费期间事务不会被释放，所以会有大量的事务和链接保持，会数据库有一定的性能影响，具体影响有多少未进行测试。这个设计也仅仅是一个轻量级的拉模式消息队列实现，至少保证了事务一定会被消费成功。
后续有时间会进行简单的性能测试。

额外

基于这个表还可以实现消费结果的存放

发表于 更新于 分类于 ，

第一章 概述

1.1 计算作用

  1. 21世纪的一些重要特征：数字化、网络化、信息化。
  2. 网络分类：电信网络，有线电视网络，计算机网络
  3. 互联网两个基本特性：连通性和共享
  4. 连通性：互联网使上网用户之间不管相距多远，都可以非常便捷非常经济地交换各种信息
  5. 共享：资源共享，包括信息共享，软件共享，硬件共享。

1.2 互联网概述

  1. 计算机网络由若干节点(node)和连接这些节点的链路(link)组成
  2. 互联网是“网络的网络”(network of networks)
  3. 连接在因特网上的计算机都称为主机 (host)
  4. 互联网三个阶段：
    • 第一阶段：从单个网络ARPANET向互联网发展的过程，1983年TCP/IP协议成为ARPANET上的标准协议，人们把1983年作为因特网的诞生时间，特点：TCP/IP首次成型
    • 第二阶段：建立了三级结构的互联网，特点：分为主干网，地区网，校园网
    • 第三阶段：形成了多层次的ISP结构的互联网，ISP的首次出现
  5. 小写开头的internet泛指多个计算机网络互连而成的网络，大写开头的Internet指代因特网，前身是ARPANET
  6. ISP(Internet Service Provider)划分成不同层次
    • 主干ISP：服务面积大，覆盖国家
    • 地区ISP：通过一个或多个主干ISP连接
    • 本地ISP：给用户提供直接服务的ISP，也称末端用户，可以是公司，学院或者大学
    • 三层ISP结构图：三层ISP结构图
  7. 互联网交换点IXP(Internet eXchange Point)：允许两个网络直连交换分组，不需要通过第三个网络来转发分组，这样可以更快的转发分组，有效利用网络资源
  8. 万维网 WWW (World Wide Web)

1.3 互联网的组成

  1. 以工作方式划分为两大块：
    • 边缘部分：由所有连接在因特网上的主机组成。这部分是用户直接使用的，用来进行通信(传送数据、音频或视频) 和资源共享。低速接入互联网。
    • 核心部分：由大量网络和连接这些网络的路由器组成。这部分是为边缘部分提供服务的(提供连通性和交换)。高速进行分组交换。
  2. 处在因特网边缘的部分就是连接在因特网上的所有的主机。这些主机又称为端系统(end system)。
    “主机 A 和主机 B 进行通信”，实际上是指:“运行在主机 A 上的某个程序和 运行在主机 B 上的另一个程序进行通信”。
    即“主机 A 的某个进程和主机 B 上的另一个进程进行通信”。或简称为“计算机之间通信”
  3. 两种通讯方式：
    • 客户−服务器方式(C/S 方式)，Client/Server
    • 对等方式(P2P 方式)，Peer-to-Peer
  4. 客户-服务器方式C/S：都是指通信中所涉及的两个应用进程，所描述的是进程之间服务和被服务的关系。客户是服务的请求方，服务器是服务的提供方。
  5. 客户软件的特点：被用户调用后运行，在打算通信时主动向远地服务器发起通信(请求服务)。因此，客户程序必须知道服务器程序的地址。不需要特殊的硬件和很复杂的操作系统。
  6. 服务器软件的特点：一种专门用来提供某种服务的程序，可同时处理多个远地或本地客户的请求。系统启动后即自动调用并一直不断地运行着，被动地等待并接受来自各地的客 户的通信请求。因此，服务器程序不需 要知道客户程序的地址。一般需要强大的硬件和高级的操作系统支持。
  7. 对等连接方式P2P：指两个主机在通信时并不区分哪一个是服务请求方还是服务提供方。只要两个主机都运行了对等连接软件 (P2P 软件)，它们就可以进行平等的、 对等连接通信。双方都可以下载对方已经存储在硬盘中的共享文档。
  8. 对等连接方式的特点：对等连接方式从本质上看仍然是使用客 户服务器方式，只是对等连接中的每一个主机既是客户又同时是服务器。例如主机 C 请求 D 的服务时，C 是客户， D 是服务器。但如果 C 又同时向 F提供 服务，那么 C 又同时起着服务器的作用。
  9. 网络中的核心部分要向网络边缘中的大量主机提供连通性，使边缘部分中的任何一个主机都能够向其他主机通信(即传送或接收各种形式的数据)。
  10. 在网络核心部分起特殊作用的是路由器(router)，路由器是实现分组交换(packet switching) 的关键构件，其任务是转发收到的分组，这是网络核心部分最重要的功能。
  11. 电路交换：2部电话只需要1对电线，5部电话需要10对电线， N 部电话机两两相连，需 N(N – 1)/2 对电线。当电话机的数量很大时，这种连接方法需要的电线 对的数量与电话机数的平方成正比。
  12. 交换机交换（使用交换机进行电路交换）：“交换”(switching)的含义就是转接——把一条电话线转接到另一条电话线，使它们连通起来。从通信资源的分配角度来看，“交换” 就是按照某种方式动态地分配传输线路的资源。
  13. 电路交换特点：
    • 电路交换必定是面向连接的
    • 电路交换的三个阶段：
      • 建立连接
      • 通信
      • 释放连接
    • 电路交换传送计算机数据效率低
    • 在电话通话的全部时间内，通话的两个用户始终占用端到端的通信资源
  14. 分组交换：采用存储转发技术，我们把要发送的整块数据称为一个报文(message)，在发送端，先把较长的报文划分成较短的、固定长度的数据段，每一个数据段前面添加上首部构成分组。分组又称为包，分组的首部也可以称为包头。
  15. 因特网的核心部分：
    • 由许多网络和把它们互连起来的路由器组成，而主机处在因特网的边缘部分。
    • 在因特网核心部分的路由器之间一般都用高速 链路相连接，而在网络边缘的主机接入到核心 部分则通常以相对较低速率的链路相连接。
    • 主机的用途是为用户进行信息处理的，并且可以和其他主机通过网络交换信息。路由器的用途则是用来转发分组的，即进行分组交换的
  16. 讨论互联网核心部分中的路由器转发分组的过程时，往往把单个网络简化成一条链路，而路由器成为核心部分的节点。
  17. 路由器：在路由器中的输入和输出端口之间没有直接连线。路由器处理分组的过程是：
    • 把收到的分组先放入缓存（暂时存储）
    • 查找转发表，找出到某个目的地址应从哪个端口转发
    • 把分组送到适当的端口转发出去
  18. 主机和路由器的不同：
    • 主机是为用户进行信息处理的，并向网络发送分组，从网络接收分组。
    • 路由器对分组进行存储转发，实际就是分组交换，最后把分组交付目的主机
  19. 分组交换的优点：
    • 高效——动态分配传输带宽，对通信链路是逐段占用。
    • 灵活——以分组为传送单位和查找路由。
    • 迅速——不必先建立连接就能向其他主机发送分组。
    • 可靠——保证可靠性的网络协议。
    • 分布式——的路由选择协议使网络有很好的生存性。
  20. 分组交换带来的问题
    • 分组在各结点存储转发时需要排队，这就会造成一定的时延。
    • 分组必须携带的首部（里面有必不可少的控制信息）也造成了一定的开销，还需要专门的管理和控制机制。
  21. 三种交换方式在数据传送阶段的主要特点：
    • 电路交换——整个报文的比特流连续地从源点直达终点，好像在一个管道中转发。
    • 报文交换——整个报文先转发到相邻节点，全部存储下来后查找转发表，转发到下一个节点
    • 分组交换——单个分组（这只是整个报文的一部分）传送到相邻节点，存储下来后查找转发表，转发到下一个节点
    • 三种交换的比较
    • 由于一个分组的长度往往远小于整个报文长度，因此分组交换比报文交换的时延小，同时也具有更好的灵活性
  22. 传统的电路交换(circuit switching)的电信网有一个缺点：正在通信的电路中有一个交换机或有一条链路被炸毁，则整个通信电路就要中断。如要改用其他迂回电路，必须重新拨号建立连接。这将要延误一些时间
  23. 新型网络的基本特点:
    • 网络用于计算机之间的数据传送，而不是为了打电话。
    • 网络能够连接不同类型的计算机，不局限于单一类型的计算机。
    • 所有的网络结点都同等重要，因而大大提高网络的生存性。
    • 计算机在进行通信时，必须有冗余的路由。
    • 网络的结构应当尽可能地简单，同时还能够非常可靠地传送数据。
  24. 早期的面向终端的计算机网络是以单个主机为中心的星形网.分组交换网则是以网络为中心，主机都处在网络的外围。

1.5 计算机网络的分类

  1. 不同的定义：
    • 计算机网络是一些互相连接的、自治的计算机的集合。
    • 因特网(Internet)是“网络的网络”。
  2. 不同的网络分类：
    1. 网络的作用范围分类：
      • 广域网 WAN (Wide Area Network)
      • 局域网 LAN (Local Area Network)
      • 城域网 MAN (Metropolitan Area Network)
      • 个人区域网 PAN (Personal Area Network)
    2. 网络的使用者分类：
      • 公用网 (public network)
      • 专用网 (private network)
    3. 主干和接入网：
      • ISP，提供的接入网只是起到让用户能够与因特网连接的“桥梁”作用。
      • AN(Access Network)，它又称为本地接入网或居民接入网。

1.6 计算机网络的性能

1.6.1 性能指标

  1. 速率：指的是数据的传送速率，也称为数据率。
  2. 带宽：原本指的是某个信号具有的频带宽带，计网中表达是的网络中某通道传送数据的能力，在单位时间内某信号所通过的“最高数据率”，这种意义下的单位是bit/s，比特每秒。前者是频域称谓，后者是时域称谓。
  3. 带宽：原本指的是某个信号具有的频带宽带，计网中表达是的网络中某通道传送数据的能力，在单位时间内某信号所通过的“最高数据率”，这种意义下的单位是bit/s，比特每秒。前者是频域称谓，后者是时域称谓。
  4. 吞吐量：单位时间内通过某个网络（或通道，端口）的实际数据量，吞吐量受到网络带宽或网络额定速率的限制。
  5. 时延：指数据（或一个报文或分组，甚至比特）从网络（或链路）的一端传送到另一端所需的时间，也称为延迟或迟延。
    1. 发送时延：从主机或路由器发送数据帧所需要的时间。发送时延=数据帧长度(bit)发送速率(bit/s)\text{发送时延}=\frac{\text{数据帧长度(bit)}}{\text{发送速率(bit/s)}}
    2. 传播时延：电磁波在信道中传播一定的距离需要花费的时间。传播时延=信道长度(m)电磁波在信道上的传播速度(m/s)\text{传播时延}=\frac{\text{信道长度(m)}}{\text{电磁波在信道上的传播速度(m/s)}}
    3. 处理时延：主机或路由器接受到分组之后需要时间进行处理。
    4. 排队时延：分组进过路由器时，需要进入缓存排队等待交换，出现排队时延，排队时延的长短往往取决于网络中当时的通信量。
    5. 总时延=发送时延+传播时延+处理时延+排队时延
  6. 时延带宽积=传播时间×\times带宽，又称为以比特为单位的链路长度。
  7. 往返时间RTT：有效数据率=数据长度发送时间+RTT(bit/s)\text{有效数据率}=\frac{\text{数据长度}}{\text{发送时间+RTT}}\left(bit/s\right)
  8. 利用率：
    • 信道利用率指出某信道有百分之几的时间是被利用的(有数据通过)。完全空闲的信道的利用率是零。
    • 网络利用率则是全网络的信道利用率的 加权平均值。信道利用率并非越高越好。
    • 如果D0D_0表示空闲时时延，U表示网络利用率，那么D=D01−UD=\frac{D_0}{1-U}

1.6.2 非性能特征

  1. 费用
  2. 质量
  3. 标准化
  4. 可靠性
  5. 可扩展性和升级性
  6. 易于管理和维护

1.7 计算机网络体系结构

  1. 相互通信的两个计算机系统必须高度协调工作才行，而这种“协调”是相当复 杂的。
  2. “分层”可将庞大而复杂的问题，转化 为若干较小的局部问题，而这些较小的 局部问题就比较易于研究和处理。
  3. 网络协议(network protocol)，简称为协议，是为进行网络中的数据交换而建立的规则、标准或约定。
  4. 网络协议的组成要素：
    • 语法——数据与控制信息的结构或格式 。
    • 语义——需要发出何种控制信息，完成何 种动作以及做出何种响应。
    • 同步——事件实现顺序的详细说明。
  5. 分层的好处：
    • 各层之间是独立的。
    • 灵活性好。
    • 结构上可分割开。
    • 易于实现和维护。
    • 能促进标准化工作。
  6. 层数多少要适当：若层数太少，就会使每一层的协议太复杂。层数太多又会在描述和综合各层功能的 系统工程任务时遇到较多的困难。
  7. 5层协议的体系结构：
    • 应用层(application layer)
    • 运输层(transport layer)
    • 网络层(network layer)
    • 数据链路层(data link layer)
    • 物理层(physical layer)
  8. 实体、协议、服务 和服务访问点：
    • 实体(entity)——表示任何可发送或接收信息的硬件或软件进程。
    • 协议——控制两个对等实体进行通信的规则的集合。
    • 在协议的控制下，两个对等实体间的通信使得本层能够向上一层提供服务。
    • 要实现本层协议，还需要使用下层所提供的服务。
    • 下面的协议对上面的服务用户是透明的。
    • 协议是“水平的”，即协议是控制对等实体之间通信的规则。
    • 服务是“垂直的”，即服务是由下层向上层通 过层间接口提供的。
    • 同一系统相邻两层的实体进行交互的地方，称为服务访问点 SAP (Service Access Point)
  9. 协议必须把所有不利的条件事先都估计到，而不能假定一切都是正常的和非常理想的，必须非常仔细地检查这个协议能否应付各种异常情况。

第二章 物理层

2.1 物理层的概念

  1. 物理层的主要任务描述为确定与传输媒体的接口的一些特性，即:
    • 机械特性：指明接口所用接线器的形状和尺寸、引线数目和排列、固定和锁定装置等等。
    • 电气特性：指明在接口电缆的各条线上出现的电压的范围。
    • 功能特性：指明某条线上出现的某一电平的电压表示何种意义。
    • 过程特性：指明对于不同功能的各种可能事件的出现顺序。

2.2 数据通道的基础知识

  1. 几个术语：
    • 数据(data)——运送消息的实体。
    • 信号(signal)——数据的电气的或电磁的表现。
    • “模拟的”(analogous)——代表消息的参数的取值是连续的。
    • “数字的”(digital)——代表消息的参数的取值是离散的。
    • 码元(code)——在使用时间域(或简称为时域)的波形表示数字信号时，代表不同离散数值的基本波形。
    • 模拟信号——连续的信号
    • 数字信号——
  2. 数据在通信线路上的传输方式一般都是串行传输。
  3. 一个数据通信系统可以划分三大部分：源系统（或发送端、发送方）、传输系统（或传输网络）和目的系统（或接收端、接收方）。输入信息–(源点)–>输入数据–(发送器)–>发送的信号–(传输系统)–>接受的信号–(接收器)–>输出数据–(终点)–>输出信息。 数据过程
  4. 源系统包含：源点、发送器
  5. 目的系统包含：接收器、终点
  6. 几个概念：
    • 单向通信(单工通信)——只能有一个方向的通信而没有反方向的交互。
    • 双向交替通信(半双工通信)——通信的双方都可以发送信息，但不能双方同时发送(当然也就不能同时接收)。
    • 双向同时通信(全双工通信)——通信的双方可以同时发送和接收信息。
    • 基带信号(即基本频带信号)——来自信源的信号。像计算机输出的代表各种文字或图像文件的数据信号都属于基带信号。基带信号往往包含有较多的低频成分，甚至有直流成分，而许多信道并不能传输这种低频分量或直流分量。因此必须对基带信号进行调制(modulation)。
    • 带通信号——把基带信号经过载波调制后，把信号的频率范围搬移到较高的频段以便在信道中传输(即仅在一段频率范围内能够通过信道)。
  7. 基带解调，编码，载波，带通信号，带通解调
  8. 最基本的二元制调制方法有以下几种：
    • 调幅(AM)：载波的振幅随基带数字信号而变化。
    • 调频(FM)：载波的频率随基带数字信号而变化。
    • 调相(PM) ：载波的初始相位随基带数字信号而变化。
  9. 奈氏准则，在任何信道中，码元传输的速率是有上限的，否则就会出现码间串扰的问题，使接收端对码元的判决(即识别)成为不可能。
  10. 香农公式：C=Wlog2(1+S/N)C=Wlog_2(1+S/N) b/sb/s，W 为信道的带宽（以 Hz 为单位）；S 为信道内所传信号的平均功率；N 为信道内部的高斯噪声功率。用信息论的理论推导出了带宽受限且有高斯白噪声干扰的信道的极限、无差错的信息传输速率。
  11. 信噪比(dB)=10log10(S/N)(dB)10log_{10}(S/N)(dB)

2.3 物理层下面的传输媒体

  1. 导引型传输媒体：
    • 双绞线：屏蔽双绞线，无屏蔽双绞线
    • 同轴电缆：50Ω\Omega同轴电缆，75Ω\Omega同轴电缆
    • 光缆：单模光纤，多模光纤
  2. 非导引型传输媒体
    • 短波
    • 微波
    • 卫星

2.4 信道复用技术

  1. 频分复用：所有用户在同样的时间占用不同的带宽（频率带宽）资源
  2. 时分复用：将时间划分为一段段等长的时分复用帧(TDM 帧)。每一个时分复用的用户在每一个 TDM 帧中占用固定序号的时隙。每一个用户所占用的时隙是周期性地出现(其周期就是 TDM 帧的长度)。TDM 信号也称为等时(isochronous)信号。时分复用的所有用户是在不同的时间占用同样的频带宽度。
  3. 统计时分复用
  4. 波分复用：光的频分复用。
  5. 码分复用CDM：常用的名词是码分多址 CDMA。各用户使用经过特殊挑选的不同码型，因此彼此不会造成干扰。这种系统发送的信号有很强的抗干扰能力，其频谱类似于白噪声，不易被敌人发现。每一个比特时间划分为 m 个短的间隔，称为码片(chip)。
  6. 码分复用：当码片序列长度为mm bit发送的信息的速率为bb bit/s，则实际的发送速率要达到mbmb bit/s
  7. CDMA 的重要特点：每个站分配的码片序列不仅必须各不相同，并且还必须互相正交(orthogonal)。在实用的系统中是使用伪随机码序列。
  8. 待补

2.5 数字传输系统

  1. 待补

第三章 数据链路层

  1. 链路层使用的信道分为两种类型：
    • 点对点信道——一对一
    • 广播信道——一对多

3.1 使用点对点信道的数据链路层

  1. 链路(link)：是一条无源的点到点（一个节点到相邻节点）的物理线路段，中间没有任何其他的交换结点。一条链路只是一条通路的一个组成部分。
  2. 数据链路(data link)：除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。最常用的就是网络适配器（即网卡）。
  3. 数据链路层传送的是帧。
  4. 数据链路层的三个基本问题：封装成帧、透明传输和差错检测。
  5. 早期的数据通信协议曾叫作通信规程 (procedure)。因此在数据链路层，规程和协议是同义语。
  6. 封装成帧(framing)：就是在一段数据的前后分别 添加首部和尾部，然后就构成了一个帧。确定 帧的界限。首部和尾部的一个重要作用就是进行帧定界。
  7. 每一种链路层协议都规定了所能传送的帧的数据部分长度上限——最大传送单元 MTU (Maximum Transfer Unit)。
  8. 控制字符SOH(Start Of Header)放在一帧的最前面，EOT(End Of Transmission)放在一帧的结束。如果只有SOH没有EOT则丢弃。
  9. 透明传输：如果在数据中发现非ASCII字符并且与SOH或EOT一致，那么会错误地“找到数据帧边界”。若发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”，则在前面插入一个转义字符 “ESC”(其十六进制编码是 1B)。
  10. 字节填充(byte stuffing)或字符填充(character stuffing)——接收端的数据链路层在将数据送往网 络层之前删除插入的转义字符
  11. 透明传输的”透明“：指的是某一个实际存在的事物看起来却好像不存在一样。
  12. 差错检测：在传输过程中可能会产生比特差错: 1可能会变成0而0也可能变成1。在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)。误码率与信噪比有很大的关系。
  13. 在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。在发送端，先把数据划分为组。假定每组 k 个比特。n 假设待传送的一组数据 M = 101001(现在 k = 6)。我们在 M 的后面再添加供差错检测用的 n 位冗余码一起发送。
  14. 循环冗余码的计算，待补
  15. 在数据后面添加上的冗余码称为帧检验序列 FCS
  16. CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。
  17. 仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(accept)。“无差错接受”是指:“凡是接受的帧(即不包括丢弃的帧)，我们都能以非常接近于 1 的 概率认为这些帧在传输过程中没有产生差错”。也就是说:“凡是接收端数据链路层接受的帧 都没有传输差错”(有差错的帧就丢弃而不接 受)。要做到“可靠传输”(即发送什么就收到什么) 就必须再加上确认和重传机制。

3.2 点对点协议 PPP

  1. 现在全世界使用得最多的数据链路层协议是点对点协议 PPP (Point-to-Point Protocol)。
  2. PPP 协议应满足的需求：
    • 简单——这是首要的要求：互操作性提高了
    • 封装成帧：必须规定特殊字符作为帧定界符
    • 透明性
    • 多种网络层协议：同一条物理链路上同时支持多种网络层协议
    • 多种类型链路
    • 差错检测：立刻丢弃有差错的帧
    • 检测连接状态
    • 最大传送单元：是数据链路层的帧可以负载的数据部分的最大长度，而不是帧的总长度
    • 网络层地址协商
    • 数据压缩协商
  3. PPP 协议不需要的功能:
    • 纠错
    • 流量控制
    • 序号
    • 多点线路
    • 半双工或单工链路
  4. PPP 协议的组成：
    • 一个将 IP 数据报封装到串行链路的方法。
    • 链路控制协议 LCP (Link Control Protocol)。
    • 网络控制协议 NCP (Network Control Protocol)。
  5. PPP 协议的帧格式:
    PPP 有一个 2 个字节的协议字段。
    当协议字段为 0x0021 时，PPP 帧的信息字段就是IP 数据报。
    若为 0xC021, 则信息字段是 PPP 链路控制数据。若为 0x8021，则表示这是网络控制数据。
    PPP 协议的帧格式
  6. PPP 协议的信息字段长度是可变的，但不超过1500字节。
  7. PPP 透明传输问题：当 PPP 用在同步传输链路时，协议规定 采用硬件来完成比特填充(和 HDLC 的 做法一样)。当 PPP 用在异步传输时，就使用一种特殊的字符填充法：
    • 将信息字段中出现的每一个 0x7E 字节转变成为 2 字节序列(0x7D, 0x5E)。
    • 若信息字段中出现一个 0x7D 的字节，则将其转变成为 2 字节序列(0x7D, 0x5D)。
    • 若信息字段中出现 ASCII 码的控制字符 (即数值小于 0x20 的字符)，则在该字 符前面要加入一个 0x7D 字节，同时将该字符的编码加以改变。
  8. 零比特填充：PPP 协议用在 SONET/SDH 链路时，是使用同步传输，这时 PPP 协议采用零比特填充方 法来实现透明传输。信息字段每出现5个连续的1，则添加一个0，这样不会产生控制字符F相同的信息部分。
  9. PPP 协议之所以不使用序号和确认机制是出于以下的考虑：
    • 在数据链路层出现差错的概率不大时，使用比较简单的 PPP 协议较为合理。
    • 在因特网环境下，PPP 的信息字段放入的数 据是 IP 数据报。数据链路层的可靠传输并不能够保证网络层的传输也是可靠的。
    • 帧检验序列 FCS 字段可保证无差错接受。
  10. PPP 协议的工作状态：暂无

3.3 使用广播信道的数据链路层

发表于

题目链接 - Codeforces #469D

题目简述：

给出n个数据中心，把每天的时间分为h部分，每个数据中心有个更新时间hi(0≤hi≤h)h_i(0\leq h_i \leq h)。m个客户，每个客户的数据放在2个数据中心。
现在要调整尽量少的数据中心，让这些数据中心时间向后调整一个小时。如果2个数据中心的时间一致，则会发生风险，不允许这种情况的发生，问至少调整几个数据中心，并且输出是哪些。

题目思路：

这题分析之后，如果一个客户关联的两个数据中心u,vu,v，如果hu+1=hvh_u+1=h_v则拉一条u到vu到v的边，如果hv+1=huh_v+1=h_u则拉一条v到uv到u的边，(如果hi+1=hh_i+1=h则hi+1h_i+1视为0)。这样就产生了一个关联关系，每条边的源方向如果需要被选中，那么目的方向也必须被选中，图就建立起来了。
然后对着这个图跑Tarjan。如果要选择在上层的强连通分量，那么下层的必须要选，答案将会变大，所以只选择最底部的强连通分量。然后只需要在最底部的强连通分量里面选择一个元素最少的强连通分量，将这个强连通分量输出即可。

代码：

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
143
144
145
146
147
148
149
150
151
152
// 巨菜的ACMer-Happier233

#include <bits/stdc++.h>

using namespace std;

//-----
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pw(x) (1ll << (x))
#define bt(x, k) (((x) >> k) & 1)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i, l, r) for(int i=(l);i<(r);++i)
#define per(i, l, r) for(int i=(r)-1;i>=(l);--i)
#define mst(t, v, n) memset(t, v, sizeof(decltype(*(t))) * (n))
#define sf(x) scanf("%d", &(x))
#ifndef ACM_LOCAL
#pragma GCC optimize(2)
#define endl '\n'
#endif

const int N = int(1e5 + 10);
const int M = int(2e5 + 10);
int a[N];
int n, m, h;

inline bool check(int u, int v) {
    return a[u] + 1 == a[v] || a[u] + 1 == a[v] + h;
}

int head[N], tot;
pii eg[M];

void addEdge(int u, int v) {
    eg[tot] = {v, head[u]};
    head[u] = tot++;
}

int dfn[N], low[N], st[N], belong[N], num[N];
bool inst[N];
int idx, top, scc;

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    st[top++] = u;
    inst[u] = true;
    for (int i = head[u]; i != -1; i = eg[i].second) {
        int v = eg[i].first;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inst[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    int v;
    if (dfn[u] == low[u]) {
        scc++;
        do {
            v = st[--top];
            inst[v] = false;
            belong[v] = scc;
            num[scc]++;
        } while (u != v);
    }
}

void work() {
    fill_n(dfn, n + 1, 0);
    fill_n(num, n + 1, 0);
    fill_n(inst, n + 1, false);
    idx = top = scc = 0;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            tarjan(i);
    }
}

bool g[N];

void solve() {
    while (cin >> n >> m >> h) {
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        tot = 0;
        fill_n(head, n + 1, -1);
        rep(i, 0, m) {
            int u, v;
            cin >> u >> v;
            if (check(u, v)) {
                addEdge(u, v);
            }
            if (check(v, u)) {
                addEdge(v, u);
            }
        }
        work();
        fill_n(g, n + 1, 0);
        for (int u = 1; u <= n; u++) {
            for (int i = head[u]; ~i; i = eg[i].second) {
                int v = eg[i].first;
                if (belong[u] == belong[v])continue;
                g[belong[u]] = true;
            }
        }
        int mn = -1;
        for (int i = 1; i <= scc; i++) {
            if (g[i]) continue;
            if (mn == -1 || num[i] < num[mn]) {
                mn = i;
            }
        }
        cout << num[mn] << endl;
        for (int i = 1, c = 0; i <= n; i++) {
            if (belong[i] == mn) {
                cout << i << " \n"[++c == num[n]];
            }
        }
    }
}

int main() {
#ifdef ACM_LOCAL
    freopen("./data/std.in", "r", stdin);
    // freopen("./data/std.out", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif

#ifdef ACM_LOCAL
    auto start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    auto end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}

发表于 更新于 分类于 ， ， ，

总结

这场比赛看到参赛队伍名单的时候就感觉是神仙云集，亚历山大，北京并没有想象的那么冷，中国传媒大学还是很大很厉害的。
热身赛的时候vscode的cpp扩展貌似因为权限问题没有跑起来，正赛的时候也没时间去尝试怎么调教vscode了，但vscode写代码还是可以的，写完丢codeblock跑。
正赛开始的签到题队友签了半小时没有调处来，然后我上去写，开了12个大小的数组，但因为少写一个"dec"，wa1，然后因为没仔细看题，所以是最后额外读了一个，等于读入了n+1个，最后应该i∈[0,n]i \in [0,n]但写了一个i∈[0,n)i \in [0,n)少了个等号又wa1，最后用时一小时AC加两次罚时。
构造题我们面向题面整了3个小时，没有整出来(内心OS: 出题人太坏坏了)。最后发现这个构造的确有点简单，就是个printf题，我只是一个没有思想的菜鸡啊。
这场是我今年第一次打铁，感受到了去年南京的感觉，希望接下来的EC能有机会上场吧。

题解

暂无，待补

发表于 更新于 分类于 ， ， ， ，

题目链接 - 计蒜客 39277

题目简述：

给出一颗有n个节点的树，第2~n的父亲和边权
求树上任意两点u,v (u < v)的路径上的子集中的两点间的疑惑和为0的个数

∑u=1n∑v=1n∑u′⊆E(u,v)∑v′⊆E(u,v)n[u<v][u′<v′][X(u′,v′)=0]\sum_{u=1}^n{ \sum_{v=1}^n{ \sum_{u'\subseteq{E(u,v)}}{ \sum_{v'\subseteq{E(u,v)}}^n{ [u<v][u'<v'][X(u',v')=0] } } } }

E(u, v)是从u到v路径上的所有点，X(u, v)是u到v路径上所有的边权异或和

题目思路：

这样每次在确定根之后，可以把边权转换为点权，根节点的权值为0。转化完之后就可以用树分治解决这个问题。

每次找到一个合法的X(u,v)=0之后，以v作为根的视角去看u的子树大小作为sons[u]，再以u作为根的视角去看v的子树大小作为sons[v]，那么(u,v)这条合法路径对答案的贡献就是sons[u]*sons[v]

计算答案的时候需要特殊处理直接到达根节点的所有边的情况，假设u为根，v为子节点。

因为每次根不同，所以不知道以x作为树根，y作为子节点的时候，y子树的大小，所以预处理这颗树，算出每个(u,v)边对应的v子树的大小，每次计算答案的时候可以很方便的转化每个子树大小。

代码：

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
// 巨菜的ACMer-Happier233

#include <bits/stdc++.h>

using namespace std;

//-----
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pw(x) (1ll << (x))
#define bt(x, k) (((x) >> k) & 1)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i, l, r) for(int i=(l);i<(r);++i)
#define per(i, l, r) for(int i=(r)-1;i>=(l);--i)
#define mst(t, v, n) memset(t, v, sizeof(decltype(*(t))) * (n))
#define sf(x) scanf("%d", &(x))
#ifndef ACM_LOCAL
#pragma GCC optimize(2)
#define endl '\n'
#endif

struct Edge {
    int to, nxt;
    ll w;
};
const int N = int(1e5 + 10);
const int M = N << 1;

struct Grahp {
    int head[N];
    Edge eg[M];
    int tot;

    void init(int n) {
        memset(head, -1, sizeof(int) * ++n);
    }

    inline void addEdge(int u, int v, ll w) {
        eg[tot] = {v, head[u], w};
        head[u] = tot++;
    }
} gh;

bool vis[N];
// q队列, fa祖先, sz是子树大小, smx是子树最大
int q[N], fa[N], sz[N], smx[N];

int froot(int s) {
    int l, r, mn = N, rt = 0;
    q[l = r = 1] = s;
    while (l <= r) {
        int u = q[l++];
        sz[u] = 1;
        smx[u] = 0;
        for (int i = gh.head[u]; ~i; i = gh.eg[i].nxt) {
            int v = gh.eg[i].to;
            if (v == fa[u] || vis[v]) continue;
            fa[v] = u;
            q[++r] = v;
        }
    }
    // 反向遍历所有点算size
    while (--l) {
        int u = q[l];
        int mx = max(smx[u], r - sz[u]);
        if (mx < mn) mn = mx, rt = u;
        if (l == 1) break; // 根节点没有fa
        sz[fa[u]] += sz[u];
        smx[fa[u]] = max(smx[fa[u]], sz[u]);
    }
    return rt;
}

// sons子树方向节点个数, val根到该节点异或和, gc边后继方向的节点个数
int sons[N], gc[M];
ll val[N];
ll ans = 0;
int n;

const int MOD = int(1e9 + 7);

ll nums[N];
int cnt[N];

void go(int s, int rt) {
    fa[s] = rt;
    val[s] = 0;
    int l, r;
    // 不计算s
    q[l = r = 0] = s;
    int m = 0;
    while (l <= r) {
        int u = q[l++];
        nums[m++] = val[u];
        for (int i = gh.head[u]; ~i; i = gh.eg[i].nxt) {
            int v = gh.eg[i].to;
            if (v == fa[u] || vis[v]) continue;
            fa[v] = u;
            q[++r] = v;
            val[v] = val[u] ^ gh.eg[i].w;
            // 这个点方向后面有多少点
            sons[v] = gc[i];
        }
    }
    sort(nums, nums + m);
    m = unique(nums, nums + m) - nums;
    mst(cnt, 0, m);
    // 遍历分支
    for (int j = gh.head[s]; ~j; j = gh.eg[j].nxt) {
        // 分支的根
        int du = gh.eg[j].to;
        if (vis[du]) continue;
        q[l = r = 1] = du;
        while (l <= r) {
            int u = q[l++];
            int k = lower_bound(nums, nums + m, val[u]) - nums;
            (ans += 1ll * sons[u] * cnt[k] % MOD) %= MOD;
            if (val[u] == 0) {
                (ans += 1ll * sons[u] * (n - gc[j]) % MOD) %= MOD;
            }
            for (int i = gh.head[u]; ~i; i = gh.eg[i].nxt) {
                int v = gh.eg[i].to;
                if (v == fa[u] || vis[v]) continue;
                q[++r] = v;
            }
        }
        // 增加这个方向的值
        while (--l) {
            int u = q[l];
            int k = lower_bound(nums, nums + m, val[u]) - nums;
            (cnt[k] += sons[u]) %= MOD;
        }
    }
}

void work(int u) {
    // 换根
    u = froot(u);
    vis[u] = true;
    go(u, 0);
    for (int i = gh.head[u]; ~i; i = gh.eg[i].nxt) {
        int v = gh.eg[i].to;
        if (vis[v]) continue;
        work(v);
    }
}

// 预处理边后继节点个数
int pdfs(int u, int f) {
    int fg_id = -1;
    int s = 1;
    for (int i = gh.head[u]; ~i; i = gh.eg[i].nxt) {
        int v = gh.eg[i].to;
        if (v == f) { // 记录父边ID
            fg_id = i;
            continue;
        }
        int c = pdfs(v, u);
        gc[i] = c;
        s += c;
    }
    // 存在父边
    if (~fg_id) gc[fg_id] = n - s;
    return s;
}

void solve() {
    while (cin >> n) {
        gh.init(n);
        for (int i = 2; i <= n; i++) {
            int u, v;
            ll w;
            u = i;
            cin >> v >> w;
            gh.addEdge(u, v, w);
            gh.addEdge(v, u, w);
        }
        mst(vis, false, n + 1);
        pdfs(1, 0);
        ans = 0;
        work(1);
        cout << ans << endl;
    }
}

int main() {
#ifdef ACM_LOCAL
    freopen("./data/std.in", "r", stdin);
    // freopen("./data/std.out", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif

#ifdef ACM_LOCAL
    clock_t start = clock();
#endif
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
#ifdef ACM_LOCAL
    clock_t end = clock();
    cerr << "Run Time: " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}

发表于 更新于 分类于 ， ， ，

题目链接 - HDU 5274

题目简述：

一棵树有n个节点，每次修改其中一个节点的权值，或者查询从u到v的路径上所有的节点里面是否有出现奇数个的权值
例如：一个路径上出现了 2 2 4 5 5，那答案就是4，题目保证每次查询路径上只有一个点出现奇数次。

题目思路：

这就是一个树上的节点修改，非常简单的树剖模板题。因为题目保证只有一个点出现奇数次，所以用树状数组维护异或和即可。当一个数字出现偶数次，异或和就会重新变为0。但这题有个坑点，a[i]∈N，N为自然数，所以有可能权值为0。所以在树状数组里维护权值+1的异或和即可，每次输出答案-1，这样当没有答案的时候正好可以输出-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
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
// 巨菜的ACMer-Happier233

#include <bits/stdc++.h>

using namespace std;

//-----
typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pw(x) (1ll << (x))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i, l, r) for(int i=(l);i<(r);++i)
#define per(i, l, r) for(int i=(r)-1;i>=(l);--i)
#define sf(x) scanf("%d", &(x))

#define foreg(i, s, eg) for(int i = (s); ~i; i = (eg)[i].nxt)

const double pi = acos(-1);
const ll MOD = ll(1e9 + 7);

struct Edge {
    int e, nxt;
    ll v;

    Edge() = default;

    Edge(int a, ll b, int c = 0) : e(a), v(b), nxt(c) {}

    bool operator<(const Edge &a) const {
        return (a.v == v ? e < a.e : v < a.v);
    }
};

const ll INF = ll(1e11);
const int N = int(2e5 + 10);
const int M = int(6e5 + 10);

struct Graph {
    Edge eg[M];
    int head[N];
    int cnt;

    void init(int n) {
        memset(head, -1, sizeof(int) * ++n);
        cnt = 0;
    }

    inline void addEdge(int x, int y, ll v) {
        eg[cnt] = Edge(y, v, head[x]);
        head[x] = cnt++;
    }

    inline int begin(int p) {
        return head[p];
    }

    inline Edge &operator[](int i) {
        return eg[i];
    }

    inline int next(int i) {
        return eg[i].nxt;
    }
} gh;

struct TreeChain {
    int top[N]; // 链条顶端点ID
    int fa[N]; // 父亲节点
    int son[N]; // 重儿子
    int deep[N]; // 深度
    int num[N]; // 儿子节点数（包括自己）


    int p[N]; // 点在线段树中的ID
    int fp[N]; // 线段树中ID对应的点
    int fe[N]; // 每个点到父亲节点的边ID
    int ep[N]; // 每个点到父节点对应的边在线段树中的ID
    // int fep[N]; // 线段树中ID对应的边
    int tot;

    void dfs(int u, int pre, int d) {
        num[u] = 1;
        deep[u] = d;
        fa[u] = pre;
        son[u] = -1;
        fe[u] = -1;
        for (int i = gh.head[u]; ~i; i = gh.eg[i].nxt) {
            int v = gh.eg[i].e;
            if (v == pre) {
                fe[u] = i;
                continue;
            }
            dfs(v, u, d + 1);
            num[u] += num[v];
            if (son[u] == -1 || num[v] > num[son[u]]) {
                son[u] = v;
            }
        }
    }

    void getpos(int u, int sp) {
        top[u] = sp;
        p[u] = tot++;
        fp[p[u]] = u;
        ep[fe[u] >> 1] = p[u];
        if (son[u] == -1) return;
        getpos(son[u], sp);
        for (int i = gh.head[u]; ~i; i = gh.eg[i].nxt) {
            int v = gh.eg[i].e;
            if (v == son[u] || v == fa[u]) continue;
            getpos(v, v);
        }
    }

    void build(int start, int root) {
        tot = start; // start是线段树中的ID起始数值
        dfs(root, 0, 0);
        getpos(root, root);
    }
} treec;

struct BITree {
    int n;
    ll c[N];

    void init(int _n) {
        n = _n;
        memset(c, 0, sizeof(ll) * ++n);
    }

    void change(int pos, ll v) {
        for (int i = pos; i < n; i += i & (-i))
            c[i] ^= v;
    }

    ll query(int x) {
        ll ans = 0;
        for (int i = x; i > 0; i -= i & (-i))
            ans ^= c[i];
        return ans;
    }

    ll query(int l, int r) {
        if (r < l) swap(l, r);
        return query(r) ^ query(l - 1);
    }
} tree;

ll query(int u, int v) {
    int f1 = treec.top[u];
    int f2 = treec.top[v];
    ll ans = 0;
    while (f1 != f2) {
        if (treec.deep[f1] < treec.deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        ans ^= tree.query(treec.p[f1], treec.p[u]);
        u = treec.fa[f1];
        f1 = treec.top[u];
    }
    if (treec.deep[u] > treec.deep[v]) {
        swap(u, v);
    }
    ans ^= tree.query(treec.p[u], treec.p[v]);
    return ans;
}

int _tc = 0;
int val[N];

void solve() {
    int n, m, q;
    cin >> n >> q;
    m = n - 1;
    gh.init(n);
    tree.init(n);
    rep(i, 0, m) {
        int a, b;
        cin >> a >> b;
        gh.addEdge(a, b, 0);
        gh.addEdge(b, a, 0);
    }
    rep(i, 0, n) {
        cin >> val[i + 1];
        val[i + 1]++;
    }
    treec.build(1, 1);
    rep(i, 0, n) {
        int p = treec.p[i + 1];
        tree.change(p, val[i + 1]);
    }
    rep(i, 0, q) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 1) {
            ll ans = query(x, y);
            cout << (ans - 1) << endl;
        } else {
            tree.change(x, val[x]);
            tree.change(x, val[x] = y + 1);
        }
    }
}


int main() {
#ifdef ACM_LOCAL
    freopen("./data/std.in", "r", stdin);
    // freopen("./data/std.out", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}