TOAD 19 - Homework Scores

有点线性代数的味道。

Problem

有一个 \(n \times n\) 的矩阵，每个格子内有一个数。你每次可以查询一个子矩阵的权值和，求找出主对角线上点的权值和的最少需要多少次查询。

Solution

可以证明至少要 \(n\) 次查询，所以直接一个一个查询对角线就好了。

其实有个解法完全与线性代数无关 →_→

考虑 \(n\) 个对角线格子的四条边界。易知每条边界都必须被某次查询的边界经过：若某条夹在格子 \(u, v\) 之间边界没有被经过，则表示任意时刻 \(u, v\) 均同时被查询或同时不被查询，也就是说我们至多能确定这两个值的和，而不能确定其中的一个。由于每次查询至多经过 4 条边界，而总共有 \(4n\) 条边界，所以至少要查询 \(n\) 次。