Difference between revisions of "North American Invitational Programming Contest 2018 (NAIPC 2018)"
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...") |
|||
(7 intermediate revisions by one other user not shown) | |||
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 == | ||
Solved by Xiejiadong. 00:11:06(+) | Solved by Xiejiadong. 00:11:06(+) | ||
+ | |||
+ | 题意:给出一个排列的子序列,求满足要求的最小字典序的原序列。 | ||
+ | |||
+ | 题解:在每一个已经确定的数字前,贪心的放没有出现过的、小于它的数即可。 | ||
== Problem E == | == Problem E == | ||
+ | |||
+ | 一开始这道题目在用hash搞,怎么都过不去。 | ||
+ | |||
+ | 赛后算是过去了,就是不同长度的字符串hash的时候,应该把字符串的长度也作为其中一个key。 | ||
Solved by Xiejiadong. 02:44:14(+4) | Solved by Xiejiadong. 02:44:14(+4) | ||
+ | |||
+ | 题意:给出$n$个串,选取其中的$m$组合,将所有的组合按照字典序排序,求目标串的排名。 | ||
+ | |||
+ | 题解:用Trie树为辅助,将目标串分割。由于保证了所有给出的字符串之间不会互为前缀,所以分割一定唯一。 | ||
+ | |||
+ | 然后计算方式就是类似于求排列是第几个,将所有小于目标串的个数处理出来,可以用树状数组来维护当前已经处理的数。 | ||
+ | |||
+ | 时间复杂度$O(nlog_2n)$。 | ||
== Problem F == | == Problem F == | ||
Line 30: | Line 56: | ||
Solved by Xiejiadong. 02:23:59(+) | Solved by Xiejiadong. 02:23:59(+) | ||
+ | |||
+ | 题意:给出行和列的$1$个数的奇偶性,构造一个符合要求的$0/1$矩阵,在$1$数量最多的情况下,使得行的字典序最小。 | ||
+ | |||
+ | 题解:我么首先将整个矩阵用$1$填充。 | ||
+ | |||
+ | 主要的构造方法就是,除第一行外,所有不符合要求的行允许在一个不符合要求的列上修改。 | ||
+ | |||
+ | 然后剩下不符合要求的列数应该和第一行所需要的符合,否则无解。 | ||
+ | |||
+ | 然后贪心的从第一行开始修改,如果不够,继续在第二行修改。 | ||
+ | |||
+ | 不过需要注意,可能出现修改不到第一行,列就满足了,但行仍然没有满足的情况,需要处理一下:方法是,从第一列开始贪心的改(因为这样能保证字典序最小)。 | ||
== Problem I == | == Problem I == | ||
− | + | Upsolved by oxx1108. | |
+ | |||
+ | 题意:给一棵树,以及一些红点,求取若干结点不存在祖先关系且恰好有$k$个红点的方案数。 | ||
+ | |||
+ | 题解:树形dp加个剪枝。 | ||
== Problem J == | == Problem J == | ||
Line 42: | Line 84: | ||
Solved by Xiejiadong. 04:58:11(+3) | Solved by Xiejiadong. 04:58:11(+3) | ||
+ | |||
+ | 题意:给出一些点,每次询问一个区间的点,允许删除其中的一个点,求覆盖所有点所需要的最小正方形边长(正方形边必须与坐标轴平行)。 | ||
+ | |||
+ | 题解:显然,如果没有删除操作,答案就是行的最大差值*列的最大差值。 | ||
+ | |||
+ | 那么允许删除一个,我们就还需要维护八个信息:行的区间最大值,行的区间最小值,行的区间次大值,行的区间次小值,列的区间最大值,列的区间最小值,列的区间次大值,列的区间次小值。 | ||
+ | |||
+ | 直接用主席树维护一下就好了。不过要注意可能两个极值取属于同一个点坐标,这个需要用map来支持特判。 |
Latest revision as of 09:16, 3 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
一开始这道题目在用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来支持特判。