Day 3

在被昨天晚上的莫比乌斯反演刷新了世界观后，今天的咱做好了爆零的万全准备

然后果然就爆零了【趴 咱还是乖乖地抄题解吧

T1 Matrix

可能这两天DP题见太多了现在看啥都像DP了233333读完题的第一反应觉得可以选取n行，令m为这若干行的并中最长的连续的1的个数，使得n*m，然后对这个东西套上DP就……挂掉了。仔细一想这破玩意似乎是有后效性的，转移也是十分难做，于是这题就愉快地爆零了，咱甚至连部分分都拿不到wsl

下午看完题解和czh dalao的思路之后弄出了个很奇怪的算法。我们用扫描线扫过每个可能的右端点并将其固定，寻找所有可能的左端点并求最大值即可。

那么，我们如何知道对于每个左端点，有多少个连续的1呢？我们知道如果固定了右端点，那么只有当一段1从我们确定右端点的左侧连续的到右侧，这段1才能被计算。那么，我们可以将每行连续的1扒下来变成区间，然后按左端点和右端点为关键字分别排一次序。如果我们的扫描线碰到了一个区间的左端点，那么把它加入树状数组，如果碰到了右端点则将其从树状数组中减掉即可。

T2 Present

NOIP 2018 Day 1 T2 货币系统

显然这题是个完全装满背包，然而这个数据范围告诉我们这道题并不简单。写背包的话时间复杂度为O(na_{max})，在这题的数据范围下是一定要T的，并且用上背包还要顶着巨大的空间复杂度，这意味着我们需要寻找更加可行的方法。

我们注意到，假设所有物品中体积最小为p_{min}，那么如果有一件物品的件数超过p_{min}，我们就可以用p_{min}对应的物品取代原来的那个物品，这样我们就可以先用p_{min}尽可能填充背包，剩余部分再去DP，这样可以大大缩小DP的范围。

然而事实上我们完全不需要DP。考虑用若干件物品组成a，使得a \equiv a_i \pmod{p_{min}}，如果a \leq a_{i}，那么我们一定可以用p_{min}将a比a_{i}小的部分补齐，这样就能够组成a_{i}。

因此，我们只需要找最小的a \equiv a_i \pmod{p_{min}}，判断a是否不大于a_{i}即可。我们可以将其看做一个最短路，其中s向(s + p_{i}) \mod {p_{min}}连边，边权为p_{i},跑SPFA即可。

T3 Mahjong

@xbz

教练，我想打雀魂

其实就是一个大模拟。我们枚举所有牌并检查是否可以听该张牌即可。七对子和国士无双可以直接判掉，然后我们找一个雀头并检查是否有4个面子即可。不过注意等效的情况不应重复判断，否则会导致T的非常惨。