日企面试题

cai_lw 发表于 2022-5-6 07:51
AtCoder（日本的编程竞赛网站）不太久之前出过几乎一模一样的题
ABC238-E https://atcoder.jp/contests/abc ...

看了看感觉还是不一样…………

davidwei3310273 发表于 2022-05-05 18:26:32
看了看感觉还是不一样…………

这题的最本质和最难的一步是把“a[i]+a[i+1]+...+a[j-1]可以唯一确定”转化成“顶点i和顶点j连通”，在这点上这两题是一样的

（之前想了一个解释但是不对，删掉了）

cai_lw 发表于 2022-05-05 19:19:52
这题的最本质和最难的一步是把“a+a+...+a可以唯一确定”转化成“顶点i和顶点j连通”，在这点上这两题是一样的

接下来又怎么得到index呢？Iterate一遍所有单独的index又把复杂度变成n^2了

先排序再用类似找线段overlap的方法找出所有l+1 ==r的overlap.

补充内容 (2022-05-06 18:14 +08:00):
感觉可以用sweep line 来做

clark.li86 发表于 2022-5-6 18:07
先排序再用类似找线段overlap的方法找出所有l+1 ==r的overlap.

补充内容 (2022-05-06 18:14 +08:00):

那对[[1, 2], [2,3], [3,4]]这个query list可以得出结果为空的结论吗？

davidwei3310273 发表于 2022-5-6 08:08
那对[[1, 2], [2,3], [3,4]]这个query list可以得出结果为空的结论吗？

这个按照解答算出来当然是空，精髓是前闭后开

并查集, 将值转化为边, 例如index=1的值, 转化为点1到点2的边的权值, 那么本质上就是求点i到i+1是否连通