# C

# 题目大意

你现在有 $n$ 个用户， $m$ 个页面，初始时，所有用户都是没有权限访问任何界面的，你现在有三种操作

1 X Y ：授予 $X$ 访问 $Y$ 的权限
2 X ：授予 $X$ 访问所有界面的权限
3 X Y ：请输出 $X$ 是否有访问 $Y$ 的权限

# 数据范围

$1 \le N,M \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$

# 题解

# 错解

一开始没想着数据范围，直接用的 vector<vector<bool>> 开了个 $NM$ 大小的，显然会 $MLE$ ，一个 $bool$ 一个字节， $NM$ 也就是 $4 \times 10^{10}$ 个字节， $40GB$ 了，直接爆炸了

C++

int n, m, q, op, x, y;
map<int, vector<bool>> mp;

void solve () {
    cin >> n >> m >> q;
    vector<bool> flag(n + 1);
    vector<vector<bool>> mp(n + 1, vector<bool>(m + 1));
    
    while (q--) {
        cin >> op;
        if (op == 1)
            cin >> x >> y, mp[x][y] = 1;
        else if (op == 2)
            cin >> x, flag[x] = 1;
        else {
            cin >> x >> y;

            if (flag[x])
                cout << "Yes" << endl;
            else
                cout << (mp[x][y] ? "Yes" : "No") << endl;
        }
    }
}

# 正解

最多只有 $Q$ 2e5 个操作，也就是说，刚刚的 $4 \times 10^{10}$ 个 $bool$ 里，只有 $2 \times 10^{10}$ 个空间会被用到，我们此时可以考虑用 $set$ ，而不是一次把所有空间都开辟出来

C++

int n, m, q, op, x, y;
set<int> mp[N];

void solve () {
    cin >> n >> m >> q;
    vector<bool> flag(n + 1);
    while (q--) {
        cin >> op;
        if (op == 1)
            cin >> x >> y, mp[x].insert(y);
        else if (op == 2)
            cin >> x, flag[x] = 1;
        else {
            cin >> x >> y;

            if (flag[x])
                cout << "Yes" << endl;
            else
                cout << (mp[x].count(y) ? "Yes" : "No") << endl;
        }
    }
}

# D

# 题目大意

给定一个 $A = (a_1, ..., a_n)$ 序列和一个非负整数 $D$ ，你现在要做的是，从 $A$ 中删除尽可能少的元素，得到序列 $B$ ，需要满足：

对于任意 $i, j~(1 \le i < j \le |B|)$ ，满足 $|B_i - B_j| \neq D$
问：需要最少删除的元素个数是？

# 数据范围

$1 \le N \le 2 \times 10^5$
$0 \le a_i, D \le 10^6$

# 题解

从考虑两个数 $|B_i - B_j| \neq D$ 变成，将这个序列变为对于每个数，删到不存在比他大 $D$ 和小 $D$ 的数

我们此时，暂且只考虑对于 $i$ 来说，小 $D$ 的，不考虑另一半
那么考虑使用 $dp$ ， dp[i][0 / 1] 表示不删除 / 删除值为 $i$ 的数后，要满足题意的最小操作次数

先行预处理 $i=minn \to i = minn + d - 1$ $i = m i n n \to i = m i n n + d - 1$ ，这一段数没有 $i - d$ $i - d$ 的前驱，故初始化
- dp[i][1] = cnt[i] ，值为 $i$ 的删掉就是把所有 $i$ 都删掉
再考虑 $i = minn + d \to i = maxx$ $i = m i n n + d \to i = m a x x$
- 如果不删除 $i$ $i$
  - dp[i][0] = min(dp[i - d][0] + cnt[i - d], dp[i - d][1])
  - 取（ $i-d$ 不删的次数 + $i - d$ 的个数）和（ $i-d$ 删掉次数）两者取 $minn$
- 如果删除 $i$ $i$
  - dp[i][1] = min(dp[i - d][0], dp[i - d][1]) + cnt[i]
  - 无论是否删除 $i - d$ ， $i$ 都是要删的，故需要加上 cnt[i] ，再加上（ $i-d$ 删的次数）和（ $i-d$ 不删的次数）取 $minn$ 即可

最后再从 $maxx$ 倒着求到 $maxx - d + 1$ ，因为我们之前考虑的是， dp[i][0 / 1] 只考虑了，比 $i$ 小 $d$ 的不会冲突，所以倒着找也不会出现大 $d$ 冲突的情况 ``

C++

#include <bits/stdc++.h>  
#define int long long  
#define endl '\n'  
  
using namespace std;  
  
const int N = 2e5 + 10;  
int n, d, a[N];   // 存放原数组  
int dp[N * 10][2];   // dp[i][0/1] 表示，选到值 i 时，不删除 / 删除 i 时的最小删除数  
int cnt[N * 10];  
  
