做题记录 25.10.14

szt100309 · 2025-10-14 07:31:53 · 个人记录

\blue\odot AT_arc104_d [ARC104D] Multiset Mean

令 1\sim n 减去 x，得到 [1-x,-1],0,[1,n-x] 三个部分，其中 0 的部分数量任意，答案乘以 k+1，要求 [1-x,-1] 和 [1,n-x] 部分总和为 0，即从 [1,x-1] 和 [1,n-x] 中选出若干数使得和相等，答案需要减去 1，因为多算空集

令 f_{i,j} 表示值 1\sim i 中选择若干使得和为 j 的方案数，转移是容易的，容易前缀和优化到 O(n^3k)（显然 i=O(n),j=O(n^2k)）

总时间复杂度 O(n^3k)

代码

参考

\blue\odot AT_arc107_d [ARC107D] Number of Multisets

将数字从小到大排序，每次在末尾加入一个 1 或所有数字除以 2，令 f_{i,j} 表示数字 1\sim i 选择若干使得和为 j 的方案数，转移为 f_{i,j}\gets f_{i-1,j-1},f_{i,j}\gets f_{i,j+j}，按完全背包的顺序进行

时间复杂度 O(n^2)

代码

参考

\purple\odot AT_arc179_d [ARC179D] Portable Gate

先考虑固定起点为 1 的情况

可以将操作转化为带着门移动，放下门单独移动，回到门的位置

显然最优情况下一定以某种 \text{dfs} 序移动

若访问子树 u 时门在 u 的祖先处，则最优情况下不会回到门两次，否则不如把门放到 u 处，因此一定是访问到子树内最深的点后回到门处

令 md_u 表示子树 u 内点到 u 的最大距离，令 mnr_u=2(sz_u-1)-md_u 表示门放置在 u 的祖先时遍历 u 的最小代价，令 mv_{u,0/1} 表示允许移动门，是否强制要求回到 u 时（连同门一起回到 u）的最小代价

显然 mv_{u,1}=\sum_{v\in\text{son}(u)}\min(mv_{v,1}+2,mnr_v+1)

考虑 mv_{u,0} 的转移，显然需要在 mv_{u,1} 的基础上，选择某一 \min(mv_{v,1}+2,mnr_v+1) 替换为 \min(mv_{v,0}+1,mnr_v+1)，因此 mv_{u,0}=mv_{u,1}+\min_{v\in\text{son}(u)}(\min(mv_{v,0}+1,mnr_v+1)-\min(mv_{v,1}+2,mnr_v+1))

单独做一遍为 O(n) 的，使用换根 dp 容易做到总复杂度 O(n)

代码

参考

\purple\odot AT_arc186_d [ARC186D] Polish Mania

序列 a_{1\sim n} 合法当且仅当 \sum a_{1\sim n}=n-1,\;\;a_n=0,\;\; (\forall 1\le i<n,1+\sum a_{1\sim i}>i)，等价于从 (0,1) 出发，每次从 (i-1,s) 走到 (i,s+w_i)，不穿越 y=x 且在 x=y=n 处结束

因此枚举 1\le p<n，计算 w_{1\sim i-1}=a_{1\sim i-1},w_i<a_i 的情况下 w 的合法数量，令 b=w_i，枚举 0\le b<a_i，将 [x\le y][y\le n](S\binom{n-1-x}{n-y}-S\binom{n-x}{n-1-y}\mid x=i,y=1+b+\sum a_{1\sim i-1}（S\binom xy=\binom{x+y}x）计入答案，若在扫描过程中前缀已经不满足以上要求，则退出

显然时间复杂度 O(n)

代码

参考

\purple\odot AT_arc193_c [ARC193C] Grid Coloring 3

时间倒流，转化为第一次选择一个十字删去，之后每次选择一行（列已经被之前删去），一列（同理）或一个十字删去

令 f_{i,j} 表示 i\times j 的网格中可以通过删行列十字而清空的数量

先考虑行，钦定 1\le x\le i 行同色，设容斥系数为 c_x，对于恰好有 k 行同色的情况，有 \sum_{1\le x\le k}\binom kx c_x=1，得到 c_x=(-1)^{x+1}

因此这部分贡献为 \sum_{1\le x\le i}\binom ix (-1)^{x+1} c^x f_{i-x,j}（其中 c^x 表示这 x 行每行颜色任意）

同理列的贡献为 \sum_{1\le y\le j}\binom jy(-1)^{y+1} c^y f_{i,j-y}

然后考虑十字，钦定 x 行 y 列同色，设系数为 c_{x,y}，则 \forall (i,j),\sum_{1\le x\le i}\sum_{1\le y\le j}\binom xi\binom yj c_{x,y}=1，得到 c_{x,y}=(-1)^{x+y}，因此贡献为 \sum_{1\le x\le i}\sum_{1\le y\le j}\binom ix\binom jy(-1)^{x+y}cf_{i-x,j-y}

同理答案为

由于前面两种情况分别包含了十字的情况，因此

容易分步转移做到 O(hw(h+w))

代码

参考