2018 Multi-University, HDU Day 8

Problem A

Solved by zerol. 00:41 (+1)

题意：求 $\sum_{i=1}^m x_i = k$ ($0 \le x_i < n$) 的整数解的组数。

题解：如果只有限制 $0 \le x_i $，那么可以用插板法很方便的算出来。对于上限，对于至少 0,1,2...,m 个数超过上限的方案数也能方便计算，剩下的就是容斥一下求出恰好 0 个数超过上限的方案。

Problem B

Solved by kblack. 03:10 (+2)

题意：给定三角形和矩形的宽度，求矩形的最小高度，使得矩形能装下三角形。

题解：分两种情况，卡住和没卡住，没卡住的情况要求某条边与垂直，求三角形的高就好了（注意判断整个的宽度），卡住的情况，显然可以至少卡住两个点，枚举一下，然后算一算就好了。可以通过无脑点积减少不必要的分类讨论。

Problem D

Solved by zerol. 01:23 (+1)

题意：构造一个 $h \times w$ 的括号矩阵，使得匹配的行数、列数之和最大。

题解：两个奇数或者一奇一偶的情况显然。对于两个偶数的情况考虑以下两种构造之一：

$h+w-2$

((((((((
(()()())
()()()()
(()()())
()()()()
(()()())
()()()()
()))))))

$\max(h,w)-\min(h,w)/2-1$

()()()
(()())
()()()
(()())
()()()
(()())

zerol：看这一度 2%~3% 的通过率，吓坏了，果不其然，先 WA 一发。

Problem E

Solved by zerol. 00:14 (+)

题意：给一个 $3 \times 3$ 的数阵，每次旋转一个 $2 \times 2$ 的子阵，求最终结果。

题解：赤裸裸的签到。

Problem F

Upsolved by ultmaster.

题意：求在面对换、面翻转操作下本质不同的大小为 $m \times n \times p$ 的三维 01 数组的个数。

题解：建议先去做 ProjectEuler 的那个题。（为了推广 Mathematica 贴一份代码，其实也一点都不简洁。）

partitions = IntegerPartitions[n];
cycles = Flatten[Table[{partitions[[i]], partitions[[j]]}, {i, 1, Length[partitions]}, {j, 1, Length[partitions]}], 1];
Length[cycles]
c[p_] := Total[p]!/(Times @@ p)/(Times @@ Map[Count[p, #]! &, Range[Total[p]]])
g[c_, k_] := Times @@ Flatten[Table[2^(c[[i]]*k[[j]]/LCM[c[[i]], k[[j]]]), {i, 1, Length[c]}, {j, 1, Length[k]}]]
flip[c_, k_] := Flatten[Table[If[col == i, LCM[c[[i]], k[[j]]]/c[[i]], If[col == Length[c] + j, LCM[c[[i]], k[[j]]]/k[[j]], 0]], {i, 1, Length[c]}, {j, 1, Length[k]}, {col, 1, Length[c] + Length[k]}], 1]
h[c_, k_] := 2^(2 n - MatrixRank[flip[c, k], Modulus -> 2])
ans = Total[Map[c[#[[1]]]*c[#[[2]]]*h[#[[1]], #[[2]]]*g[#[[1]], #[[2]]] &, cycles]] / (n!*2^n)^2

然后就像题解所说的那样推广到三维的就好了。大概效率还是不大行，需要打表的。

题解最后有个地方有个笔误，应该是 $n+m+p$ 而不是 $nmp$。

ultmaster's comment: 本题最难的地方在于把两种变换拆开算，最后乘到一起。这里面的不动点计数逻辑还是比较复杂的。

Problem G

Upsolved by zerol.

题意：给定 $n$ 张卡片，每张卡片正反面各有一个数。问至少要翻转多少张卡片，才能使正面向上的数互不相同，并求方案数。

题解：首先卡片反面的数字向正面的数字连边。问题转化为了至少翻转多少条边能够使得每个数字的入度至多为 1。考虑原图的底图，对于所有联通分量，只有基环树或者树才可能有解。对于树，枚举一下根的位置（根从 a 到 b，只需要把 ab 之间的边反向即可）。对于基环树，枚举环的方向（要么正要么反），而环上的树的方向是唯一确定的（都要朝外）。

Problem I

Solved by zerol. 03:37 (+1)

题意：给定若干个字符串，每个字符串有一个值。随机选取一个长度不超过 $q$ 的串，问是给定字符串中父串的值的乘积的期望。

题解：建立广义后缀自动机。对于一个串的所有后缀接受结点插入该串标识。然后在树上启发式合并，获得每个结点的所有标识的对应的值的积。最后每个结点对应到一段长度，区间加，离线查询所有前缀和，差分或者 bit 搞一下。

Problem J

Solved by kblack. 00:33 (+1)

题意：给一个序列，每次贪心选取比前一个数大的数。每次询问修改一个数，求修改后的序列的能选出多少个数。询问不叠加。

题解：将询问挂在修改的位置上，先正着跑一遍看看每个点实际的开头是修改后的数字还是之前的最大值，并得到答案的前面部分，然后从后往前跑一遍单调栈，每到有修改的位置，在单调栈上二分即可得到后面部分。

Problem K

Solved by ultmaster. 04:56 (+4)

题意：给定一个气球矩阵，扎掉一个气球后，同行同列的气球都消失。问对于每个 $1 \le x \le k$，扎恰好 $x$ 次能够清除所有气球的方案数。

题解：$f(i,state)$：前 $i$ 行，状态每一维上有 0 1 2，0 表示该行没填过，1 表示该行已填过不能再填，2 表示该行以后必须得填）。只有在该行没填东西，又有某些列没有被覆盖的时候，才会产生 2，所以状态总数是 $n \times 3^m$，转移代价是 $m$。所以总复杂度是 $O(nm 3^m)$。

注意两个事情：一、时限较紧，注意常数优化（包括但不限于跳过 $f(i,j)=0$ 的那些状态的转移，或者评测机抖动需要多交两次）。二、计算过程不会，但答案要乘以 $m!$ 会爆 LL，需要 int128。

Problem L

Upsolved by kblack. (-5)

题意：告诉你工厂每个月的原料价格，客户需求，产能，生产成本，原料和产品的仓储成本，产品的仓库容量限制，求满足客户需求前提下的最小成本。

题解：搞了个烦得一批的线段树，结果贪心就好了，每天假装完全生产，然后用掉最便宜的，存不下的话，最贵的就当他无事发生。