T1

题目描述

小猿非常热爱学习，所以他在猿辅导上购买了$N$节课来提升自己，每节课有一个开始时间$S$和结束时间$E$（$S$和$E$均用正整数表示）。买完课程后，粗心的小袁发现这些课程之间有些时间冲突，幸好小猿有一种“一心多用”的超能力，能同时兼顾$K$节课上课。当然是$K$越大，使用这种能力就越累。请问小猿最少需要一心几用，才能上完所有他买的课程呢？

输入描述

第一行输入为$N$（$N \leq 200000$），表示购买课程数。
接下来$N$行，每行输入两个数$Si、Ei$（$0 < Si < Ei < 1e9$），为第$i$节课的起止时间

输出描述

请输出最小满足条件的$K$

示例1

输入

4
1 4
1 2
2 3
3 4

输出

2

算法

(堆) $O(nlog(n))$

1. 按开始时间和结束时间从小到大排序
2. 使用堆维护时间区间，对于排序后两个课程$a$和$b$来说，如果$a$和$b$无法分开上，则须满足$b$的开始时间小于$a$的结束时间
3. 答案为堆中同时存在的课程数量的最大值

时间复杂度

输入数据的复杂度为$O(n)$，排序课程时间的复杂度为$O(nlog(n))$，维护堆的时间开销为$O(nlog(n))$，因此总时间复杂度为$O(nlog(n))$

C++ 代码

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

#define x first
#define y second

typedef pair<int, int> PII;

int n, ret;
vector<PII> course;

int main() {
    cin >> n;

    for (int i = 0; i < n; i ++ ) {
        int s, e; cin >> s >> e;
        course.push_back({s, e});
    }

    sort(course.begin(), course.end());

    priority_queue<int, vector<int>, greater<int>> q;

    for (int i = 0; i < n; i ++ ) {
        while (q.size() && q.top() <= course[i].x) q.pop();
        q.push(course[i].y);
        ret = max(ret, (int)q.size());
    }

    cout << ret;

    return 0;
}

T2

题目描述

猿辅导组织一次抽奖活动，奖券的发放方式是：某个同学拿到全部的奖券，然后自己留一张，其他的分发给他周边的同学；其他同学收到奖券后，自己留一张，再分发给周边还未收到过奖券的同学，以此类推，知道每个同学都收到一张奖券为止。
开奖时，每张奖券会得到一个奖励值，每个同学最终奖励值除了要包含自己奖券的奖励之外，还可以额外加上从经由自己发出去的奖券中选择出一部分奖券的奖励值。但是如果不选择某张奖券，那么经由持有这张没被选择奖券的同学发出去的所有奖券都不能再选了。比如A把BCD的奖券发给了B，B再把CD的奖券分发给了CD，A可以只选择自己的奖券，可以选择ABCD的奖券，也可以选择AB或ABC或ABD的奖券，但是不能只选择AC或者AD的奖券。
奖励值当然是越大越好，大家一定也想知道最终大奖是多少，请你帮大家算一下吧。

输入描述

第一行输入$N$，表示$N$个同学，$N \leq 100000$；
第二行到第$N + 1$行输入两个整数$A、B$，其中$A$表示某同学持有奖券的奖励值，$-1e9 \leq A \leq 1e9$，$B$表示该奖券是第$B$行的同学发给他的；
$B=0$表示他是第一个发奖券的同学。

输出描述

输出整数$M$，为所有同学中获得的最大的奖励值除$1000000003$的模。

示例1

输入

3
2 0
1 2
-1 2

输出

3

算法

($DFS$) $O(n)$

1. 传递奖券的线路可构成一个有向无环图，$N$个同学一定只有$N - 1$条边
2. 开一个哈希表记录每个同学能获得的最大奖励，下次搜到这个同学时直接返回结果
3. 注意节点下标从2开始，到$N + 1$

时间复杂度

每个节点最多只会被遍历一次，时间复杂度是$O(n)$，额外需要$O(n)$的空间复杂度存储哈希表

C++ 代码

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

const int N = 1e5 + 10, mod = 1e9 + 3;

int n, root, ret;
int h[N], e[N], ne[N], idx;
int s[N];
unordered_map<int, int> f;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u) {
    if (f.count(u)) return f[u];

    int t = s[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        t = (t + max(0, dfs(j))) % mod;
    }

    f[u] = t;
    ret = max(ret, f[u]);

    return t;
}

int main() {
    cin >> n;

    memset(h, -1, sizeof h);

    for (int i = 2; i <= n + 1; i ++ ) {
        int a, b; cin >> a >> b;
        s[i] = a;
        if (!b) root = i;
        else add(b, i);
    }

    dfs(root);

    cout << ret;

    return 0;
}

T3

题目描述

