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

From EOJ Wiki
Jump to navigation Jump to search
Line 27: Line 27:
  
 
此处省略一万字。
 
此处省略一万字。
 +
 +
== Problem C ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意:有一条折线,两端有两个人,A 要走到 B,B 要走到 A,他们的高度需要始终保持一致。求最小路程和。
 +
 +
题解:三维状态 (i,j,h) 表示 A 在第 i 条折线上,B 在第 j 条折线上,它们的一致高度是 �h 的最小路程。然后跑 Dijkstra 即可。
 +
 +
此题是出题人眼中的签到题。但事实上现场过了没几个队,而且实现起来可能较为繁琐。有几个需要注意的地方(可能会好写一点):
 +
 +
* 每段折线都看成是左闭右开的。没有右端点。最后一条折线只有左端点。
 +
* 搜下一状态时,可以把某一个人看成是主动方,另一个人看成是被动方。主动方先动,动完了以后被动方要去它所在的位置左右看,有没有合适的地方能走过去。对于每个能走的位置都是合法的后继状态。
 +
* 主动方不能不动,被动方可以不动。
 +
* 每一步只在一条线段上走,不要因为是平的之类的情况而一步多动。
 +
* 注意折线某一段是平的情况。在这种情况下「第 i 条折线上高度为 h 的位置」可以更精确地定义为:第 i 条折线上第一次出现高度 h 的位置。转移过状态时候,可能会需要对状态进行校正。
  
 
== Problem F ==
 
== Problem F ==

Revision as of 06:13, 2 December 2018

Replay

zerol: 来了

ultmaster:

  • 只做了半道题是怎么回事啊?
  • 赛后发现傻逼题还不如不要发现呢。难受 QAQ~
  • WF 顺位 3,岌岌可危。(然而已经没救了
  • 食堂又远又不好吃。
  • 出租车坑。
  • 要不是这个比赛我有可能永远都不会听说矿大这个学校。
  • 回想了一下这好像是第二次有教练跟来的比赛。上一次是 16 年北京。

kblack:

  • 高铁定晚了,导致来回的时间都很蛋疼,酒店虽然贵了点,但是房间大小好评。
  • 刘爷爷好强啊。
  • 成就:罚时担当——贡献全部六发罚时。
  • 嗦不粗发,相距 364 个行星日整,上次被卡金,这次怕是要被卡 Final,而且全是因为罚时,还都是我干的。
  • 没什么能多说了,自闭去了。
  • 血拼 EC 2018?

Problem A

Solved by kblack. 00:50 (+3)

此处省略一万字。

Problem C

Upsolved by ultmaster.

题意:有一条折线,两端有两个人,A 要走到 B,B 要走到 A,他们的高度需要始终保持一致。求最小路程和。

题解:三维状态 (i,j,h) 表示 A 在第 i 条折线上,B 在第 j 条折线上,它们的一致高度是 �h 的最小路程。然后跑 Dijkstra 即可。

此题是出题人眼中的签到题。但事实上现场过了没几个队,而且实现起来可能较为繁琐。有几个需要注意的地方(可能会好写一点):

  • 每段折线都看成是左闭右开的。没有右端点。最后一条折线只有左端点。
  • 搜下一状态时,可以把某一个人看成是主动方,另一个人看成是被动方。主动方先动,动完了以后被动方要去它所在的位置左右看,有没有合适的地方能走过去。对于每个能走的位置都是合法的后继状态。
  • 主动方不能不动,被动方可以不动。
  • 每一步只在一条线段上走,不要因为是平的之类的情况而一步多动。
  • 注意折线某一段是平的情况。在这种情况下「第 i 条折线上高度为 h 的位置」可以更精确地定义为:第 i 条折线上第一次出现高度 h 的位置。转移过状态时候,可能会需要对状态进行校正。

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 (+)

题意:从给定的若干条路径中选取 k 条,使得路径交至少为 1 个点。

题解:枚举路径交的 LCA,设为 u。设有 s 条路径经过了 u,有 c 条路径的 LCA 恰好是 u,那么这个点上的计数是 $\binom{s}{k} - \binom{c}{k}$。LCA + 差分前缀和 + 预处理组合数就好了。

Problem H

Solved by kblack. 03:05 (+2)

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

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

Problem M

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

题意:$n$ 个点的凸包,在 $m$ 个点中选最小个数个,使得凸包能被照亮。

题解:求出每个灯能照亮的区间,然后就是求最小个区间能覆盖整个凸包。据说是个经典问题。数据范围很小,暴力就行。

计算几何签到,乱换上机间不仅丢了一血,还 WA 了一发。