题比较简单。第一题：7min，第二题：13min，第三题：30min

第一题#

题意描述#

一行输入，输入是有 $n$ 个数字，每个数字按照空格隔开。注意： $n$ 在输入并未给出。

然后他有个这样的题意：每个数字都是一只老鼠的编号，它们发现有一个地洞，那么这些老鼠就按照输入的数字编号钻到地洞去，然后如果碰到有重复的编号，说明这只老鼠就在以其它上面的老鼠都需要出来，然后当前编号的老鼠再跳进去，到最后所有的老鼠都要出来。问：老鼠出地洞序列

比如：输入：1 2 3 1 3 3 1，则输出为 3 2 1 3 3 1 1。解释：首先 1 2 3 老鼠入洞，然后碰到 1 ，说明按照 3 2 1 顺序出洞，然后老鼠 1 3 再入洞；碰到 3 ，按照 3 顺序出洞，然后老鼠 3 再入洞；碰到 1，按照 3 1 顺序出洞，老鼠 1 入洞。最后都要出洞，老鼠 1 再出洞。

数据范围#

$1 \le n \le 10^5$
$1 \le A_i \le 10^5$

题解#

栈#

时间复杂度 $O(n)$

其实按照题意已经知道是栈了，洞就是一个栈，满足先进后出的规则

代码如下

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 10010;
7

8
int n;
9
int q[N], stk[N], tt = 0;
10
bool in_stk[N];
11

12
int main() {
13

14
    // freopen("in.txt", "r", stdin);
15
    // freopen("out.txt", "w", stdout);
16

17
    int x;
18
    int flag = 0;
19
    while (~scanf("%d", &x)) {
20
        if (in_stk[x]) {
21
            while (in_stk[x]) {
22
                int y = stk[-- tt];
23
                in_stk[y] = false;
24
                if (flag ++ ) putchar(' ');
25
                printf("%d", y);
26
            }
27
        }
28
        stk[tt ++ ] = x;
29
        in_stk[x] = true;
30
    }
31

32
    while (tt > 0) {
33
        if (flag ++ ) putchar(' ');
34
        printf("%d", stk[-- tt]);
35
    }
36
}

第二题#

题意描述#

给你一个长度为 $n$ 的数组，然后一个大小为 $interval$ 的时间间隔。

求：在数组里面任取一个数 $x$ ，然后有一个集合 $\{x+ interval*k, k \ge 0\}$ 的集合，那么说明数组里面有 $y$ 个数在这个集合里面，求最大的 $y$ 对应的 $x$ ，如果两个 $x$ 值的 $y$ 相等，则求最小的 $x$

数据范围#

$1 \le n \le 10^5$
$0 \le x \le 10^9$
$0 \le interval \le 10^5$

题解#

思维#

时间复杂度 $O(nlogn)$

第一步预处理 $h$ 数组， $h[i]$ 表示数组里面的数对 $interval$ 取模后有多少个值为 $i$

第二步，有序离散化。因为对于重复值，只需要计算一次。同时使用哈希表记录下每个数出现了多少次

第三步，从小到大枚举有序离散化后的数组，那么对于当前值 $x$ ， $y$ 一定是等于 $h[x \% interval]$ 的数量。同时在最后 $h[x \% interval]$ 要更新，减去原数组里面 $x$ 的数量。因为 $h[i]$ 只是保证了取模后的值为 $i$ 的数量，但是对于一个 $x$ 而言，我们需要的不仅仅是取模要相等，而且要保证 $\ge x$

WARNING
因为这题 interval 可能为 0，因此需要特判

代码如下

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
#include <unordered_map>
5
#include <vector>
6

7
using namespace std;
8

9
const int N = 100010;
10

11
int q[N];
12
int n;
13
int delta;
14
int h[N];
15

16
unordered_map<int, int> um;
17
vector<int> alls;
18

