Warning: session_start(): open(/tmp/sess_39aa45c53b0a02d66b269a578a509bcd, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Writing /data/wiki/data/cache/8/878e000dca5c08fe55e62fff31fad8b7.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
2020-2021:teams:famerwzyyuki:week_1_2020_5_4-2020_5_10

目录

2020/5/4-2020/5/10
- 团队训练
- 吕双羽
  - 专题
  - 比赛
- 吴湛宇
  - 专题
  - 比赛
- 陶虹宇
  - 专题
  - 比赛
- 本周推荐

2020/5/4-2020/5/10

团队训练

第一场团队赛：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种牌凑成刻子，如
  有多余，则必须再凑成顺子。