集训队作业 2021

2021 是 ACM 题，反正做做看吧。

感谢 M_sea。

由于笔者暂时没有上紫名，所以预计 11 月份修复本文所有的代码链接。

PART I

我还是不知道。

A

发现好多不是我能做的……

[ICPC2014 WF] Baggage

Portal.

我们是否能将 $n$ 较大的转化为 $n$ 较小的？观察样例，$n=5$ 时整体左移了两格，发现只需要利用左四右四个数就可以做成左边空两格，将 $n\le 7$ 的打表打出解即可（$n=3$ 特殊，只左移两格是无解的）。代码。

跳过 *2

PART III

Portal.

A

满天星斗，广袤宇宙，不如向前走。

[CERC2015] Cow Confinement

Portal.

一头牛的话显然是 DP（$f_{i,j}=f_{i+1,j}+f_{i,j+1}-f_{i+1,j+1}$），那么考虑用扫描线从右向左扫，线段树维护当前每个点的 DP 值。如果扫到了一个右区间，那么从上线到下一条下线都要被加在上线上的一个格子，并且线内数据清零。扫到左线线内数据清零，并把原来线外的东西加回来，最后再把右下角算重的部分减去就行。代码。