Difference between revisions of "2018 ACM-ICPC Xuzhou Regional Onsite"

From EOJ Wiki
Jump to navigation Jump to search
Line 10: Line 10:
  
 
Unsolved. (-11)
 
Unsolved. (-11)
 
T 飞了。
 
  
 
题意:求一个字符串 S 中的非空子串 T 的数量,满足不存在 TP 是 S 的子串且 TP 和 PT 完全一致。
 
题意:求一个字符串 S 中的非空子串 T 的数量,满足不存在 TP 是 S 的子串且 TP 和 PT 完全一致。
  
题解(伪):如果 P 的长度小于 T,那么 P 的最小循环节是 T 的循环节,否则 T 是 P 的循环节。后缀树上启发式合并得到出现位置集同时维护相邻两个位置的差 d。一个长度为 $l$ 的子串不计当且仅当 $d \le \frac l2$ 或 $l=d$
+
题解(伪):如果 P 的长度小于 T,那么 P 的最小循环节是 T 的循环节,否则 T 是 P 的循环节。后缀树上启发式合并得到出现位置集同时维护相邻两个位置的差 d。一个长度为 $l$ 的子串不计当且仅当 $d \le \frac l2$ 或 $l=d$,用 pb_ds 和 set 随便维护一下就能 T 到生活不能自理了。
  
 
== Problem G ==
 
== Problem G ==

Revision as of 07:45, 28 October 2018

Replay

Problem A

Solved by kblack. 00:50 (+3)

此处省略一万字。

Problem F

Unsolved. (-11)

题意:求一个字符串 S 中的非空子串 T 的数量,满足不存在 TP 是 S 的子串且 TP 和 PT 完全一致。

题解(伪):如果 P 的长度小于 T,那么 P 的最小循环节是 T 的循环节,否则 T 是 P 的循环节。后缀树上启发式合并得到出现位置集同时维护相邻两个位置的差 d。一个长度为 $l$ 的子串不计当且仅当 $d \le \frac l2$ 或 $l=d$,用 pb_ds 和 set 随便维护一下就能 T 到生活不能自理了。

Problem G

Solved by zerol. 01:14 (+)

Problem H

Solved by kblack. 03:05 (+2)

题意:$n$ 个区间,$k$ 染色使得有 $k$ 种颜色的区间最长。

题解:扫描线,贪心,set 里扔缺的颜色和可用线段,每当颜色不够 $k$ 的时候才延迟区间染色。

Problem M

Solved by kblack & ultmaster. 02:17 (+1)