SP14932 LCA-Lowest Common Ancestor 超水题解

OI生涯中的第一篇题解 (迫真)

复习LCA的时候去查了查有什么题, 就发现了这道模板题.

因为我太菜, 不会写树上倍增, 就想有什么别的方法能过.

刚好发现一种朴素解法:

  • 先从 x 往上走到根,沿途会经过 x 所有的祖先,把它们用一个数组标记。
  • 再从 y 往上走到根,沿途会经过 y 所有的祖先,遇到的第一个被标记的点就是 x,y 的最近公共祖先。

看了一眼数据范围, N <= 1000. 这么水 (虽然有多组数据), 果断开搞.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstring>
using namespace std;
int fa[1005], vis[1005];
int LCA(int x, int y){
memset(vis, 0, sizeof(vis));
while(x!=0){
vis[x]=1;
x=fa[x];
}
while(vis[y]==0){
y=fa[y];
}
return y;
}
int main(){
int T, cnt = 0;
cin >> T;
while(T--){
cnt++;
cout << "Case " << cnt << ":" << endl;
int n;
cin >> n;
for(int i = 1; i <= n; i++){
int m;
cin >> m;
for(int j = 1; j <= m; j++){
int tmp;
cin >> tmp;
fa[tmp] = i;
}
}
int Q;
cin >> Q;
while(Q--){
int a, b;
cin >> a >> b;
cout << LCA(a, b) << endl;
}
}
return 0;
}

没想到竟然AC了……

虽然正解树上倍增肯定要学习一个, 但这也不失为一种骗分暴力可行的技巧 (如果真的忘了怎么写).

#EOF.

YouTube China 的好时代, 来临了 (迫真)

最近通过这个知乎问题了解到了 bilibili 手机客户端更新后启动图的 2233 被换下的事儿. 看来*睿是铁了心想去ACG化了… 呐, 你[数据删除]什么时候[数据删除]啊

所以说现在的 bilibili 已经可以算是 YouTube China 了嘛.

有感而发就摸了两张图. 原谅我Ps水平低下

P2 主要是不知道怎么处理那个艺术字体了. “油管”两字所用字体为 ITXE Writing.

YouTube Logo 后面跟的后缀以及 P1 下面那个 Copyright 用的字体是 Google Sans. 我承认我是故意加了个后缀的, 我又不是不知道这有违YouTube视觉规范

源知乎回答在这里. 工程文件? 做完就删了 (逃

唔.

[老作品] '[计蒜客] Liquid (Paul Rosenthal Remix)'

去年暑假上qbxt的夏令营的时候, 我在某个晚上第一次尝试做音mad. 因为我不会用 Fl Studio, 就用欠费调音师专用的 Audition 加上计蒜客的音源搞了一首出来.

在申请Let's Encrypt证书时可能会遇到的坑

最近尝试给我的博客申请一个Let’s Encrypt证书, 结果发现跟网上的各种教程有点不同, 不是简单的clone一个repo那么简单 — 坑真的很多.

CSP-S 2019 崩溃记

作为入OI坑一年多的蒟蒻, 得知NOIp已死的消息后, 我去参加了这次的CSP-S 第一届全国中学生树学竞赛.

然鹅, 考完之后心态彻底炸了.

浅谈Android模拟器/虚拟机/各种Android-x86发行版

最近心血来潮想折腾折腾Android虚拟机(当然这也包括模拟器).

所以我就去把一些Android模拟器/Android-x86发行版都去装(yong)了个遍.

小评 Logitech K380

(最近发懒, 两个月没更新了, 抱歉.)
3个月前入了一台 Logitech K380 (因为自己rmbp的键盘又双叒叕坏了orz), 来说说使用心得吧…

请不要信口开河

前几天看《作文素材》。 本来感觉很好看, 直到看到这儿, 我一下子气炸了。

开学了...

这个寒假除了去hz上qbxt的冬令营之外几乎就是宅在家里拼命写数学题了. 年也没怎么过(除夕夜我还在肝作业).

啊, 感觉寒假过得真快.

不说了, 希望这个学期能有个好开头吧…

Andy Chen 的杭州地铁小记

搬运自我的知乎文章: https://zhuanlan.zhihu.com/p/56258223

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×