【水】做题家每天做题碎碎念

搬砖
1

因为被陆老师嫌弃了，开个水贴每次做题的时候抱怨一下自己有多弱智

为什么要做题：

规则：
为了不浪费生命，除了DP以外的题瞪眼5分钟找不到最优解思路直接写暴力+看题解
由于leetcode数据弱，能用暴力解决的不浪费太多生命写优化算法
心里没底或者懒了用python，否则用c++

感觉自己太笨了，怎么办

广告：

\color{red}征友，\color{blue}希望可以婚绿\color{orange}130
\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

\Large\color{purple}富\color{olIve}婆\color{blue}大姐姐\color{red}请\color{violet}大力\color{green}送\color{lime}我\color{black}黑神话\color{orange}DLC

广告2：

每天睡觉前，他都要默诵“知足常乐，老天厚爱，你已功成名就，睡觉”；早晨醒来，再激励自己继续“奋斗”，默诵“不知足常进取，功名就在前边，努力前行”。

10 个赞
2

支持 一起刷题 一起进步

3

今天是一道签到题级别的分治，我却需要看一眼（非官方）题解才能想出平均nlogn思路
我已经彻底是个傻逼了 :cry:

https://leetcode.com/problems/number-of-good-leaf-nodes-pairs

（题解显然不是分治）

4

先拉黑魔芋大师 :troll:

5

amex什么鬼

3 个赞
6

为什么要抛弃 cf 刷 lc……
刷 kattis 也比刷 lc 快乐啊……

4 个赞
7

这个题有点难啊，如果path定义为必须经过root还好一些，现在不经过root来计算path，每对nodes都要找到common parent才行，这样复杂度立刻就上去了。还没想到一个好解法。

8

要努力找工作而且cf时间实在太阴间，准备去打洛谷的比赛

不好的回忆，悲

从父节点找左右子树的叶子节点配对

9

我没想清楚每个节点代表什么，感觉上可以存当前节点下面的leaf和distance，但没想清楚如何汇总，以及如何去重 :doge:

明天再看看吧

10

插眼zszs

11

https://www.luogu.com.cn/problem/B3785

T1: b-c<0 显然会向下而不是向上取整，随便找一个符合条件的输入，秒了
T2: 题干说

需要注意的是，刷新缓冲区是一件速度很慢的事情，如果刷新次数太多，会导致程序超时。

直接输出1e5个std::cerr造tle，秒了

program nitan(output);

var i : integer;
var t: integer;

begin
    readln(t);
    if t=1 then writeln('69 4 20')
    else begin
        writeln('19999');
        for i := 1 to 19999 do writeln('std::cerr');
    end;
end.

今天做了两道题了，明天的题如果难的话就摸鱼

12

太自律了，谭友个个身怀绝技还不断进步 :cry:

13

看了一眼

10秒钟后，尼玛这是medium，怎么感觉是hard呢……

14

因为转化成朴素的图然后从每个叶子节点BFS这种暴力到不敢想的算法是题解1，而且可以过全部样例AC

15

这玩意儿一眼直觉上去就是DP

DP = Hard

Q.E.D.

17

:clown_face:再次尝到了不读题的后果

18

脑仁疼 lz你施法了吗

19

想了一会儿

貌似这样就可以了：

  1. 后续遍历
  2. 对每个节点生成2个数组，分别对应当前节点的左子树和右子树，数组记录【距离当前节点距离为n的子树叶片数】n为数组index
  3. 遍历完一个节点后可以清除其所有子节点的数组，所以空间是log(n)

又想了一下我这么搞空间不是log(n)，因为遍历右树时候左子节点的数组是保留在那里的。所以一直遍历到右树最右叶片的时候整个枝上每一层都留着左子节点的信息。加起来应该还是O(n)

所以最后还是时间空间都O(n)

21

我写的空间O(n)的算法，我是sb

22

遍历右树的时候左树应该已经遍历完了，留下的个数组最大长度O(logn)？