标签：边界 题解 sum dbinom YY ARC157 节点 rightarrow

Atcoder Regular Contest 157

A XXYYX

可以考虑得到 \(a,b,c,d\) 后如何构造，实际上是先根据 \(b,c\) 铺出形如 XYXYXYXYX 的序列，之后每存在一个 XX 或 YY 就填进去一个 X 或 Y。于是能构造出上面序列的充要条件为 \(|b-c|\le 1\)，还要特判 \(b=c=0\) 的情况。

B XYYYX

设 X 的个数为 \(cnt\)。

• \(cnt\le k\) 时，操作应当是将一些 X 换成 Y。发现形如 XXYXXXYXX 的序列中，改变“贴着” Y 的 X 可以每次获得 \(1\) 的贡献，而填满一个不在边界的 X 连续段能额外获得 \(1\) 的贡献。我们希望能填满的非边界连续段尽量多，只需将边界 X 连续段放在最后，其他的按照长度升序排序，贴边填即可。

• \(cnt>k\) 时，操作应当是将所有 X 换成 Y，再将一些 Y 换成 X，贪心的策略应当正好相反，改变"贴着” X 的 Y 会每次削去 \(1\)，而将一个不在边界的 Y 连续段完全改变会额外削去 1。我们希望被削去的连续段尽量少，而不在边界的连续段是更优秀的，只需将边界 Y 连续段放在最前，其他的按照长度降序排序，贴边删即可（与上面相反，这次有边界从边界删）。

C YY Square

\(n^2\) 的答案不能拆成每个点的贡献，考虑 \(n^2=(n-1)^2+2(n-1)+1\)，加上 \(\sum\) 也是可以维护的，形如 \(\sum n^2=\sum (n-1)^2 +2\sum (n-1)+\sum 1\)。

于是只需要维护一个前缀的 \(\sum n^2\) 以及 \(\sum n\)，分别设成 \(f_{i,j}\) 与 \(g_{i,j}\)。

最基本转移：

\[f_{i-1,j}+f_{i,j-1}\rightarrow f_{i,j} \]

\[g_{i-1,j}+g_{i,j-1}\rightarrow g_{i,j} \]

当 \((i,j)\) 为 Y 且 \((i-1,j)\) 为 Y 时，可以有：

\[f_{i-1,j}+\dbinom{i+j-3}{i-2}\rightarrow f_{i,j} \]

\[g_{i-1,j}+2\times f_{i-1,j}+\dbinom{i+j-3}{i-2}\rightarrow f_{i,j} \]

同理，当 \((i,j)\) 为 Y 且 \((i,j-1)\) 为 Y 时，可以有：

\[f_{i,j-1}+\dbinom{i+j-3}{i-1}\rightarrow f_{i,j} \]

\[g_{i,j-1}+2\times f_{i,j-1}+\dbinom{i+j-3}{i-1}\rightarrow f_{i,j} \]

D YY Garden

咕。

E XXYX Binary Tree

没有 YY 的情况，说明 Y 对应节点是个独立集。

考虑一个 Y 非根节点，对 XY 有 \(1\) 的贡献；一个 Y 非叶子节点，对 YX 有 \(2\) 的贡献。

于是非叶子节点应当有 \(\dfrac{c}{2}\) 个，若 \(c\) 为奇数显然答案不合法，

若根为 x，则 Y 节点有 \(b\) 个，Y 叶子有 \(b-\dfrac{c}{2}\) 个；若根为 Y，则 Y 节点有 \(b+1\) 个，Y 叶子有 \(b+1-\dfrac{c}{2}\) 个。

考虑一个 DP，\(f_{u,k,0/1}\) 表示 \(u\) 子树内有 \(k\) 个叶子节点且 \(u\) 为 X 或 Y 时子树内含有的最多 Y 节点个数。

这样只需要判断理论 Y 节点个数是否不超过理论最大值了。

F XY Ladder LCS

咕。

标签：边界,题解,sum,dbinom,YY,ARC157,节点,rightarrow
From： https://www.cnblogs.com/SoyTony/p/Solution_on_ARC157.html