AtCoder Regular Contest 146

Problem A. Three Cards

取任意张也可做。排序两次，第一次用数字排序，第二次用字符串排序（但是要修改一下字典序的定义，不存在的字符取无穷大）。

Problem B. Plus and AND

题解里说二分，但是应该没有人会去写二分吧（复杂度一样）。。。
当然是去写按位贪心。。。每次确定第 i 位是否可以为 1，那么对于每个数需要求出与当前目标的距离。。
难点在于这个距离函数，需要各种讨论。

当然大牛们都是用位运算一行就把距离函数写出来的囧。。

Problem C. Even XOR

Problem E. Simple Speed

计数，问有多少种满足以下条件的整数序列：
1. 每个数字出现的次数恰好为 Ai。
2. 相邻位置的差的绝对值恰好为 1。

个人觉得这个 dp 非常的优雅！

首先不考虑条件 2，那么就是 多项式系数。
考虑条件 2，我们似乎可以暴力 dp…
dp[i][j] 表示前 i 位，末尾为 j 的方案数，
但这个显然不可行。。因为我们没法记录每个数字当前还剩多少。。

所以核心是我们要避免去讨论当前状态里每个数字还剩多少。。。有办法吗？

答案是有的！逐层推进 就行，也就是用数字的大小划分阶段。。。

那么一开始显然只有。。
1 1 1
下一层，我们要把 2 插入 1 之间的空隙里。。。不妨考察两个边界情况。。。
最少需要 2 个 2。。。变成。。
1 2 1 2 1
最多似乎可以有 4 个 2。。。变成。。
2 1 2 1 2 1 2
其实不止。。因为我们还可以往两边任意的继续加 2。
只不过中间的这个 {2 1 2 1 2 1 2} 现在是一个整体，而且它现在等价于上一轮的一个 {1}。。。这样我们似乎找到了可以描述的状态。。序列的序列。。
比如如果我们有 6 个 2，那么这一轮我们可以是。。
{2} {2 1 2 1 2 1 2} {2}
{2 1 2 1 2 1 2} {2} {2}
{2} {2} {2 1 2 1 2 1 2} …
这三种情况，都和第一轮的 {1} {1} {1} 是等价的。。。

所以我们每一层的任务，就是连接这些子序列之间的空隙，并生成一些新的空隙。
或者更简单的理解。。。下一轮最后等价于一些 {3} {3} {3} 。。。然后我们用上一层的序列，去连接这一层的序列。。。简单组合数即可。。

难点是需要讨论两侧的状态，因为它们可能不可参与拼接。。

所以状态就是 dp[i][j][k]。。当前阶段为 i，两侧可拼接 j 次，中间还有 k 个位置可拼接。。
。。。
分析状态转移，我们会发现这个状态空间非常稀疏，直接开个 map 跑 dp 即可。

Posted by xiaodao
Category: 日常