2020/5/4-2020/5/10
团队训练
吕双羽
专题
比赛
吴湛宇
专题
比赛
陶虹宇
专题
比赛
本周推荐
吕双羽
ZJOI 2007：棋盘制作
分类：二分&单调栈
题意：给定一个N*M的01矩阵，求这个矩阵中面积最大的正方形棋盘和矩形棋盘 N,M⇐2000
题解：对于一个大小固定的棋盘只有两种可能：第一个元素为0或者第一个元素为1
那么我们把输入的数据与一个标准的棋盘进行异或
原问题就可以转化为：分别求一个01矩阵中最大的全为0或者全为1的正方形和矩形
吴湛宇
TJOI 2017：可乐
分类：邻接矩阵&倍增
题意：给定一张图，在1号点有一个机器人，每次可以选择走到一个相邻结点，不动或者自爆.问t秒的方案数。
N⇐30,M⇐100,t⇐10^6
题解：根据矩阵乘法的定义，我们惊奇的发现，邻接矩阵的k次幂中的i行j列的元素代表从i经过k步到j的方案数
对于自爆这个行为，我们只需要把每个点连到一个自爆节点上即可
然后写一个矩阵快速幂就OK了
陶虹宇
JSOI 2007：麻将
分类：搜索
题意：考虑一种特殊的麻将，该麻将只有一种花色，但序数从1到n，每种牌可认为有无限多张
和牌定义为有两张组成对子（完全相同的两张牌）,其余3m张牌以3张一组分成m组
每组需要是顺子（序数连续的三张牌）或是刻子（完全相同的三张牌），给出3m+1
张牌，判断其是否听牌（还差一张就可以和牌） 9⇐n⇐400, 4⇐m⇐1000
题解：需要使用合适的枚举顺序，该题先枚举差的牌，先直接枚举对子，即假设将枚举的差的牌
补齐后枚举哪两张牌构成对子，再通过深搜来枚举刻子和顺子，具体来说，先考虑将第i种牌凑成刻子，如
有多余，则必须再凑成顺子。