月度归档:2018年07月

2018牛客暑期ACM多校训练营(第一场)题解

A. Monotonic Matrix

给定$1\leq m,n \leq 1000$,求满足下列条件的$m \times n$矩阵个数,使得

  • $a_{i,j} \in \{0, 1, 2\}$
  • 每一行从左到右和每一列从上到下单调不减

题解:考虑每一行大于等于1和大于等于2的位置,其实就是要求两个单调不减的数列$\{a_i\}, \{b_i\}$的个数,满足对于任意$i$,有$a_i \leq b_i$。

B. Symmetric Matrix

给定$1 \leq n \leq 10^5$,求满足每个元素为非负整数,主对角线全0,每一行和为2的$n \times n$的对称矩阵的数量。

题解:把矩阵想象成邻接矩阵,就是要求顶点带标号的所有不允许自环、但允许重边的2-正则图的数量。

C. Fluorescent 2

在模2域下,给定$m \times n$的01矩阵$M$,$1 \leq n \leq 50$,$1 \leq m \leq 1000$,求对于每一个$n$维向量$v$,$Mv$中0的个数的三次方的和。

D. Two Graphs

给定图$G_1 = (V, E_1), G_2 = (V, E_2)$,求有多少$E_1$的子集$E’$,使得$(V, E’)$与$G_2$同构。点数不超过8。

题解:枚举所有的排列,如果构成子图,就把选出来的边用bitmap表示出来,最后去重即可。

E. Removal

给定$1 \leq n \leq 10^5$个数的序列,每个数为不超过$k$的正整数。问删掉$m$个数后,有多少种不同的子序列。$k, m$不超过10。

题解:用dp[i][j][k]表示前i个数删去j个数后,最后一个数为k的方案数。可以在$O(1)$时间内转移。

F. Sum of Maximum

给定数列$a_1, a_2, \cdots, a_n$,求

\[\sum_{x_1=1}^{a_1} \sum_{x_2=1}^{a_1} \cdots \sum_{x_n=1}^{a_n} \max\{x_1, x_2, \cdots, x_n\}\]

题解:把$\max\{x_1, x_2, \cdots, x_n\}$写为$\sum_{m=1}^a [\exists i, x_i \geq m]$,进而改写为$\sum_{m=1}^a 1-[\forall i, x_i < m]$。将$a_i$排序后,从大到小分段计算,每一段都是$x_i$的一个前缀积乘以$i^k$的求和,后者可用Lagrange插值法快速计算。

G. Steiner Tree

H. Longest Path

I. Substring

给一个字符集为{a,b,c}的字符串,求在同构意义下的子串的等价类的数目。两个串同构当且仅当长度相等,并且存在字符集到字符集的双射f,使得一个串经过f变换后变成另一个串。

题解:将原串经过6种双射f后变成的6个串丢到SAM里,求出所有本质不同的子串。含有大于等于2种子串有6中不同的同构串,而只含有1种字符的串只有3中不同的同构串,分类讨论一下即可。

J. Different Integers

给一个序列,每次询问给出一个区间,求序列扣除这个区间后,有多少个不同数。

题解:在某次询问中,某数不出现当且仅当这个数第一次出现到最后一次出现包含于询问区间中即可。只要离线排序一下,按右端点的顺序处理即可。

2017-2018 问题求解(四)上机考试题解

Day1

A 差异度

题意:给$n (1 \leq n \leq 10^5)$个20位的01串,求两两之间hamming距离的最小值。

解法:此题解法甚多。下面列举3个常见的解法:

  1. 注意到当$n$很大时,最终答案不会太大(考虑一个01串hamming距离为$d$的邻域大小随$d$是指数增长的,然后用鸽巢原理即可)。所以,从小到大枚举答案$d$,并在每个串的$d$-邻域内搜索即可。
  2. 建图。将所有20位的01串视为顶点,相差1位的两个串连边。问题就变成了:给定一个顶点子集,求这个子集中两两距离的最小值。这用多线程bfs就可以解决。时间复杂度为$2^{20}*20$。
  3. 用FWT处理出所有可能的异或值,取popcount最小的那个即可。(FWT课内没学,用了感觉有点犯规,但写起来方便是真的

B 工作安排

题意:某人有$T (0 \leq T \leq 100)$时间,$N (0 \leq N \leq 100)$组工作。每组工作有3种类型:至多选一个做,至少选一个做,无限制。每组工作中最多有100个工作,每个工作有完成的时间和所能得到的收益值。求所能获得的最大收益。

题解:较为复杂的背包问题。用常规的dp就可以解决。对于每组工作的附加限制,在更新dp值的时候需要特殊处理。

Day2

A 矩阵分割游戏

题面:NOI1999 棋盘分割

题意:给一个8*8的矩阵,每次可以横着或竖着掰成两半并舍弃一块,最后得到$n$块子矩阵。求子矩阵数字和的标准差的最小值。

题解:由gay率论相关知识,要使标准差取得最小值,只要让平方和最小即可(因为和是固定的)。然后dp或者记忆化爆搜即可。

B 旅行箱

题意:有$n \leq 42$个数,取出它的一个子集,使得子集和在不超过$W$的前提下,使得子集和最大。(简单背包问题)

题解:用meet-in-the-middle思想。将集合分成两部分,预处理出每部分的所有子集和。然后将这些子集和排序,对于一部分的某个子集和$S$,在另一部分中找出不超过$W-S$的最大子集和,然后取最大值即可。复杂度$O(n2^{n/2})$。