第一场团队赛：Nordic Collegiate Programming Contest 2019
训练记录--比赛记录

• 数据结构专题（把ppt一页一页粘过来好麻烦啊Ծ‸Ծ）

• 无

• 图论专题

• 无

• 搜索专题

• 无

• 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种牌凑成刻子，如
    有多余，则必须再凑成顺子。