「考试总结」ZROI-21-CSP7连-DAY1 总结

发表于 更新于 分类于
ZROI-21-CSP7连-DAY1 总结

估计是温水煮青蛙，本场比赛比较水。

#T1

#Problem

一种递归定义的数列（字符串列？）：第一项为 1，后面的每一项形式为上一项自左往右 相邻的相同数字个数+该数字，比如第二项为 11，表示 1 个 1，问第 \(n(n\leq 25)\) 项。

#Solution

就是简单模拟，没有难度。

#Code

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
#include <bits/stdc++.h>
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))
using namespace std;

const int N = 100010;
const int INF = 0x3fffffff;

int n, t[N][2], cnt, len, tlen, lst;

int main() {
    scanf("%d", &n);
    t[len = 1][1] = 1;
    for (int i = 2; i <= n; ++ i) {
        tlen = 0, lst = 0, cnt = 0;
        for (int j = 1; j <= len; ++ j) {
            if (j != 1 && t[j][(i - 1) % 2] != lst) {
                t[++ tlen][i % 2] = cnt;
                t[++ tlen][i % 2] = lst; cnt = 0;
            }
            lst = t[j][(i - 1) % 2]; ++ cnt;
        }
        t[++ tlen][i % 2] = cnt;
        t[++ tlen][i % 2] = lst;
        len = tlen;
    }
    for (int i = 1; i <= len; ++ i)
      printf("%d", t[i][n % 2]);
    return 0;
}

#T2

#Problem

一个严格递增的序列 \(a_i\)，支持两种操作：

  • 区间修改
  • 查询是否有位置满足 \(a_i=i\)

#Solution

我们来考虑所有满足 \(a_i=i\) 的位置中 \(i\) 最大的，不难发现如果存在这样的位置，那么其一定具有二分性，即设该位置为 \(i\)，那么对于所有的 \(j<i\)，有 \(a_j\leq j\)，对于 \(j>i\)，则有 \(a_j > i\)，于是我们可以依靠此性质进行二分，注意我们需要判断二分结束后的位置是否满足条件（赛时脑抽忘判了 \(100pts\to 10pts\) QwQ），如果不满足，那么意味着不存在这样的位置，同时需要注意边界。

关于区间修改，我们可以直接采用线段树维护，由于线段树本身便是天然的二分结构，所以二分的过程可以直接在线段树上进行。总体时间复杂度为 \(O(k\log n).\)

#Code

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
#include <bits/stdc++.h>
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))
using namespace std;

const int N = 20000010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

struct Node {int ls, rs, mx, tag;} p[N];

int cnt, n, m, a[N], rt;

inline void add(int k, int x) {
    p[k].tag += x; p[k].mx += x;
}

inline void pushdown(int k) {
    int ls = p[k].ls, rs = p[k].rs;
    if (ls) add(ls, p[k].tag);
    if (rs) add(rs, p[k].tag);
    p[k].tag = 0;
}

inline void pushup(int k) {
    p[k].mx = p[p[k].rs].mx;
}

void build(int &k, int l, int r) {
    if (!k) k = ++ cnt;
    int mid = l + r >> 1;
    if (l == r) {p[k].mx = a[l]; return;}
    build(p[k].ls, l, mid);
    build(p[k].rs, mid + 1, r); pushup(k);
}

void modify(int k, int l, int r, int x, int y, int c) {
    if (x <= l && r <= y) {add(k, c); return;}
    int mid = l + r >> 1; pushdown(k);
    if (x <= mid) modify(p[k].ls, l, mid, x, y, c);
    if (mid < y) modify(p[k].rs, mid + 1, r, x, y, c);
    pushup(k);
}

int get_pos(int k, int l, int r) {
    if (l == r) {return p[k].mx == l ? l : 0;}
    pushdown(k); int mid = l + r >> 1;
    int lval = p[p[k].ls].mx;
    if (lval > mid) return get_pos(p[k].ls, l, mid);
    if (lval < mid) return get_pos(p[k].rs, mid + 1, r);
    return mid;
}

