[8.2] Code Source - [Currency System] [Coins] [New Year's Questions (Data Enhanced Edition)] [Three Stages]

#852. 货币系统

题意：给定货币系统.for a value,小 t Each time, the maximum currency that does not exceed the amount to be paid will be found from the wallet,用于支付,until payment.if for all positive integer values,The total number of currencies for which no other payment scheme exists is strictly less than small t of payment currencies,then this country is smart.$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$ 是聪明的.

Then we only need to judge the number below this upper bound.First brute force to calculate each small value t of payment currencies,The knapsack can then be used to find the minimum number of coins for each value,One by one to judge whether it is smart.put a face value $a_i$ regarded as the volume of $a_i$ ,价值为 $1$ 的物品,Ask the least value for what you happen to fill your backpack with,Just run the backpack.

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

#815. 硬币

题意：略.

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

思路：不会,直接抄的题解.

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

#856. new year question（数据加强版）

题意：给定一个 $n\times m$ 的矩阵,requires that exactly one number be selected in each column,And there are two numbers in these numbers on the same line,request to make this $m$ The minimum and maximum number of,输出该值.$2\le n,m\le 2500,a_{i,j}\le 10^9$

思路：二分最小值,Determine if there is an option.判断的话,Keep elements greater than or equal to two fractions,if each column has elements,and there exists a row with at least two elements,there are options.

Here we should pay attention to a constant optimization related to the addressing mode.

my traversal（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
	}

Whether the array is one-dimensional or high-dimensional,are stored contiguously in memory.后者遍历,The vast majority of addressing is contiguous,因为 cache 的存在,We can all quickly get it based on the last address.while the former traverses,Each time we address the array, we jump instead of consecutively,Counting will be slow.

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$ ,See how many are ahead $j(j\in [1,i-1])$ 满足 $pr{e}_j=base$ .注意 $i$ cannot be enumerated to $n$ ,because it is not empty.时间复杂度 $O(n\log n)$ .

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