T1

题目描述

给定一棵二叉树，二叉树每个节点都有一个唯一的正整数值代表节点，在遍历时，我们使用节点的整数值作为标记。输入：二叉树的节点个数，前序和中序遍历结果，分别是第一行、第二行和第三行。输出：二叉树叶子节点的个数。

输入描述

第一行输入二叉树节点个数$N$，其中$0 < N < 30000$
第二行与第三行，分别输入二叉树的前序遍历和中序遍历的结果，每个节点对应唯一整数值

输出描述

二叉树叶子个数

示例1

样例输入

3
1 2 3
2 1 3

样例输出

2

算法

(递归) $O(n)$

1. 递归构建二叉树
2. 递归遍历二叉树的每个节点，遇到叶子节点就更新答案

时间复杂度

建树过程中使用哈希表保存了每个节点中序遍历对应的下标，因此在递归过程中查找时间为$O(1)$，每个节点都会被遍历并且创建，总时间复杂度为$O(n)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

const int N = 30010;

int n, ret;
int preorder[N], inorder[N];
unordered_map<int, int> S;

struct Node {
    int val;
    Node *left, *right;
    Node(int x) : val(x), left(NULL), right(NULL) {}
};

Node* build(int pl, int pr, int il, int ir) {
    if (pl > pr) return NULL;
    int k = S[preorder[pl]];
    auto root = new Node(preorder[pl]);
    root->left = build(pl + 1, pl + k - il, il, k - 1);
    root->right = build(pr + k + 1 - ir, pr, k + 1, ir);
    return root;
}

void dfs(Node* root) {
    if (!root) return;
    if (!root->left && !root->right) {
        ret ++ ;
        return;
    }

    dfs(root->left), dfs(root->right);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> preorder[i];
    for (int i = 0; i < n; i ++ ) {
        cin >> inorder[i];
        S[inorder[i]] = i;
    }

    auto root = build(0, n - 1, 0, n - 1);
    dfs(root);
    cout << ret;

    return 0;
}

T2

题目描述

小明在学习一种编码协议，二进制数据可以用一串16进制的字符表示（0-9、A-F）。其中的“0010”是这个协议的特殊字符串，不允许出现；现在给出一串16进制的字符串s，问：最少去掉几个字符，使得剩下的字符串中不存在“0010”。

输入描述

第一行$t$（$1 \leq t < 1000$），表示接下来有$t$个样例；
每个样例一行字符串s，s的长度不大于$10^5$。

输出描述

每个样例一行，输出最少去掉字符数。

示例1

样例输入

2
0123456789ABCDEF
001023456789ABCDEF00

样例输出

0
1

说明

样例1，给出的字符串不包括0010，不需要去掉字符；
样例2，包括一个0010，可以去掉其中的1，剩下00023456789ABCDEF00，只需要去掉1个字符。

算法

(枚举) $O(T \times k)$

1. 如果出现“0010”，贪心删掉‘1’
2. 考虑两个“0010”的相交情况，可能出现如下4种：
   • 00100010：删2次
   • 0010010：删2次
   • 001010：删1次
   • 00110：不需要删除
3. 综合这几种情况来看，枚举“0010”出现的次数即可

时间复杂度

枚举$T$组长度为$O(k)$的字符串，总时间复杂度为$O(T \times k)$

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

int T;
string s;

int main() {
    cin >> T;
    while (T -- ) {
        cin >> s;
        int ret = 0;
        for (int i = 0; i + 3 < s.size(); i ++ )
            if (s.substr(i, 4) == "0010")
                ret ++ ;
        cout << ret << endl;
    }

    return 0;
}

T3

题目描述

某视频网站上有$N$个视频，每个视频时长为$L_i$秒。产品经理找到你，希望你帮忙在其中插入$M$个广告。一个视频离得两个广告必须间隔一段时间（间隔时间可以为0，且一个视频内可无限次插入广告）。考虑到用户体验，他希望这个间隔时间尽可能长。为方便实现，间隔时间是一个整数。请你帮忙计算一下，这个间隔时间最大可以设置为多少秒？如果不能插入广告，输出0。

输入描述

第一行有两个整数$N$、$M$（$1 \leq N \leq 100000, N < M \leq 5000000$）
第二行有$N$个整数$L_i$，表示视频时长（$1 \leq L_i \leq 1000000000$）

输出描述

一个整数，表示最大的间隔时间

示例1

样例输入

3 9
90 100 120

样例输出

45

算法

(二分) $O(nlog(n))$

1. 如果较大的间隔时间满足要求，那么小于它的所有间隔时间也可以
2. 时间间隔越短，插入的广告数量就越多
3. 具有单调性，可以使用二分
4. 答案的上界为最长的视频时长，此时可以插入2条广告（开头一次，结尾一次）

时间复杂度

总共要进行$O(log(n))$时间判断答案是否合法，判断时需要$O(n)$的时间枚举每个视频时长计算最多能塞进多少广告，因此总的时间复杂度为$O(nlog(n))$

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, m;
int L[N];

bool check(int mid) {
    int cnt = 0;
    for (int i = 0; i < n; i ++ ) cnt += L[i] / mid + 1;
    return cnt >= m;
}

int main() {
    cin >> n >> m;
    int l = 0, r = 0;
    for (int i = 0; i < n; i ++ ) {
        cin >> L[i];
        r = max(r, L[i]);
    }

    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << l;

    return 0;
}

T4

题目描述

在$n$个正整数中，任意挑选$k$个（不可重复挑选，$0 \leq k \leq n$）数字的和记为$sum$，另有一个正整数$m$，请问$sum \% m$的最大值是多少？

输入描述

第一行为两个正整数，分别为$n$、$m$
第二行为$n$个正整数

输出描述

一个数$x$，$x$表示$sum \% m$的最大值

示例1

样例输入

5 5
1 2 3 4 5

样例输出

4

备注

数据范围
$2 \leq m \leq 1e^9 + 7$
30%的数据（$1 \leq n \leq 15$）
40%的数据（$1 \leq n \leq 25$）
40%的数据（$1 \leq n \leq 35$）

算法

(折半) $O(2 ^ \frac{n}{2} \times n)$

1. 把整个数组分成前半段和后半段，每一半枚举所有可能算出来的数存在对应的set中
2. 枚举前半段的所有可能，找后半段与其相加不超过$m$的最大的数，更新答案

时间复杂度

枚举前半段和后半段的所有可能的时间复杂度为$O(2 ^ \frac{n}{2} \times 2)$，查找过程的时间复杂度为$O(2 ^ \frac{n}{2} \times log(2 ^ \frac{n}{2}))$，因此总时间复杂度为$O(2 ^ \frac{n}{2} \times n)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int N = 40;

int n, m, ret;
int a[N];
set<int> set_l, set_r;

void dfs(int u, int n, int t, set<int> &s) {
    if (u == n) {
        s.insert(t);
        return;
    }

    dfs(u + 1, n, (t + a[u]) % m, s);
    dfs(u + 1, n, t % m, s);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    dfs(0, n / 2, 0, set_l);
    dfs(n / 2, n, 0, set_r);

    for (auto l: set_l) {
        auto it = set_r.upper_bound(m - l);
        ret = max(ret, (l + *it) % m);
    }

    cout << ret;

    return 0;
}

标准答案在此