int main() {
    read(m); read(n);
    for (int i = 1; i <= n; ++ i) read(a[i]);
    a[n + 1] = n + 1; build(rt, 0, n + 1); -- m;
    int pos1 = get_pos(rt, 0, n + 1);
    if (pos1 < 1 || pos1 > n) printf("NO\n");
    else printf("YES\n");
    while (m --) {
        int l, r, c; read(l); read(r); read(c);
        modify(rt, 0, n + 1, l, r, c);
        int pos = get_pos(rt, 0, n + 1);
        if (pos < 1 || pos > n) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

#T3

#Problem

给定序列 \(a_i\)，\(q\) 个询问，每次询问位于 \(a_l\) 到 \(a_r\) 这个子序列中出现次数为奇数的数的个数。

#Solution

莫队的板子题，不多讲。

#Code

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
#include <bits/stdc++.h>
#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))
using namespace std;

const int N = 500010;
const int INF = 0x3fffffff;

int n, m, a[N], t[N], cnt[N];
int len, res, ans[N];

struct Query {
    int l, r, id;

    inline bool operator < (const Query &b) const {
        if (l / len != b.l / len) return l < b.l;
        if ((l / len) & 1) return r < b.r;
        return r > b.r;
    }
};
Query q[N];

inline void add(int x) {
    ++ cnt[x]; if (cnt[x] & 1) ++ res; else -- res;
}

inline void del(int x) {
    -- cnt[x]; if (cnt[x] & 1) ++ res; else -- res;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
      scanf("%d", &t[i]), a[i] = t[i];
    sort(t + 1, t + n + 1);
    int _n = unique(t + 1, t + n + 1) - t - 1;
    for (int i = 1; i <= n; ++ i)
      a[i] = lower_bound(t + 1, t + _n + 1, a[i]) - t;
    scanf("%d", &m);
    for (int i = 1; i <= m; ++ i)
      scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    len = sqrt(n); sort(q + 1, q + m + 1);
    for (int i = 1, l = 1, r = 0; i <= m; ++ i) {
        while (l > q[i].l) add(a[-- l]);
        while (r < q[i].r) add(a[++ r]);
        while (l < q[i].l) del(a[l ++]);
        while (r > q[i].r) del(a[r --]);
        ans[q[i].id] = res;
    }
    for (int i = 1; i <= m; ++ i)
      printf("%d\n", ans[i]);
    return 0;
}

#T4

本题是 TJOI 的一道原题 [题目链接]

#Problem

求 \(n\) 个点的二叉树的叶结点期望个数，对 \(2148473647\) 取模。

用 \(2148473647\) 做模数就恶心人，最开始以为是 \(2147483647(2^{31}-1)\)，发现这样没有逆元...

#Solution

设 \(f_n\) 表示 \(n\) 个节点的不同二叉树的个数，\(g_n\) 表示 \(n\) 个节点的 \(f_n\) 个二叉树的叶结点总数。答案显然应当是

\[ \dfrac{g_n}{f_n} \]

\(f_n\) 显而易见是 Catalan 数，那么来考虑 \(g_n\) 怎么求，通过打表可以得到如下性质

\[ g_n=nf_{n-1} \]

我们这样考虑证明：

  • 对于每棵 \(n\) 个点 \(k\) 个叶结点的二叉树，如果我们把这 \(k\) 个叶结点分别去掉，可以得到 \(k\) 棵不同的 \(n-1\) 个节点的二叉树；
  • 对于每棵 \(n-1\) 个点的二叉树，我们知道有 \(n\) 个位置可以挂上一个叶结点，所以通过上面的变换，每一棵 \(n-1\) 个点的二叉树可以被得到 \(n\) 次；

于是综合上面两点不难得到 \(g_n=nf_{n-1}\) 的结论，于是有

\[ \dfrac{g_n}{f_n}=\dfrac{nf_{n-1}}{f_n} \]

其中有 \(f_n=\dfrac{\binom{2n}{n}}{n+1}\)，带入化简后可以得到

\[ \dfrac{g_n}{f_n}=\dfrac{nf_{n-1}}{f_n}=\dfrac{n(n+1)}{2(2n-1)}. \]

#Code

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
#include <bits/stdc++.h>
#define ll unsigned long long
#define mset(l, x) memset(l, x, sizeof(l))
using namespace std;

const ll N = 100010;
const ll INF = 0x3fffffff;
const ll MOD = 2148473647;

ll n;

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

int main() {
    scanf("%llu", &n);
    ll res1 = n * (n + 1) % MOD;
    ll res2 = fpow(2 * (2 * n - 1) % MOD, MOD - 2);
    printf("%llu", (res1 * res2 % MOD + MOD) % MOD);
    return 0;
}

期望得分：\(100+100+100+100=400\) 实际得分：\(100+10+100+100=310\) 血亏QwQ