T4

核心思想：通过二分答案将问题转化为判定性问题，利用二维前缀和优化判断过程。

步骤如下：

1. 二分中位数：
   中位数的取值范围在矩阵的最小值到最大值之间。通过二分法猜测一个中位数 x，判断是否存在至少一个 $k \times k$ 的子矩阵，其中位数不超过 x 。

2. 转化为01矩阵：
   对于猜测的 ( x )，将原矩阵转换为01矩阵 ( b )：

   • 如果 ( a_{i,j} > x )，则 ( b_{i,j} = 1 )；
   • 否则 ( b_{i,j} = 0 )。

3. 计算二维前缀和：
   对矩阵 ( b ) 计算二维前缀和，以便快速查询任意子矩阵中 ( 1 ) 的个数（即大于 ( x ) 的元素数量）。

4. 判断可行性：
   遍历所有 ( k \times k ) 的子矩阵，检查是否存在至少一个子矩阵，其中 ( 1 ) 的个数 ( \leq \left\lfloor \frac{k^2}{2} \right\rfloor )。如果存在，说明 ( x ) 可能是中位数，尝试更小的值；否则尝试更大的值。

时间复杂度：

• 二分次数为 ( O(\log (\text{max_val})) )。
• 每次检查的时间复杂度为 ( O(n^2) )（计算前缀和和遍历子矩阵）。
• 总复杂度为 ( O(n^2 \log (\text{max_val})) )，可以通过 ( n = 800 ) 的数据。

T6

关键思路

1. 连通块独立性

首先观察到每个连通块是独立的，整个图的方案数是各连通块方案数的乘积。因此我们可以分别处理每个连通块，最后将结果相乘。

2. 必要条件分析

对于一个连通块，要满足每个点恰好一个出边的条件，必须满足：

• 边数等于点数（即每个点贡献一条出边）
• 该连通块必须是一个基环树（即恰好包含一个环的图）

3. 方案数计算

对于满足条件的连通块（边数=点数），有2种可能的方案：

1. 环上的边全部顺时针方向，其他边指向环
2. 环上的边全部逆时针方向，其他边指向环

实现方法

1. 并查集处理连通块

可以使用并查集来统计每个连通块的点数和边数：

• 初始化时每个点的父节点是自己，集合大小为1
• 处理每条边时合并两个端点所在的集合
• 统计每个集合的边数（可以用哈希表记录）

2. 验证条件

对于每个连通块检查：

• 点数 == 边数 如果不满足，则整个方案数为0

3. 计算最终答案

如果所有连通块都满足条件，则总方案数为2^连通块个数（每个连通块有2种选择）