Atcoder比赛总结

ARC130

周末把周日晚的东西都提前补了才过来打。

A： 给出一个字符串，求有多少个位置对，使得分别删去两个位置的两个字符串相同。
连续一串相同字母内的任意两个都合法。

B： 一个 \(W \times H\) 的矩阵，每次操作将某一行或一列染色，求最终状态下每个颜色有多少个格子。
从后往前直接做。

C： 给出两个数 \(a\) , \(b\) ，让你将其重排列，最小化 \(a+b\) 每一位的和。
考虑两数相加进位是有 \(-9\) 的贡献的，如果两数之和为 \(9\) ，但是后面有 \(1\) 进位，也可以有贡献。
那么暴力枚举两个最小位，这里钦定其能进位，由于进位至多为 \(1\) ，所以可以贪心地将能进位的全部靠在最小位，此时能进位的是 \(9\)~\(18\) 。
将这些放完后会有两种情况，一种是两个数都还有剩，这时只能全部求和了。
另一种是一种用完了，那另一个数就能优先把 \(9\) 放完，此时可以去掉所有 \(9\) 的贡献。
这样写 WA 了两发，还一直以为是细节没写对。
后来意识到最后的两种情况可以做点文章。
两个数都还有剩的可以并到第二种，做法是将枚举的最小位往后移，把影响答案的不可能进位数塞到前面。

D： 给出一棵树，要求计算这样的排列数：对于树上的节点，每个和它相邻的节点的对应值要么都小于它，要么都大于它。
一定要注意到是排列不然会打空。（同时说明了手玩数据的必要性）
我们设 \(f_{i,j,0/1}\) 为在 \(i\) 号节点，其子树中有 \(j\) 个 小于/大于 它，它的所有儿子都 小于/大于 它，的方案数。
转移的时候要带上排列数的系数。