一、总体情况
- 考试一共有五道题。
- 这次考试失误严重，C题非常水的一道题做了快两个小时，严重影响了心态和做其它题的时间。
- 最终3个小时只做了 A , C A,C A,C 两道题。
二、题解
A题 二叉树深度
题目描述
有一个 n ( n ≤ 1 0 6 ) n(n \le 10^{6}) n(n≤106) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 n n n)，建立一棵二叉树（根节点的编号为1），如果是叶子结点，则输入 0, 0。
建好这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。
思路分析
建好树之后跑一个dfs即可算出所有点的深度，取最大就是答案，每个点遍历一次，复杂度 O ( n ) O(n) O(n).
代码
#include <iostream>
#include <algorithm>
using namespace std;
struct Edge {
int to;
int next;
};
const int N = 1e6 + 6;
int n;
Edge edge[N];
int head[N];
int idx = 0;
int depth[N];
int ans = 0;
void add_edge(int from, int to)
{
edge[idx].to = to;
edge[idx].next = head[from];
head[from] = idx++;
}
void dfs(int u, int father)
{
depth[u] = depth[father] + 1;
ans = max(ans, depth[u]);
for (int i = head[u]; i != -1; i = edge[i].next)
dfs(edge[i].to, u);
}
int main()
{
ios::sync_with_stdio(false);
fill(head, head + N, -1);
cin >> n;
int l, r;
for (int i = 1; i <= n; i++) {
cin >> l >> r;
if (l != 0)
add_edge(i, l);
if (r != 0)
add_edge(i, r);
}
dfs(1, 0);
cout << ans << '\n';
return 0;
}
B题 智商
题目描述
Doremy被要求测试 n n n个比赛。比赛 i i i只能在第 i i i天测试。比赛 i i i的难度为 a i a_{i} ai。一开始，Doremy的智商为 q q q。在第 i i i天，Doremy将决定是否测试比赛 i i i。只有当她的当前智商严格大于0时，她才能测试比赛。如果Doremy选择在第 i i i天测试比赛 i i i，将发生以下情：
- 如果 a i > q a_i>q ai>q，Doremy会觉得自己不够聪明，所以 q q q 会减少 1 1 1；
- 否则，不会发生任何变化。
如果她选择不测试比赛，就不会发生任何变化。
Doremy希望尽可能测试更多的比赛。请给Doremy一个解决方案。
思路分析
这道题再选比赛的时候有两个显而易见的策略:
- 智商尽量越在后面的时候降越好，这样才有机会体验更多前面的比赛.
- 智商在最后一刻越接近于 0 0 0 越好。
由此可得，这道题可以用贪心思想，策略就是刚才那两个。并且，由于确定的是最后的智商，所以可以倒过来枚举智商。
智商从 0 0 0 开始，倒着枚举，如果又一场比赛的值大于智商，则智商 + 1 +1 +1，一直枚举到智商 = q = q =q
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int t;
int n, q;
int a[N];
int vis[N];
void init()
{
n = q = 0;
fill(a, a + N, 0);
fill(vis, vis + N, 0);
}
int main()
{
ios::sync_with_stdio(false);
cin >> t;
while (t-- > 0) {
init();
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
int tmp = 0;
int i = n;
for (i = n; i >= 1 && tmp < q; i--) {
if (a[i] > tmp)
tmp++;
vis[i] = true;
}
for (; i >= 1; i--)
if (a[i] <= q)
vis[i] = true;
for (int i = 1; i <= n; i++)
if (vis[i])
cout << 1;
else
cout << 0;
cout << '\n';
}
return 0;
}
C题 科学家看电影
题目描述
莫斯科正在举办一次重要的国际会议，来自不同国家的科学家参加了会议。每个科学家都只知道一种语言。为方便起见，我们用 1 1 1 到 1 0 9 10^9 109 的整数枚举世界上所有语言。
会议结束后的晚上，所有科学家都决定去电影院。他们来到的电影院里有 m m m 部电影。每部电影都有两个不同的语言——音频语言和字幕语言。来到电影旁的科学家，如果听得懂电影的音频，他会非常高兴，如果他看得懂字幕，他会很满意，如果他既听不懂音频也看不懂字母，他会非常生气（注意，每部电影的音频语言和字幕语言总是不同的）。
科学家们决定一起去看同一部电影。你必须帮助他们选择电影，这样非常高兴的科学家的数量是尽可能多的。如果有几部这样的电影，请从中选择一部能够最大限度地增加满意的科学家的数量。
思路分析
这道题其实非常简单，可以用map或者离散化将每种语言会的人数统计出来，再在电影里面以电影语言对应的人数从大到小排序。并且，音频语言的人数如果相等的话，再以字幕语言的人数排序。这样，排完序后，第一个电影就是答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
map<int, int> mp; //每种语言出现的次数
int n, m;
int a[N];
struct Node {
int a; //音频语言
int b; //字幕语言
int r_a; //听得懂音频语言的人数
int r_b; //看得懂字幕语言的人数
int idx; //电影编号
};
bool cmp(Node a, Node b)
{
//优先按音频排序
if (a.r_a != b.r_a)
return a.r_a > b.r_a;
return a.r_b > b.r_b;
}
Node f[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mp[a[i]]++;
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> f[i].a;
f[i].r_a = mp[f[i].a];
f[i].idx = i;
}
for (int i = 1; i <= m; i++) {
cin >> f[i].b;
f[i].r_b = mp[f[i].b];
}
sort(f + 1, f + m + 1, cmp);
cout << f[1].idx;
return 0;
}
D题 寻找段落
题目描述
给定一个长度为 n n n 的序列 a a a，定义 a i a_i ai 为第 i i i 个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在 [ S , T ] [S, T] [S,T] 之间的连续序列。最有价值段落是指平均值最大的段落。
段落的平均值 等于 段落总价值 除以 段落长度。
思路分析
这道题的答案是满足单调性的，若答案越大，则能产生这个答案的区间就越少；若答案越小，则区间就越多。所以，可以考虑二分答案。
二分答案的关键就在于check()函数，而这道题的check()显然就是要确认有没有区间的平均值 ≥ m i d d l e \ge middle ≥middle，换句话说，可以把每个元素都减去一个 m i d d l e middle middle，再用前缀和来算区间和，如果区间和 ≥ 0 \ge 0 ≥0，则返回true。而这个平均值可以用单调队列维护。
假设以一个下标 i i i 作为区间的右端点，则区间 [ i − s + 1 , i ] [i - s + 1, i] [i−s+1,i] 和区间 [ i − t + 1 , i ] [i - t + 1, i] [i−t+1,i] 是合法的。那么就可以用一个单调递增队列 q q q 来维护这些区间，单调队列中的队首是非常好弹出的，当 i − q i - q i−q 的队首 > t > t >t 的时候，那 q q q 的队首就要出队。
但比较难维护的是队尾。我们知道，区间 [ i − s + 1 , i ] [i - s + 1, i] [i−s+1,i] 的区间和 = s u m [ i ] − s u m [ i − s ] = sum[i] - sum[i - s] =sum[i]−sum[i−s]，而我们就要尽量让这个值 ≥ 0 \ge 0 ≥0。 队尾就要尽量小。当 q q q 不为空且 s u m [ q sum[q sum[q的队尾 ] > s u m [ i − s ] ]> sum[i - s] ]>sum[i−s]，就弹出队尾。
代码
#include <iostream>
#include <iomanip>
#include <queue>
#define N 100005
#define DELTA 1e-6
using namespace std;
int n;
int s, t;
int nums[N];
double sum[N];
bool check(double middle)
{
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + nums[i] - middle;
deque<int> q;
for (int i = 1; i <= n; i++)
if (i >= s) {
while (!q.empty() && sum[q.back()] - sum[i - s]> DELTA)
q.pop_back();
q.push_back(i - s);
while (i - q.front() > t)
q.pop_front();
if (sum[i] > sum[q.front()])
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> s >> t;
for (int i = 1; i <= n; i++)
cin >> nums[i];
double left = 0, right = 1e9;
double middle = (left + right) / 2;
while (right - left > DELTA) {
middle = (left + right) / 2;
if (check(middle))
left = middle;
else
right = middle;
}
cout << fixed << setprecision(3) << left << '\n';
return 0;
}
E题 恢复序列
题目描述
Peter 在白板上写下一个严格递增的正整数序列
a
1
,
a
2
,
.
.
.
,
a
n
a_{1}, a_{2}, ..., a_{n}
a1, a2, ..., an。然后，Vasil 将这个序列中的数的某些位替换成为问号。这样一来，每个问号恰好对应了一个丢失的位。
依据白板上剩余的已知位，恢复原始的序列。
思路分析
这道题其实就是一个超级烦的模拟题，带一点点的贪心。首先，输入时，要把每个数当作字符串输入。其次，我们知道，为了让下一个数有得填，那上一个数填的就要尽可能的少，这就是贪心策略
剩下的就是分类讨论了，假设当前的数为 n o w now now，上一个数为 l a s t last last，(如果第一个数有问号全部填 0 0 0，除非第一位有问号，那第一位就填 1 1 1，其它的问号填 0 0 0)
- 若 n o w now now 的位数 > > > l a s t last last 的位数，则 n o w now now 中的问号尽量都填 0 0 0 (除了第一位)；
- 若 n o w now now 的位数 < < < l a s t last last 的位数，则直接输出NO，结束程序；
- 若 n o w now now 的位数 = = = l a s t last last 的位数，则又要分好几种情况：这时候先把问号忽略，再比较 n o w now now 和 l a s t last last 的大小，再根据每种情况分类讨论即可。
代码
#include <iostream>
#include <string>
#include <vector>
#define now v[idx]
#define last v[idx - 1]
using namespace std;
const int N = 1e5 + 5;
string v[N];
bool solve(int idx)
{
bool res = true;
if (now.size() < last.size()) {
res = false;
return res;
} else if (now.size() > last.size()) {
if (now[0] == '?')
now[0] = '1';
for (int i = 1; i < now.size(); i++)
if (now[i] == '?')
now[i] = '0';
} else {
// now.size() == last.size()
string op = "";
int pos = 0;
for (int i = 0; i < now.size(); i++) {
if (now[i] == '?' || now[i] == last[i])
continue;
if (now[i] < last[i]) {
op = "now < last", pos = i;
break;
} else if (now[i] > last[i]) {
op = "now > last", pos = i;
break;
}
}
if (op == "")
op = "now == last";
if (op == "now < last") {
bool flag = false;
bool wrong = false;
for (int i = pos - 1; i >= 0; i--)
if (now[i] == '?') {
flag = true;
if (last[i] == '9') {
wrong = true;
continue;
} else {
now[i] = last[i] + 1;
wrong = false;
for (int j = i; j >= 0; j--)
if (now[j] == '?')
now[j] = last[j];
break;
}
}
if (!flag || wrong) {
res = false;
return res;
}
for (int i = now.size() - 1; i >= 0; i--)
if (now[i] == '?')
now[i] = '0';
} else if (op == "now > last") {
for (int i = 0; i <= pos; i++)
if (now[i] == '?')
now[i] = last[i];
for (int i = pos + 1; i < now.size(); i++)
if (now[i] == '?')
now[i] = '0';
} else if (op == "now == last") {
bool flag = false;
bool wrong = false;
for (int i = now.size() - 1; i >= 0; i--)
if (now[i] == '?') {
flag = true;
if (last[i] == '9') {
now[i] = '0';
wrong = true;
continue;
} else {
now[i] = last[i] + 1;
wrong = false;
for (int j = i; j >= 0; j--)
if (now[j] == '?')
now[j] = last[j];
break;
}
}
if (!flag || wrong) {
res = false;
return res;
}
}
}
if (now.size() == last.size() && now <= last) {
res = false;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> v[i];
solve(1);
for (int i = 2; i <= n; i++)
if (!solve(i)) {
cout << "NO\n";
return 0;
}
cout << "YES\n";
for (int i = 1; i <= n; i++)
cout << v[i] << '\n';
return 0;
}
三、存在的不足
- 这次考试在心态方面吃了很大的亏，在做玩 A A A 题之后，我一直再想 B B B 题，有点思路，但还在想，这时我看到有人已经把 C C C 题做出来了。此时，我已经开始慌了，我也去看向了 C C C 题。但是，当时我把 C C C 题想得太复杂了，原本统计完之后再排个序就能解决的问题，我在那里写了3个map。写了半天没写出来后，我发现大部分人都已经把 C C C 题做出来了，我这个时候已经慌到离谱，~~写了个set<int, int> st;都还没发现哪里写错了。~~后来，我慢了下来，在还有50分钟结束考试的时候，突然想到了这个做法，写完代码再交上去一共就用了10分钟不到……
- 并且，这次考试中，我就是因为把问题想得太复杂了，导致丢失了大量时间，就和这回的 E E E 题一样， E E E 题我在考试时肯定没时间再做了，但当考完后我补题的时候，也是想复杂了，写了一大堆bool变量和一堆if…else…，也是想复杂了，还把自己绕晕了。后来，我又重新理了一下思路，重新写了一遍代码，很快就把这道题 A A A了。
四、下次考试时的改进措施
- 考试时能不看排名就不看排名，这玩意是真的影响心态……
- 做题前先把思路彻底理清楚再开写
- 考试时如果有题实在不会做，但时间充裕，可以先打个暴力交上去，说不定就过了。(这次的 D D D 题暴力都能过)；
- 对于简单问题，多想想有什么算法和这个问题很像，不要盲目开写，更不要想复杂了。