mhlwsk的博客

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3974

乍一看是要维护一颗树节点的颜色，每次要修改一整颗子树的颜色。但如果把这棵树的DFS序（这里用的先序遍历）写出来，就可以发现每次维护的颜色都是一段连续DFS序上的，用线段树维护即可。

题目链接：http://poj.org/problem?id=2528

基本思路是把坐标离散化，然后用线段树维护区间颜色即可。
颜色标记有未涂色、某一种具体单色、混合色三种，向上维护的时候需要特别判断。查询区间中颜色总数量时，只需要向下找到单色的节点，并借助一个vis数组统计颜色即可。

需要注意的是这题卡常数，离散化时不能用map，因为map常数非常大会被卡掉。可以用lower_bound来搞，也可以直接用一个数组来搞（因为数据范围只有1e7）。

题目链接：http://poj.org/problem?id=1934

先用动态规划求两个字符串的最长公共子序列的保存在dp[i][j];dp[i][j]表示s1字符串1到i和s2字符串1到j的最长公共子序列的长度

然后用两个变量last1[i][j],last2[i][j]来分别保存字符j(a的序号为0，b的序号为1，…..z的序号为25)在字符串1-i中出现的最大标号，要是字符j没有出现,则last[i][j]= 0;

然后从两个字符串的长度len1和len2开始枚举a—z字符,比如开始 t1 = last1[len1][0], t2 = last2[len2][0]表示a在s1字符串1—len1的最大下标为t1, 在s2字符串1–len2的最大下标为t2，那么若dp[t1][t2] 的值为s1和s2的最大公共子序列长度cnt则表示这个字符符合，保存起来，否则枚举下一个字符b。若满足情况的话，在继续在t1-1 和 t2 - 1 符合最大公共子序列为cnt - 1的字符串保存，如此循环，知道到达最长公共子序列为0时结束。把保存的字符串放入set集合里面，让它按字典序排序。
引用自https://blog.csdn.net/xiaoxiaoluo/article/details/8169533

动态规划具有重叠子问题的特性，dp数组只保留了相当有限的信息。为了求出所有满足条件的子序列，必须另开一个数组维护信息。
另外实现上有一个小细节出错了，就是s[i]下标从0开始，dp[i][j]下标从1开始，一开始混在一起了。

题目链接：http://codeforces.com/problemset/problem/460/C

二分一个高度，检查时考虑这样一种贪心策略：扫描数组，如果遇到高度小于二分值的就把它和它后面连续w个数加上a[i]-mid，如果能让所有的数大于mid，则二分值是满足条件的。

这题直接暴力会超时，线段树会卡常数，建树时必须是O(n)的复杂度，我尝试一开始建立一颗线段树并把它保存起来，每次重新建树时直接memcpy，卡过了这道题。

题目链接：http://codeforces.com/problemset/problem/377/A

这题需要逆向思维。考虑直接怎么往上放墙的策略非常麻烦。此时我们换个策略，尝试把所有的空缺都放上墙，并从这些新墙中连续拆掉一部分，那么剩下的新墙就是我们需要放的了。

题目链接

手推前几项可以发现，第一次消一定是从数列的正中间消最优，消完这一次后中间会出现一个零，假设n是偶数，那此时两边会出现两个一样的数列，对它们的操作是镜像的，因此只考虑一个并重复上面的操作即可，如果n是奇数，那么每次只考虑较大的那个子数列即可。

题目链接：http://poj.org/problem?id=3233

题目分析：分析可以得到
k为偶数：sum(k) = (1+A^(k/2)) ( A+A^2+……+A^(k/2)) = (1+A^(k/2)) sum(k/2)
k为奇数：sum(k) = (1+A^((k-1)/2)) * sum(k/2) + A^k
引用自https://blog.csdn.net/tc_to_top/article/details/43878231

看到这题应该考虑到提公因式，或者凑成多项式相乘的形式，进而想到A^1+A^2+…+A^n的题解拆法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6185

这题比赛时猜到是矩阵快速幂了，但推公式推了好久没有推出来，比赛结束后看到有一个题解，对于填满n列的情况，只关心第n+1列露出的形状，这些形状可以分为6类，而新的一列一定是从第n+1列的这6种形状转移到第n+2列的这6种形状。这样就可以对这6种形状写出转移矩阵了。

题解链接：https://blog.csdn.net/a664607530/article/details/77619554

情况a为第n行刚好填满且没有突出到第(n + 1)行，即为所求答案，由图不难推出：
a[n] = a[n - 1] + b[n - 1] + c[n - 1] + dx[n - 1] + dy[n - 1]
b[n] = a[n - 1]
c[n] = a[n - 1] + e[n - 1]
dx[n] = a[n - 1] + dy[n - 1]
dy[n] = a[n - 1] + dx[n - 1]
e[n] = c[n - 1]
令d[n] = dx[n] + dy[n]
则 a[n] = a[n - 1] + b[n - 1] + c[n - 1] + d[n - 1]
b[n] = a[n - 1]
c[n] = a[n - 1] + e[n - 1]
d[n] = a[n - 1] * 2 + d[n - 1]
e[n] = c[n - 1]

根据这个构造出矩阵即可

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4704

求解S(k)，把N分成k个数之和，问有多少种方案，这个问题等价于n个皮球分成k堆有多少种方案，套用高中学的隔板法得到公式为C(n-1, k-1)。
此时S(1) + S(2) + … + S(n) = C(n-1, 0) + C(n-1, 1) + … + C(n-1, n-1) = 2^(n-1)。套用费马小定理求解即可。

费马小定理：a^(n-1)≡1 (mod n), n为质数。
推论：x^y≡x^(y%(n-1)) (mod n)，n为质数。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5984

题解链接：https://blog.csdn.net/toy_block/article/details/53433240
第一次做连续概率的题，这里要设一个函数f(x)，代表距离右边界距离为x的点的切割次数期望为f。
当x < d时，显然f(x)为0；当x > d时，f(x)=1+x到d这一段的平均期望。注意边界条件f(d)=1。