小猿参加了猿辅导的编程培训课程，课后老师给大家留了作业，要求写一个简化版的模板解析器，需要具备的功能是：给一个模板字符串注入数据，输出模板解析后的字符串，保证了模板中的变量一定存在于注入的对象数据中。注入的数据是一个对象，表现形式是{key1: value1, key2: value2, key3: value3}，$key$是一个字符串，$value$可以是对象、布尔值、字符串和包含相同元素的数组，[key, value]对数为正整数。
模板字符串由一系列标签元素和普通元素组成，标签元素的形态是：<name a="v" b="t" c="p"></name>，其中标签名字是一个由小写字母组成的长度大于等于1的字符串，比如示例模板中的$div$、$button$等，并且成对出现，比如<div>和</div>。标签元素上由0个或多个属性，每个属性都有一个取值，属性可以是下述解析规则1和2。xxx是该标签元素的内容，可以是标签元素，也可以是普通元素。普通元素是一个常量或下述解析规则的动态值，常量是字符串、数字、空格、换行符和可视化的符号。

解析规则如下：
1. 解析指令【y-if="{{xxx}}"】，根据双大括号中变量值判断当前标签元素是否存在，取值范围如下：
- $true$，类型$boolean$，保留标签元素及其子元素；
- $false$，类型$boolean$，移除标签元素及其子元素；
- $undefined$，表达式$xxx$对应的变量不存在，移除标签元素及其子元素；
2. 解析指令【y-for="{{xxx, yyy in zzz}}"】，对当前标签元素做$for$循环输出，每个输出元素用换行符‘\n’分隔。指令的值域格式，如示例中的lesson, index in list，其中，变量$list$是一个数组，可以在注入的数据中找到，数组中的每个元素类型一致。变量$index$表示数组的索引，变量$lesson$表示这个数组中对应索引$index$的元素，二者顺序固定。数组索引和元素的变量名（$index$和$lesson$）可以是一个任意的由小写字母组成的长度大于等于1的字符串（注：$y-for$和$y-if$不会同时出现在一个标签中）
3. 注入动态值{{xxx.yyy}}，双括号表示获取注入数据中的变量值，$xxx.yyy$是注入数据$data$的$xxx$属性对应的对象的$yyy$属性的值，该变量值是一个$string$，比如示例中的{{lesson.teacher}}，输出$lesson$对象的$teacher$属性的值。如果注入的变量值不存在，则输出空字符串
4. 删除注释所在的一行，注释以<!--开头、以-->结尾，独占一行，如示例中的<!-- 卡片区域 -->
5. 除了注释以外，标签元素、解析指令y-if、解析指令y-for都存在嵌套情况

输入描述

输入分为两部分，用两个空行分开
第一部分共$N$行，是一个对象$Object$，包含模板字符串中需要的所有数据，数据类型有$string、boolean、array、object$；
第二部分共$M + 1$行，前M行是一个模板字符串，至少包含上述的一条规则$M > 1$，最后一行是字符串end，表示输入结束。

输出描述

对于每组测试数据，输出解析后的字符串

示例1

输入

{
    "isMain": false,
    "list": []
}

<div class="head">
<button y-if="{{isMain}}"></button>
</div>
<ul class="content">
<!-- 卡片区域 -->
<li class="card isMain" y-for="lesson, index in list">
    <div class="card-title">
        <i y-if="{{lesson.label}}">{{lesson.label.type}}</i>
        {{lesson.title}}
    </div>
    班课<span class="bold">-</span>老师：{{lesson.teacher}}
    <div class="lesson-time">{{lesson.time}}<i class="tt"></i></div>
</li>
</ul>
end

输出

<div class="head">

</div>
<ul class="content">

</ul>

说明

样例中$button$和$li$标签都需要删除，删除范围为标签头至标签尾，保留标签范围以外的换行

算法

(不会) $O(?)$

有没有大佬能a这道题的

T1（补招专场）

题目描述

用$N$（$N \leq 10$）个0-9的数字组成一个“有效”数（即没有前置0的整数），求这些组成的数中能被$K$（$0 < K < 10 ^ {10}$）整除的最小数字。

输入描述

输入分两行，第一行输入$N$，$K$，第二行输入$N$个数字。

输出描述

输出满足条件的最小数（不含前置0），如果没有满足条件的数输出—1。

示例1

输入

4 7
4 0 1 3

输出

1043

算法

(dfs) $O(10!)$

时间复杂度

C++ 代码

T2（补招专场）

题目描述

小猿在加载一个网页，这个网页共需要$N$个相关资源，这些资源之间一些依赖关系。如果这些资源中存在循环依赖，我们认为这个网页不能加载成功，否则可以加载成功。存在循环依赖是指，这些资源中存在的资源X，X依赖的资源Y直接或间接依赖于X。你能帮助小猿判断一下这个网页能否加载成功吗？

输入描述

第一行输入T（T ≤ 10），表示输入T组数据。
每组数据第1行，输入一个数N（1 ≤ N ≤ 500）表示该组case有编号为1-N的N项资源。
每组数据第2行到N+1行，输入一个$N \times N$的01矩阵，矩阵第$i$行第$j$列数字为$a[i][j] = 0$。

输出描述

输出包含T行，每行输出对应每组case中是否存在循环依赖。存在输出1，不存在输出0。

示例1

输入

2
3
0 1 0
0 0 1
1 0 0
3
0 1 0
0 0 0
0 0 0

输出

1
0

算法

(拓扑排序) $O(T \times N ^ 2)$

时间复杂度

C++ 代码