月度归档:2018年01月

2017-2018年问题求解(三)期末上机考试 Day2 题解

C. 花椰菜与西兰花

题意:有一块菜地,被分成 \(n \times m\) 格,每格被种上花椰菜、西兰花或什么都不种。现在要在格子之间建一些篱笆,使得被篱笆分隔出来的每一连通区域中,至多只有一种作物。问篱笆的总长度最少是多少。

数据范围:\(1 \leq n \leq 50, 1 \leq m \leq 1000\)

题解:最小割还是挺明显的。源点到所有花椰菜连上无穷容量边,所有西兰花到汇点连无穷容量边,然后相邻两个区域连容量为 1 的双向边。根据 MFMC 定理,答案就是从源点到汇点的最大流。

D. 旅游路线

题意:有 \(n\) 个区域,每个区域内有 \(s_i\) 个车站。区域内的车站之间移动需花费 \(k_i\) 时间;此外,还有 \(m\) 辆班车来回于两个车站之间,并需要花费 \(c_j\) 代价。问从 1 号区域的第 1 个车站到 \(n\) 号区域至少需要花费多少时间。

数据范围:

  • 部分数据满足 \(1≤n≤20, 1≤m≤100, 1≤s_i≤5, 1≤k_i, c≤1000\);
  • 部分数据满足 \(1≤n≤1000, 1≤m≤50000, 1≤s_i≤200, 1≤k_i, c≤1000\);
  • 部分数据满足 \(1≤n≤30000, 1≤m≤2*10^5, s_i=1, 1≤k_i, c≤1000\);
  • 部分数据满足 \(1≤n≤5000, 1≤m≤2*10^5, 1≤s_i≤50, 1≤k_i, c≤1000\)。

题解:最短路,但是裸的 Dijkstra 肯定是过不了的。这是因为区域内暴力连边的话,会形成完全图,导致边数爆炸。为此,可以为每个区域设置一个特殊节点,该节点可以表示从区域内任何一个节点出发。这样,每个区域内的点都可以连一条长度为 \(k_i\) 的单向边到该特殊节点,此外,从该区域中的某一点出发的边,同样也可以从特殊节点出发。这样整个图中只有 \(m + \sum s_i \) 条边,跑 Dijkstra 就不会T了。

2017-2018年问题求解(三)期末上机考试 Day1 题解

A. 智能机器

题意:求 \(\sum_{i=l}^r d(i^k)\) 模 16290047,其中 \(d(n)\) 表示 \(n\) 的约数个数。

数据范围:\(r – l \leq 10^6, l \leq r \leq 10^{12}, k \leq 10^6\)。

题解:首先,对于任意正整数 \(n\),如果它的唯一分解为

$$ n = q_1^{a_1} q_2^{a_2} \cdots q_m^{a_m} $$

那么它的约数个数就是

$$ d(n) = (1+a_1)(1+a_2)\cdots(1+a_m) $$

从而

$$ d(n^k) = (1+ka_1)(1+ka_2)\cdots(1+ka_m) $$

这样,我们只要对每个要求的 \(i\),找出所有形如 \(p^x | i\) 中 \(x\) 最大的因子。注意到这样的因子不可能超过 \(\sqrt{i}\),除非 \(x = 1\)。从而我们对素数 \(p\),可以枚举 l~r 区间范围内的 \(rp^x\) 形式的数(其中 \(r\) 不是 \(p\) 的倍数),并乘上 \(kx+1\) 的贡献。如果某个数除以所有枚举过的 \(p^x\) 形式的因子仍然不为 1,说明剩下的数一定是一个素数,那么还要乘上 \(k+1\) 的贡献。

经过仔细的分析,上述三重循环枚举的时间复杂度实际上不会超过 \(O(\frac{\sqrt{r}}{\log r} \log (r – l))\),完全可以接受。

B.  Lunatic

题意:一共有 \(n\) 个动作,每个动作可以在 \([l_i, r_i]\) 之间的某个时刻完成,完成后可得到 \(v_i\) 分数。每一时刻只能做一样动作,计算最多能拿多少分。

数据范围:\(1 \leq n \leq 1000, 1 \leq s_i \leq t_i \leq 30000, 1 \leq v_i \leq 1000\)

题解:显然是带权二分图的最大权匹配。考场上没带 Kuhn-Munkres 的板子,只好敲费用流,最后 2 分钟卡过去的…(不过这题用裸的 KM 算法应该也过不了 233)其实这题标答是贪心匹配,将边按收益排序,优先匹配收益高的就行了…

说一下费用流的做法吧。每个动作连一条容量为 1,费用为 \(-v_i\) 的边到 \([l_i, r_i]\) 中的每个时间点,源点到每个动作连费用为 0 容量为 1 的边,每个时间点连费用为 0 容量为 1 的边到汇点,然后跑最小费用流取负就好了。不过这样是过不了全部数据的,要过全部数据,还要加两个优化:一是把时间区间离散化;二是如果某个动作有 \(r_i – l_i + 1 \geq n\),那么这个动作一定可以在某个时刻完成,就不需要加到图里面了。