【8.2】代码源 - 【货币系统】【硬币】【新年的问题（数据加强版）】【三段式】

#852. 货币系统

题意：给定货币系统。对于某价值，小 t 每次会从钱包里找出不超过还需要支付的金额的最大货币，用于支付，一直到支付完毕。如果对于所有正整数价值，不存在其他支付方案的货币总数严格小于小 t 的支付货币数，那么这个国家是聪明的。$1\le n\le 1000,1=a_i<a_2<\cdots a_n\le 10000$

题解：(DP) 代码源每日一题 Div1 货币系统

思路：首先有个结论（不会证）：$\forall w>2\times \max (a_i),w$ 是聪明的。

那么我们只需要判断这个上界之下的数字即可。先暴力计算每个价值小 t 的支付货币数，然后可以用背包求解每个价值的最少货币数，逐一判断是否聪明。把一个面值 $a_i$ 看作体积为 $a_i$ ，价值为 $1$ 的物品，问你恰好装满背包的最少价值，跑一下背包就行。

AC代码：http://oj.daimayuan.top/submission/315376

---

#815. 硬币

题意：略。

题解：(暴力) 代码源每日一题 Div1 硬币

思路：不会，直接抄的题解。

AC代码：http://oj.daimayuan.top/submission/316043

---

#856. 新年的问题（数据加强版）

题意：给定一个 $n\times m$ 的矩阵，要求在每列中恰好选择一个数，并且这些数里面存在两个数在同一行，要求使这 $m$ 个数的最小值最大，输出该值。$2\le n,m\le 2500,a_{i,j}\le 10^9$

思路：二分最小值，判断是否有选择方案。判断的话，保留大于等于二分数的元素，如果每一列都有元素，且存在某行有至少两个元素，则存在选择方案。

这里要注意一个和寻址方式有关的常数优化。

我的遍历（400+ms）：

rep(j, 1, m) rep(i, 1, n)
	if(a[i][j] >= down){
    
		// solve
	}

AC代码遍历（220ms）：

rep(i, 1, n) rep(j, 1, m)
	if(a[i][j] >= down){
    
		// solve
	}

数组不管是一维还是高维，在内存里都是连续存放的。后者遍历，绝大多数的寻址都是连续的，因为 cache 的存在，我们都可以根据上一次的地址快速得到。而前者遍历，我们每次寻址在数组里都是跳跃的而不是连续的，取数就会很慢。

AC代码：http://oj.daimayuan.top/submission/316533

---

#872. 三段式

题意：有一个长度为 $n(1\le n\le 10^5)$ 的序列 $a(|a_i|\le 10^5)$ ，现在我们想把它切割成三段(每一段都是连续的），使得每一段的元素总和都相同，请问有多少种不同的切割方法。

思路：前缀和。设 $base=\frac{pr{e}_n}{3}$ ，那么对于每个 $pr{e}_i=2\times base$ ，看一下前面有多少个 $j(j\in [1,i-1])$ 满足 $pr{e}_j=base$ 。注意 $i$ 不能枚举到 $n$ ，因为是非空。时间复杂度 $O(n\log n)$ 。

AC代码：http://oj.daimayuan.top/submission/316554