19
int main() {
20

21
    // freopen("in.txt", "r", stdin);
22
    // freopen("out.txt", "w", stdout);
23
    scanf("%d", &n);
24
    for (int i = 0; i < n; i ++ ) {
25
        scanf("%d", &q[i]);
26
        alls.push_back(q[i]);
27
        um[q[i]] ++ ;
28
    }
29
    scanf("%d", &delta);
30

31
    sort(alls.begin(), alls.end());
32
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
33

34
    int m = alls.size();
35

36
    if (delta == 0) {
37
        int res = 0, cnt = 0;
38
        for (auto &u: alls)
39
            if (um[u] > cnt) {
40
                res = u, cnt = um[u];
41
            }
42
        printf("%d", res);
43
    } else {
44
        for (int i = 0; i < n; i ++ )
45
            h[q[i] % delta] ++ ;
46

47
        int res = -1, cnt = 0;
48
        for (int i = 0; i < m; i ++ ) {
49
            int t = alls[i] % delta;
50
            if (h[t] > cnt) {
51
                res = alls[i], cnt = h[t];
52
            }
53
            h[t] -= um[alls[i]];
54
        }
55
        printf("%d", res);
56
    }
57
    return 0;
58

59
}

第三题#

题目大意#

给你一个长度为 $n$ 的时间区间 $[left_i, right_i]$ ，表示会议从 $left_i$ 开始， $right_i$ 天结束。如果小明在其中一天参加会议，那么就算小明参加了这场会议，但是小明每天最多只能参加 $k$ 场会议。问：小明最多能参加多少场会议？

数据范围#

$1\le n \le 10^4$
$1 \le k \le 10$
$0 \le left_i \le right_i \le 10^8$

题解#

贪心#

时间复杂度 $O(n^2logn)$

贪心策略：按照 $left_i$ 从小达到，若 $left_i$ 则按照区间长度从小到大选择。如果发现 $left_i$ 这天已经被占满了，则更新区间为 $[left_i+1,right_i]$ 。

NOTE
证明：假设贪心解为集合 $S_1$ ，最优解为 $S_2$
则有 $|S_1| \le |S_2|$
另外，对于集合 $S_1$ 和 $S_2$ 中的每个区间，都有一个生效的天数，因此，分别对 $S_1$ 和 $S_2$ 按照生效天数排序，如果生效天数相等，则按照右端点从小到大排序。
经过排序后，贪心解存在有第一个和最优解不同的区间，如果 $vaild_i \lt vaild_j$ ，（其中 $valid_i,valid_j$ 分别为贪心解和最优解的有效值，也即是区间中第几天去参加的会议。）那么现在可以将当前区间加入到 $S_2$ 中。
如果 $valid_i = valid_j$ ，说明可以将贪心解的该区间把最优解的该区间给替换掉。
如果 $valid_i \gt valid_j$ ，这种情况与贪心策略相矛盾
综上，最优解能通过添加区间或者替换区间的方式变成最优解，说明 $|S_2| \le |S_1|$
因此， $|S_1|=|S_2|$

贪心证明如若有误，欢迎批评指正

这个贪心策略用优先队列维护即可。

代码如下

1
#include <iostream>
2
#include <cstring>
3
#include <queue>
4
#include <vector>
5
#include <unordered_map>
6

7
using namespace std;
8

9
const int N = 10010;
10

11

12
struct Node {
13
    int l, r, len;
14
    Node() {};
15
    Node(int a, int b, int c) {
16
        l = a, r = b, len = c;
17
    }
18
    bool operator < (const Node& a) const {
19
        if (a.l == l) return len > a.len;
20
        return l > a.l;
21
    }
22
};
23

24
priority_queue<Node> Q;
25
unordered_map<int, int> cnt;
26

27
int main() {
28

29
    // freopen("in.txt", "r", stdin);
30
    // freopen("out.txt", "w", stdout);
31
    int n, k; scanf("%d%d", &n, &k);
32
    for (int i = 0; i < n; i ++ ) {
33
        int l, r; scanf("%d%d", &l, &r);
34
        Q.push({l, r, r - l + 1});
35
    }
36

37
    int res = 0;
38
    while (Q.size()) {
39
        auto q = Q.top(); Q.pop();
40
     //   cout << q.l << ' ' << q.r << ' ' << q.len << endl;
41
        if (cnt[q.l] >= k) {
42
            if (q.l < q.r) Q.push({q.l + 1, q.r, q.len - 1});
43
            continue;
44
        }
45
        cnt[q.l] ++ ;
46
        res ++ ;
47
    }
48
    printf("%d", res);
49

50
}

TIP
如果 $n=10000$ , $k=1$ ,区间都是 $[1,1000000000]$ 那么，很明显这个时间复杂度就是 $O(n^2logn)$

写在最后，第三题有 $O(n^2)$ 或者以下做法欢迎讨论