Difference between revisions of "2018 ECNU AK ICPC/CCPC Typing Speed Contest"

From EOJ Wiki
Jump to navigation Jump to search
Line 30: Line 30:
 
=== Problem H ===
 
=== Problem H ===
  
Solved by oxx1108. 02:02:32(+5)
+
Unsolved.
 
 
题意:给两个石头剪刀布的序列,求最好的匹配位置使得你赢的次数尽量多。
 
 
 
题解:分三种匹配情况跑三次 FFT(等于字符串匹配,校赛原题),然后求和最大,bitset被卡了。
 
  
 
=== Problem I ===
 
=== Problem I ===

Revision as of 10:31, 5 October 2018

One,Two,Three,AK

Problem A

Solved by dreamcloud. 01:26:50(+1)

Problem B

Solved by oxx1108. 03:46:24(+7)

Problem C

Unsolved.

Problem D

Solved by oxx1108. 00:45:57(+)

Problem E

Solved by Xiejiadong. 03:52:04(+2)

Problem F

Solved by oxx1108. 00:33:40(+2)

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Upsolved by Xiejiadong.(-6)

题意:给出一个字符串,去掉某一部分前缀以后,一定是一个循环字符串。

题解:kmp的next数组的应用。

反串构造next数组,那么对于反串的前$i$为,他的最小循环节长度一定是$i-next[i]$,这个就是$p$,那么$k=n-i+1$,这里直接美枚举所有$k$和$p$去$k+p$的最小值即可。

还要注意$k=0$的情况,所以枚举的时候要向后多找一位。

Problem J

Unsolved.

Problem K

Solved by Xiejiadong. 03:31:05(+1)

题意:给定平面上折线的行进方向和距离,要求修改距离使得不自相交。

题解:水平的和垂直的分开考虑,水平的如果和上一次的方向相同,走一步,否则走$i$步,可以有效避免冲突。垂直的处理方式类似。

Problem L

Unsolved.