最近一段时间在备赛第十五届蓝桥杯，自从去年参加十四届蓝桥杯后，心中有些许遗憾，看着其他同学随便拿省二省三，我却没有任何收获，所以想再参加一次。当然，之前没有获奖很大一部分原因是自己根本没有怎么准备，算法也只是刚刚入门而已。
今天回顾了去年蓝桥杯的一道题，没想到费了九牛二虎之力才拿到60%的分数，而且只是第4题，A组的题果然是不简单。去年参加考前模拟赛时觉得蓝桥杯不是很难，结果真实难度却远高于模拟难度，现在想想模拟赛应该是所有参赛选手统一的测试，不分组别，所以很可能是C组难度，不知道今年模拟赛难度如何。
题目如下：
想到去年比赛做这个题的时候，连树的数据结构都不会写，只能无奈放弃，上学期开始跟了y总的算法课，学会了很多数据结构的写法，现在做这个题已经有一定能力，思考步骤如下：
使用邻接表构建树的结构，根据题目信息，存储每个结点的下标和颜色。dfs遍历每个结点，判断每个结点作为根节点的子树是否为平衡树。
对于第二步，邻接表的遍历复杂度是O(n + m)，n为结点个数，m为边数，这道题m和n近似，暂且记为O(n)，而题目给的问题规模为2e5左右，明显需要在O(nlogn)以内完成，所以对每个结点子树的判断需要在O(logn)复杂度以内完成。
长时间没有思路后，只能考虑使用暴力方法，记录结点各个子树的不同颜色个数情况，然后将这些记录合并，再加上该结点的颜色信息，再判断以该节点为根节点的子树颜色情况，可以在O(n)复杂度完成，所以估计只能过掉60%样例。由于需要在每个结点处记录颜色信息，每个结点开一个颜色数量数组cnt[N]记录的话占用空间太大，考虑使用hash表，STL中的unordered_map存储。
代码如下：
#include
#include
#include
#include
using namespace std;
const int N = 2e5 + 10;
int h[N], e[N], ne[N], idx, color[N];
bool st[N];
int n;
int ans;
void add(int a, int b, int c) {
e[idx] = b;
color[b] = c;
ne[idx] = h[a];
h[a] = idx++;
}
unordered_map
st[u] = true;
unordered_map
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
unordered_map
// 合并
for (auto num : ct)
cnt[num.first] += num.second;
}
}
// 记录颜色
cnt[color[u]]++;
int base = 0;
for (auto it : cnt) {
if (base == 0)
base = it.second;
else {
if (base != it.second) return cnt;
}
}
ans++;
return cnt;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(h, -1, sizeof h);
cin >> n;
int C, F;
for (int i = 1; i <= n; i ++ ) {
cin >> C >> F;
add(F, i, C);
}
dfs(1);
cout << ans;
return 0;
}
小感悟：
做完以后了解了满分解法，需要使用启发式合并思想来做，但是有一定难度，对于目前来说学习的性价比不高。下个月蓝桥杯省赛，不要死磕地想要过掉所有样例，拿40%~60%分数即可，算算也有七八十分，应该能接近省一。学了一段时间的算法，感觉有很多遗憾，遗憾自己为什么没有早点接触良好的算法学习资源（y总yyds），提前学习算法知识，如今已是大三老狗。不过也无所谓了，想想现在的能力比去年强了很多，学到了许多算法知识，体会到算法AC的乐趣，这样来说也算没有太多遗憾。希望今年蓝桥杯能取得好成绩吧，至少拿个奖就好，继续加油。
相关阅读
您阅读本篇文章共花了：
发表评论