void solve() {  
    cin >> n >> d;  
    int minn = 1e18, maxx = 0;  
  
    for (int i = 1; i <= n; i++)  
        cin >> a[i], minn = min(minn, a[i]), maxx = max(maxx, a[i]), cnt[a[i]]++;  
  
    if (d == 0) {  
        int res = 0;  
        for (int i = minn; i <= maxx; i++)  
            // 注意，i 可能没出现过，只要考虑 cnt[i] > 0，即出现过的 i            if (cnt[i] > 0)  
               res += cnt[i] - 1;  
        cout << res << endl;  
        return;  
    }  
  
    // 对于 minn -> minn + d - 1，这里面的数，没有 i - d 可以转移  
    // 故若要删除 i，则必须把所有 i 都删掉，即为 cnt[i]    // 不删除 i 的话，那么值默认为 0 就行  
    for (int i = minn; i < minn + d; i++)  
        dp[i][1] = cnt[i];  
    for (int i = minn + d; i <= maxx; i++) {  
        // 如果不删 i        // dp[i - d][0] + cnt[i - d] 要把 i - d 都删了  
        // dp[i - d][1] 已经把 i - d 删了  
        dp[i][0] = min(dp[i - d][0] + cnt[i - d], dp[i - d][1]);  
  
        // 如果删 i        // dp[i - d][0] + cnt[i] i - d 不删，把 i 全删了  
        // dp[i - d][1] + cnt[i] i - d 和 i 都删了  
        dp[i][1] = min(dp[i - d][0] + cnt[i], dp[i - d][1] + cnt[i]);  
    }  
  
    int res = 0;  
    for (int i = maxx; i >= maxx - d + 1; i--)  
        res += min(dp[i][0], dp[i][1]);  
  
    cout << res << endl;  
}  
  
signed main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr), cout.tie(nullptr);  
  
    int _ = 1;  
    // cin >> _;  
    while (_--)  
        solve();  
}

# E

# 题目大意

你现在有两个空字符串集合 $X$ 和 $Y$ ，有 $Q$ 个操作，每次操作会给你一个整数 $T$ 和字符串 $S$ ，你现在需要做的是

如果 $T$ 为 $1$ ，则把 $S$ 插入集合 $X$
如果 $T$ 为 $2$ ，则把 $S$ 插入集合 $Y$
最后问： $Y$ 中有多少个字符串，不以 $X$ 中的任意一个字符串为前缀

# 数据范围

$1 \le Q \le 2 \times 10^5$
$\sum\limits_{i=1}^{Q} |S_i| \le 10^5$

# 题解

这题很明显考察的是字典树

clear[i] 记录 $i$ 位置是否被清除标记
val[i] 记录 $i$ 位置的值
res[i] 记录 $i$ 结点和其子结点的所有满足题意的字符串数量

现在写好了一个 $update$ 更新操作，其实现是这样的：

如果 clear[root] 为 $1$ ，代表已经被清除，故显然 res[root] = 0
反之，累加 res[0] -> res[26] 和 val[root]

如果是 $1$ 操作的话，那么标记 clear[结尾最后一个字符] 为 $1$
如果是 $2$ 操作的话，那么就需要把 val[结尾最后一个字符] 加一

然后执行 $update$ 操作，由于需要下一层的值，故此处使用递归实现，具体代码如下方所示

C++

const int N = 5e5 + 10;

int trie[N][27], clear[N], val[N], res[N], idx = 0;

int q, op, root = 0;
string s;

void update(int root) {
    if (clear[root]) {
        res[root] = 0;
        return;
    }

    res[root] = val[root];
    for (int i = 0; i < 27; i++)
        res[root] += res[trie[root][i]];
}

void insert(int op, int pos, int& root) {
    if (!root)
        root = ++idx;

    if (pos == s.size()) {
        if (op == 1)
            clear[root] = 1;
        else
            val[root]++;

        update(root);
        return;
    }

    insert(op, pos + 1, trie[root][s[pos] - 'a' + 1]);
    update(root);
}

void solve () {
    cin >> q;
    while (q--) {
        cin >> op >> s;

        insert(op, 0, root);

        cout << res[1] << endl;
    }
}

# F

# 题目大意

给你一个正整数 $N$ ，请你在所有由 1 + * ( ) 组成的算术表达式中，找出一个长度最小的，使得其值为 $N$

# 数据范围

$1 \le N \le 2000$

# 题解

恐怖如斯无法战胜的 $DP$

# C

# 题目大意

# 数据范围

# 题解

# 错解

# 正解

# D

# 题目大意

# 数据范围

# 题解

# E

# 题目大意

# 数据范围

# 题解

# F

# 题目大意

# 数据范围

# 题解

概率论期末复习（md版）

数据库编程