题意：给定货币系统。对于某价值，小 t 每次会从钱包里找出不超过还需要支付的金额的最大货币，用于支付，一直到支付完毕。如果对于所有正整数价值，不存在其他支付方案的货币总数严格小于小 t 的支付货币数，那么这个国家是聪明的。
1
≤
n
≤
1000
,
1
=
a
i
<
a
2
<
⋯
a
n
≤
10000
1\leq n \leq 1000,1=a_i
思路：首先有个结论（不会证）： ∀ w > 2 × max ( a i ) , w \forall w>2\times \max(a_i),w ∀w>2×max(ai),w 是聪明的。
那么我们只需要判断这个上界之下的数字即可。先暴力计算每个价值小 t 的支付货币数，然后可以用背包求解每个价值的最少货币数，逐一判断是否聪明。把一个面值 a i a_i ai 看作体积为 a i a_i ai ，价值为 1 1 1 的物品，问你恰好装满背包的最少价值，跑一下背包就行。
AC代码：http://oj.daimayuan.top/submission/315376
题意：略。
思路：不会，直接抄的题解。
AC代码：http://oj.daimayuan.top/submission/316043
题意：给定一个 n × m n×m n×m 的矩阵，要求在每列中恰好选择一个数，并且这些数里面存在两个数在同一行，要求使这 m m m 个数的最小值最大，输出该值。 2 ≤ n , m ≤ 2500 , a i , j ≤ 1 0 9 2\leq n,m\leq 2500,a_{i,j}\leq 10^9 2≤n,m≤2500,ai,j≤109
思路：二分最小值，判断是否有选择方案。判断的话，保留大于等于二分数的元素，如果每一列都有元素，且存在某行有至少两个元素，则存在选择方案。
这里要注意一个和寻址方式有关的常数优化。
我的遍历（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
题意：有一个长度为 n ( 1 ≤ n ≤ 1 0 5 ) n(1\leq n\leq 10^5) n(1≤n≤105) 的序列 a ( ∣ a i ∣ ≤ 1 0 5 ) a(|a_i|\leq 10^5) a(∣ai∣≤105) ，现在我们想把它切割成三段(每一段都是连续的），使得每一段的元素总和都相同，请问有多少种不同的切割方法。
思路：前缀和。设 b a s e = p r e n 3 base=\frac {pre_n} 3 base=3pren ，那么对于每个 p r e i = 2 × b a s e pre_i=2\times base prei=2×base ，看一下前面有多少个 j ( j ∈ [ 1 , i − 1 ] ) j(j\in[1,i-1]) j(j∈[1,i−1]) 满足 p r e j = b a s e pre_j=base prej=base 。注意 i i i 不能枚举到 n n n ，因为是非空。时间复杂度 O ( n log n ) O(n\log n) O(nlogn) 。