North American Invitational Programming Contest 2018 (NAIPC 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

一开始这道题目在用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(+)

题意：给出行和列的$1$个数的奇偶性，构造一个符合要求的$0/1$矩阵，在$1$数量最多的情况下，使得行的字典序最小。

题解：我么首先将整个矩阵用$1$填充。

主要的构造方法就是，除第一行外，所有不符合要求的行允许在一个不符合要求的列上修改。

然后剩下不符合要求的列数应该和第一行所需要的符合，否则无解。

然后贪心的从第一行开始修改，如果不够，继续在第二行修改。

不过需要注意，可能出现修改不到第一行，列就满足了，但行仍然没有满足的情况，需要处理一下：方法是，从第一列开始贪心的改（因为这样能保证字典序最小）。

Problem I

Upsolved by oxx1108.

题意：给一棵树，以及一些红点，求取若干结点不存在祖先关系且恰好有$k$个红点的方案数。

题解：树形dp加个剪枝。

Problem J

Unsolved.

Problem K

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

题意：给出一些点，每次询问一个区间的点，允许删除其中的一个点，求覆盖所有点所需要的最小正方形边长（正方形边必须与坐标轴平行）。

题解：显然，如果没有删除操作，答案就是行的最大差值*列的最大差值。

那么允许删除一个，我们就还需要维护八个信息：行的区间最大值，行的区间最小值，行的区间次大值，行的区间次小值，列的区间最大值，列的区间最小值，列的区间次大值，列的区间次小值。

直接用主席树维护一下就好了。不过要注意可能两个极值取属于同一个点坐标，这个需要用map来支持特判。