A. Triangle
给你一个两直角边长为 \(a\) 和 \(b\) 的直角三角形，问能不能把它放在平面直角坐标系中，使得每个顶点对应的坐标为均整数，且三边均不与坐标轴平行。\(a,b \leq 1000\)。1s / 250M。
不妨将直角顶点固定在原点，设出另外两个点坐标，此时总共有四个变量。利用勾股定理可以得到两个方程，利用两条直线垂直这个条件可以再得到一个方程，总共三个方程。枚举其中一个变量，进而解出其它变量，直接判断即可。
B. Long Path
有一个长为 \(n+1\) 的迷宫，初始时你在房间 \(1\)。对于一个房间 \(i\)，如果这是第奇数次到达此房间（包括现在一次），则走到房间 \(p_i\)，否则走到房间 \(i + 1\)。问走到房间 \(n+1\) 所需要的步数。\(n \leq {10}^3\)，\(p_i \leq i\)。1s / 250M。
题解难以表述，还是看讲解吧。
C. Curious Array
给你一个长度为 \(n\) 的序列，有 \(m\) 次操作，每次操作给定参数 \(l, r, k\)，操作形如对于所有的 \(i \in [l, r]\)，\(a_i \gets a_i + {i - l + k \choose k}\)。问 \(m\) 次操作后的最终序列。\(n,m \leq {10^5}\)，\(k \leq 100\)。1s / 256M。
每次操作相当于给原序列加上一个序列。不难发现，加上的那个序列相当于杨辉三角上的一条斜线。同时，有一个非常好的性质，如果你对这个序列进行差分，那么形成的新序列是原序列在杨辉三角中向上移动一格的序列。那么 \(k\) 阶差分之后就变成了单点修改了。
需要注意的是，这样直接做在 \(k\) 阶差分的序列上最后会多出一堆值。事实上，每次差分时最后一个值不下放即可。容易做到时间复杂度 \(O(nk + mk)\)。
D. Largest Submatrix 3
给你一个 \(n \times m\) 的矩阵，求其中最大的满足内部不存在两个位置数值相等的子矩阵的大小。\(n,m \leq 400\)。3s / 250M。
考虑 DP。设 \(f_{l, r, k}\) 表示考虑以第 \(l\) 列为左边界，第 \(r\) 列为右边界，第 \(k\) 行为下边界的子矩阵，它的上边界最靠上是多少。显然，\(f_{l, r, k}\) 可以从 \(f_{l, r, k-1},f_{l, r-1, k}\) 和 \(f_{l + 1, r, k}\) 转移过来。但这没考虑 \(a_{k,l}\) 和第 \(r\) 列以及 \(a_{k, r}\) 和第 \(l\) 列是否有相同的数。直接维护每个数最后一次出现的位置即可。时间复杂度 \(O(n^3)\)。