North American Invitational Programming Contest 2018 (NAIPC 2018)

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Upsolved by Xiejiadong.(-5)

题意:给出$n$盏灯的初始状态,每次按开关,从按的位置开始,每一时刻都会有后面一个灯转换状态,求变成目标状态最小需要的次数。

题解:$n\le 16$考虑状态压缩。

其实,抽象一下这道题目,可以看作是好多段长度不同的$1$异或起来,以达到目标状态。

用$f[i][j]$表示已经按了$i$次,状态为$j$时候存在,直接暴力枚举转移即可。时间复杂度$O(2^n\times n^2)$

没有看到状态处理的时候溢出了,怎么都过不了。

Problem D

Solved by Xiejiadong. 00:11:06(+)

非常温暖的签到题。

Problem E

一开始这道题目在用hash搞,怎么都过不去。

赛后算是过去了,就是不同长度的字符串hash的时候,应该把字符串的长度也作为其中一个key。

Solved by Xiejiadong. 02:44:14(+4)

题意:给出$n$个串,选取其中的$m$组合,将所有的组合按照字典序排序,求目标串的排名。

题解:用Trie树为辅助,将目标串分割。由于保证了所有给出的字符串之间不会互为前缀,所以分割一定唯一。

然后计算方式就是类似于求排列是第几个,将所有小于目标串的个数处理出来,可以用树状数组来维护当前已经处理的数。

时间复杂度$O(nlog_2n)$。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Solved by Xiejiadong. 02:23:59(+)

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by Xiejiadong. 04:58:11(+3)