【70分调不出来的可以进来看看】告诫后人

P4130 [NOI2007] 项链工厂

ducati @ 2022-02-26 16:15:57

这题我调了整整七个小时，为了避免后来人犯同样的错误，本蒟蒻打算发一个帖子来告诫后人。

请注意，在 C 的查询中，如果你的计算方案是：

  • 断环为链，在序列上求出不同位置的数量 cnt，那么段数就是 cnt+1。特别的，若项链的首尾（断环为链是断开来的两个相邻位置）颜色相同，那么段数就是 cnt 而非 cnt+1。

我就是这么认为的，但是它是错的。

为什么呢？考虑一个各个珠宝颜色都相同的项链，用这种方法算出来的答案是 cnt=0，而答案却是 1。

解决方案比较显然，就是将 C 查询的答案对 1 取 \max。

by ducati @ 2022-02-26 16:17:20

说个笑话，我写了个暴力出来打算对拍，但暴力交上去除了 TLE 竟然还有 WA——原因就是我在暴力里面也套用了我的错误想法（只是把线段树换成序列暴力操作了而已），导致我没对拍起来只能瞪眼查看 /kel

by Ephemeroptera @ 2022-02-26 16:49:54

感谢

by shuihua @ 2022-02-26 21:52:14

感谢大佬的告诫，十分有用

by LordLaffey @ 2022-05-03 22:28:24

@ducati 感谢大佬提醒

|