A - The Number of Even Pairs
相加为偶数只有偶加偶和奇加奇两种情况，其实就是在\(n\)个数中取两个（\(C\binom{2}{n}\)），在\(m\)个数中取两个（\(C\binom{2}{m}\)）。
B - String Palindrome
直接取出每一部分的字符串，判断到中心距离相等的位置的字符是否相等即可。
时间复杂度\(O(|s|)\)。
C - Maximum Volume
和一定差小积大。
其实就是一个均值不等式。
设棱长为\(a,b,c\)，则 \(a \times b \times c \leq \frac{(a+b+c)^3}{27}=\frac{x^3}{27}\)，当\(a=b=c\)时成立。
D - Banned K
我们可以把 \(n\) 个数中有多少相同的数对，因为每个数都很小所以这点我们可以用堆来做。
设 \(cnt[i]\) 代表 \(i\) 这个数出现的次数所以答案等于 \(\sum_{i=1}^{n}\frac{cnt[i] \times (cnt[i]-1)}{2}\)。
现在我们来看删掉一个值为 \(x\) 的数。
\(cnt[x]\) 的值减小了一，它的贡献变成了 \(\frac{(cnt[x]-1) \times (cnt[x]-2)}{2}\)，相比之前减少了 \(cnt[x]-1\)。
设不删时的答案是 \(tot\)，则删掉一个权值为 \(x\) 的数的答案为 \(tot-(cnt[x]-1)\)。
单词询问复杂度O(1)。
E - Dividing Chocolate
我们发现n非常的小，于是我们可以枚举行之间且的情况，再判断列之间要切的情况，取最小值即可。
时间复杂度\(O(2^n \times n \times m)\)
F - Knapsack for All Segments
考虑一组和为s的排列x1<x2<...<xk，所有[1,x1]内的L，[xk, n]之内的R都包含这组排列，所以它的贡献就是\(x_1 \times (n-x_k+1)\)。
设dp[i][j]表示枚举到第i个数，和为j的排列的第一个数的和。
显然dp[0][j]都是0。转移方程类似01背包，dp[i][j]=dp[i-1][j]+(j==a[i]?i:0)。
考虑如何统计答案，如果a[i]=s，ans+=i(n-i+1)；如果a[i]>s，ans+=dp[s-a[i]](n-i+1)。如果a[i]<s则不用更新。
当然类似于背包问题，这题也可以用滚动背包优化空间复杂度。
时间复杂度O(ns)；空间复杂度O(n+s)
标签：AtCoder,cnt,frac,Beginner,159,复杂度,个数,times,dp From： https://www.cnblogs.com/zcr-blog/p/17068239.html