F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 5331 >> 第二问也可以用莫队
save_code @ 2018-06-14 09:33:06
[ Quote ] [ Edit ] [ Delete ] 1#
不过维护参数很麻烦
第二问的 答案 等于 总数 减去 枚举 每个颜色, 这条链上所有不包含 这个颜色的和

我们可以 dp[id]记录 id 到根节点 不满足条件的答案 (也就是 相同两个颜色 之间距离减 1的组合数和)

A,B 这条链的 反面结果 就等于 dp[lca]+ 每种 颜色 三个关键点的 情况 比如 a,b,c 就是(dist[b]-dist[a]-1)*(dist[c]-dist[a]-1)

a表示 改颜色 在 A到lca之间 离lca最近的 点,b表示 该颜色在 B到lca之间 离lca最近的点,c表示 lca到根节点 之间离 lca最近的点,
然后 莫队算法维护这三个点 以及 一系列(一坨)参数

反正 目测应该是可以实现的,只不过 很麻烦,很纠结。。

复杂度n*sqrtn
save_code @ 2018-06-14 09:35:15
[ Quote ] [ Edit ] [ Delete ] 2#
统计 总数貌似也是一件麻烦的事情 啊
save_code @ 2018-06-14 09:46:00
[ Quote ] [ Edit ] [ Delete ] 3#
还有主要麻烦点 在于 A到LCA 之间 不存在 某种颜色和B到LCA之间 不存在某种颜色,要维护一个 二元二次多项式, x,y 分别对应查询的 dist[a] 和dist[b]
nzhtl1477 @ 2018-06-14 16:16:43
[ Quote ] [ Edit ] [ Delete ] 4#
是可以吧
save_code @ 2018-06-14 16:17:19
[ Quote ] [ Edit ] [ Delete ] 5#
我觉得 用我的对颜色分块 实现起来 更简单一些啊 虽然多个根号log
save_code @ 2018-06-17 03:51:25
[ Quote ] [ Edit ] [ Delete ] 6#
600多行终于过了啊。。。。
数据都没有 颜色个数>=sqrt(n)的情况 直接用算法2就能AC...
nzhtl1477 @ 2018-06-17 14:27:20
[ Quote ] [ Edit ] [ Delete ] 7#
orz 600行
save_code @ 2018-06-17 14:59:34
[ Quote ] [ Edit ] [ Delete ] 8#
很显然 status 有 3000+K的, 明显我做复杂了啊
nzhtl1477 @ 2018-06-17 17:07:52
[ Quote ] [ Edit ] [ Delete ] 9#
肯定
(话说您的代码一直都很长耶)
save_code @ 2018-06-17 17:09:52
[ Quote ] [ Edit ] [ Delete ] 10#
最长的貌似是 uoj 90 26K+
save_code @ 2018-06-17 17:10:27
[ Quote ] [ Edit ] [ Delete ] 11#
那道题 论文的方法没有见过啊。。。。自己自创解法
nzhtl1477 @ 2018-06-18 14:04:10
[ Quote ] [ Edit ] [ Delete ] 12#
orz
Claris @ 2018-06-18 15:09:43
[ Quote ] [ Edit ] [ Delete ] 13#
标算是利用数据随机性O(nlogn)做的。
iloi @ 2018-06-19 08:02:46
[ Quote ] [ Edit ] [ Delete ] 14#
orz
[Top] [Previous Page] [Next Page]

HOME Back