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

• 数据结构专题

• 无

• 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了