玩坏第一题

题意:

给出一个01矩阵,求任意交换某几行后其中最大的全1矩阵大小。

思路:

本来完全可以有$O(n^2)$的方法,我却用树状数组"优化"成了$O(n^2logn)$
思路是这样的:求出每个点正左侧有多少1,将这个值放入每一列对应的树状数组内。接下来枚举矩形的长l,枚举矩形的左侧x坐标,然后在树状数组内查找那一列有多少个点右边有l个以上的1,l和答案的乘积就是面积。

平方算法请参考:http://k-xzy.cf/archives/2723

卡坏第二题

题意:

给出n(1<=n<=500)种物品的价值(价值1<=pi<=10000),和m(1<=m<=3e5)个需要达到的价值和(Pmax不超过4e7),求有多少个价值和可以由那些物品构成(每种物品有无限个)。
其中有30分的数据满足1<=n<=10,1<=m<=100,最大价值和Pmax不超过2e5
还有30分满足1<=n<=100,1<=m<=300000,最大价值和Pmax不超过4e7
空间限制64MB

思路:

对于前30分的数据,完全可以用普通背包来做。复杂度为O(nPmax)
但是还有30分是不是也可以用背包呢?
貌似不行,因为空间限制太苛刻,而且时间复杂度过高。
这里介绍一个新的名词:位运算背包。
由于这中背包只需要考虑解的存在性,所以我们可以用每一个二进制位表示这个价值能否达到。利用64位CPU强大的位运算能力,为我们的程序添加1/64的常数。
方法是这样的,虽然有点复杂,但是非常直观:
用一个mask数组元素的每一位连续地表示对应物品的价值是否存在,f数组元素的每一位连续地表示对应价值是否存在。当向f[i]转移时,用mask数组每一个元素与f[i]数组靠后的元素进行按位与(要移动mask数组的每个元素(>>和<<)),如果按位与的结果不为0,说明f[i]可以由之前的某些f转移过来,因此可以将复杂度降为O(nPmax/64)
上代码:

正解是剩余系下的最短路:

裱坏第三题

题意:

AddEdge 最近沉迷日本麻将。
麻将是一个四人游玩的游戏。麻将牌由以下四类牌组成:
万子:一万至九万,我们用 1m~9m 表示。
索子:一索至九索,我们用 1s~9s 表示。
饼子:一饼至九饼,我们用 1p~9p 表示。
以上三种为数牌。
字牌:包括东、南、西、北、白、发、中七种牌,为了方便,我们依次用
1c~7c 表示。
以上每种牌各有四张。
麻将和牌时有 14 张牌,和牌型通常为四面子加一雀头。面子是指顺子(三
张同色且数字连续的数牌,如 1p 2p 3p 或 6m 7m 8m,字牌不能形成顺子)或刻
子(三张相同的牌,如 3s 3s 3s 或 5c 5c 5c),雀头是一对子即两张相同的牌(如
1m 1m 或 7c 7c)。
麻将中还有两种特殊和牌型:
七对子:由七个不同的对子组成(日本麻将不承认“龙七对”手役,即一杠
子加五对子)。
国士无双:由 1m 9m 1s 9s 1p 9p 1c 2c 3c 4c 5c 6c 7c 加上这十三张牌中的任
意一张组成。
每局麻将开始时四名玩家各有 13 张牌,每一轮每名玩家摸一张牌并打出一
张牌。当一副手牌再加上某一张牌构成一个和牌型时,我们称这副手牌听这张牌。
考虑一副未进行吃、碰、杠等鸣牌操作的手牌,判断这副手牌可以听哪些牌。注
意:在此题中,不能再摸起的牌即每种牌的第五张不能算作听的牌。

思路:

枚举
然而考场上我把mahjong打成了majong,狠狠地掉了97分。
为什么不是100分?因为我的算法有一定的问题,但遇上了仁慈的SPJ,在多组数据中,我的代码只错了极少的点。
为什么会错呢?
因为我枚举的策略是:先添牌,固定对子,再看剩下的有没有和牌的可能。在判断和牌的时候,我会先出完所有的对子,再找顺子,但是像4m,4m,4m,4m,5m,6m,6m,6m,7m,7m,8m,8m这种情况程序会剩下几张5m,7m,8m,如果先出顺子才行。
所以必须一下几个策略结合:1.先出对子,2.先从左往右出顺子,3.先从右往左出顺子。这样才可以减少很多出错的可能。
以下是结合3中策略的代码: