标签：begin end ATC 题解 序列 定时 cases dp

ABC129

前三题略

D.lamp

虽然数据范围不大，但也没法暴力 check ，可以考虑分别维护每行（每列）障碍物的纵（横）坐标，可以考虑到插入 std::vector 中，然后对于每一个点查找横竖方向上的前驱后继，再减去 \(3\) 即可。为了方便维护和简化讨论，对于每列可以将 \(0\) 和 \(h+1\) 也插入进 std::vector ，对于行同理

E.Sum Equals Xor

由于满足 \(a+b=a\bigoplus b\) ，且异或本质为二进制不进位加法。因此可得出 \(a\) 和 \(b\) 不能在相同位上同为 \(1\)

可通过数位dp解决该问题，但需保证 \(a\bigoplus b\leq L\) 恒成立

也可通过线性dp解决，定义 \(f[i][0]\) 为前 \(i\) 位与 \(L\) 相同的方案数，\(f[i][1]\) 为前 \(i\) 位小于 \(L\) 的方案数

可得转移方程

\[\begin{cases} f[i][0]=f[i-1][0]*2,L[i]=1 \\ f[i][0]=f[i-1][0],L[i]=0 \end{cases} \]

\[\begin{cases} f[i][1]=f[i-1][0]+f[i-1][1]*3,L[i]=1 \\ f[i][1]=f[i-1][1]*3,L[i]=0 \end{cases} \]

F.Takahashi's Basics in Education and Learning

矩阵快速幂，待补

ABC130

前三题略

D.Enough Array

套路题，由于 \(a_i\) 为整数，保证了前缀和的单调性，做出前缀和后对于每一个位置二分即可

E.Common Subsequence

比较有意思的dp，设计状态 \(f[i][j]\) 为 \(a\) 序列前 \(i\) 项与 \(b\) 序列前 \(j\) 项相同子序列的个数

可得转移方程： \(f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1]\)

该部分有容斥的知识，即 \(|A\bigcup B|=|A|+|B|-|A\bigcap B|\)

需要注意的时，当 \(a[i]=b[j]\) 时，转移方程为 \(f[i][j]=f[i][j-1]+f[i-1][j]\)

最终可得

\[\begin{cases}f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1],a[i]\neq b[j]\\f[i][j]=f[i][j-1]+f[i-1][j],a[i]=a[j]\end{cases} \]

F.Minimum Bounding Box

算法1：可以大力分类讨论，因为答案只会受到边界点的印象，因此同方向运动只考虑坐标更大（小）的点，但较为复杂

算法2：裸的三分，证明不会，代码实现简单

标签：begin,end,ATC,题解,序列,定时,cases,dp
From： https://www.cnblogs.com/Jadebo1/p/17029031.html