题意：给定 n ( n ≤ 100 ) n(nleq 100) n(n≤100) 个整数，将其划分为恰好 k ( k ≤ 100 ) k(kleq 100) k(k≤100) 个子数组，求对每个子数组求和后按与运算的最大值。
题解：(动态规划) 代码源每日一题 Div1 数组划分
思路：刚开始我定义的是 d p ( i , j ) dp(i,j) dp(i,j) 为前 i i i 个元素分为 j j j 块的最大值，转移方程是 d p ( i , j ) = max ( d p ( k , j − 1 ) & ( s u m ( k + 1 , i ) ) ) dp(i,j)=max(dp(k,j-1)&(sum(k+1,i))) dp(i,j)=max(dp(k,j−1)&(sum(k+1,i))) ，但是这样是不行的。详细讲一下为什么不行。
首先，每个状态本质是集合，集合中每个元素对应的有权值，根据题目我们通常要求集合的权值上界或者下界（即通常所说的 max − min max-min max−min ），即集合的属性。如果我们采用 DP 递推的方式求这种属性，就必须保证后继状态的属性与前驱状态的属性是单调的。怎么理解呢？
我们定义一个自变量 x x x ，他的定义域就是前驱节点的权值值域（当然是有上下界的）。我们根据递推方程，后继节点的权值值域 y = f ( x ) y=f(x) y=f(x) 。只有当 f ( x ) f(x) f(x) 在定义域内是递增的，才能通过维护前驱的上界（下界），来得到后继值域的上界（下界）。如果不满足单调递增，那么后继状态的极值不一定会在前驱状态的上界（下界）取得。动态规划的这个递推单调属性也很重要。
回到这题，因为是位运算，前驱节点的取值递增不一定使得后继节点的值递增，那么这个方法就不行了。
这道题的做法是：从高位开始枚举答案的二进制位，然后判断序列是否有分成 k 份的方案使得和的与大于等于 ans，然后做出是否保留该位 1 的决策。DP 存在性的话， y ≥ x ygeq x y≥x 的充要条件是 ( y & x ) = = x (y&x)==x (y&x)==x ，如果存在分割方案的话，每一段都必须满足 s u m i & x = = x sum_i&x==x sumi&x==x ，定义 d p ( i , j ) dp(i,j) dp(i,j) 表示前 i 个分成 k 份是否存在方案使得和的与大于等于 x，DP 转移存在性。
AC代码：http://oj.daimayuan.top/submission/290489
#611. 拆拆
题意：多组数据。每组给定两个数 X,Y，问有多少个长度为 Y 的整数序列之乘积为 X。 T ≤ 1 0 5 , X , Y ≤ 1 0 6 Tleq 10^5,X,Yleq 10^6 T≤105,X,Y≤106 。
思路：拆分质因子然后分配即可。
拆分质因子的方法优化（ O ( a ∼ b ) O(asim b) O(a∼b) 表示预处理时间为 a a a，查询时间为 b b b）：
- 预处理得到所有质数，然后只用质数去筛，时间复杂度 O ( n ∼ n ln n ) O(nsimfrac{sqrt n}{ln{sqrt n}}) O(n∼lnn n )
- 用埃氏筛预处理所有数，得到每个数的质因子（级数为 log n log n logn），时间复杂度为 O ( n × log n ∼ log n ) O(ntimes log nsim log n) O(n×logn∼logn)
这道题用的是第二个优化。我们把一个数的所有质因子预处理存起来，然后直接使用即可。
vectorprimes[M]; for(int i = 2; i < M; i ++ ){ if(primes[i].size()) continue; for(int j = i; j < M; j += i){ int t = j, cnt = 0; while(t % i == 0) cnt ++ , t /= i; primes[j].push_back(cnt); } }
AC代码：http://oj.daimayuan.top/submission/291303
#618. 选数2
题意：
题解：(贪心)代码源每日一题 Div1 选数2
思路：首先求出 m m m 。如果存在长度为 m m m 的子序列满足题意，那么必定存在长度为 m m m 的子区间满足题意，因为我们固定右端点，把其他数向右移，平均数只会变得更大。这样可以二分求出 m m m 。
求出 m m m 之后，我们对于每个满足题意的子串，都只让左端点向左移，这样可以保证左端点向左移的距离尽可能地远。仍然是二分。
AC代码：http://oj.daimayuan.top/submission/290739
#131. 最大公约数
题意：你有一个环，环上有 n n n 个正整数。你能将环切成段，每段包含一个或者多个数字。
对于一个切分方案，优美程度为每段数字和的最大公约数，你想使切分方案的优美程度最大，对于 k = 1 , 2 , ⋯ , n k=1,2,cdots,n k=1,2,⋯,n 输出答案。
题解：(数学/枚举/环上问题)代码源每日一题 Div1 最大公约数
思路：我们把环分为 k k k 份，那么 g c d ∣ s i , i ∈ [ 1 , k ] gcd|s_i,iin [1,k] gcd∣si,i∈[1,k] ，即 g c d ∣ ∑ i = 1 k s i = s u m gcd|sum_{i=1}^k{s_i}=sum gcd∣∑i=1ksi=sum 。我们枚举 s u m sum sum 的因子即 g c d gcd gcd 。因子的数量级可以认为是期望 log n log n logn ，最坏 n sqrt n n 的。
对于 g c d gcd gcd ，我们可以求出最多可以分割为多少个段，因为段可合并，后缀和最大即可。如果是普通序列，那么直接求前缀和中有多少个数在 m o d g c d bmod gcd modgcd 的意义下为 0 0 0 。如果是环的话，我们要求前缀和中有多少个数在 m o d g c d bmod gcd modgcd 的意义下相等 。
AC代码：http://oj.daimayuan.top/submission/290873
