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

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

#T1

#Problem

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

#Solution

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

#Code

#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\le j$，对于 $j>i$，则有 $a_j>i$，于是我们可以依靠此性质进行二分，注意我们需要判断二分结束后的位置是否满足条件（赛时脑抽忘判了 $100pts\to 10pts$ QwQ），如果不满足，那么意味着不存在这样的位置，同时需要注意边界。

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

#Code

#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

#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$ 个二叉树的叶结点总数。答案显然应当是

$${\displaystyle \frac{g_n}{f_n}}$$

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

$$g_n=n{f}_{n-1}$$

我们这样考虑证明：

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

于是综合上面两点不难得到 $g_n=n{f}_{n-1}$ 的结论，于是有

$${\displaystyle \frac{g_n}{f_n}}={\displaystyle \frac{n{f}_{n-1}}{f_n}}$$

其中有 $f_n={\displaystyle \frac{(\genfrac{}{}{0ex}{}{2n}{n})}{n+1}}$，带入化简后可以得到

$${\displaystyle \frac{g_n}{f_n}}={\displaystyle \frac{n{f}_{n-1}}{f_n}}={\displaystyle \frac{n(n+1)}{2(2n-1)}}.$$

#Code

#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