Difference between revisions of "North American Invitational Programming Contest 2018 (NAIPC 2018)"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (Created page with "== Problem A == Unsolved. == Problem B == Unsolved. == Problem C == Upsolved by Xiejiadong.(-5) == Problem D == Solved by Xiejiadong. 00:11:06(+) == Problem E == Solv...") |
Xiejiadong (talk | contribs) |
||
Line 10: | Line 10: | ||
Upsolved by Xiejiadong.(-5) | Upsolved by Xiejiadong.(-5) | ||
+ | |||
+ | 题意:给出$n$盏灯的初始状态,每次按开关,从按的位置开始,每一时刻都会有后面一个灯转换状态,求变成目标状态最小需要的次数。 | ||
+ | |||
+ | 题解:$n\le 16$考虑状态压缩。 | ||
+ | |||
+ | 其实,抽象一下这道题目,可以看作是好多段长度不同的$1$异或起来,以达到目标状态。 | ||
+ | |||
+ | 用$f[i][j]$表示已经按了$i$次,状态为$j$时候存在,直接暴力枚举转移即可。时间复杂度$O(2^n\times n^2)$ | ||
+ | |||
+ | 没有看到状态处理的时候溢出了,怎么都过不了。 | ||
== Problem D == | == Problem D == |
Revision as of 08:10, 1 October 2018
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
Solved by Xiejiadong. 02:44:14(+4)
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)