10.23 满帮笔试：AUC 手算、染色连通块与环上最短路边数概率

《面试题目》

编程题 1：按公式计算 AUC

输入是一个二维列表 [打分列表, 真实 label 列表]，label 取 0/1。把样本按预测值从小到大排序，rank = 下标 + 1，则

AUC = (Σ_{i ∈ 正样本} rank_i − M(M+1)/2) / (M·N)，M 为正样本数、N 为负样本数。

输出 float 保留 3 位小数。预测值保证不重复；输入以单行给出，可用 sys.stdin + 循环 + eval 读入。

输入
[[0.5, 0.3, 0.4, 0.7, 0.8, 0.2, 0.1, 0.6], [0, 0, 1, 1, 1, 0, 0, 0, 1]]
输出
0.733

编程题 2：每次染色后输出红色连通块数量

n 行 m 列的正整数矩阵，初始全白。q 次操作，每次把矩阵中所有等于 x 的格子染红（已红的保持红）。每次操作结束后，输出当前矩阵中红色连通块的数量（四连通、极大）。

输入
3 3
1 1 2
2 3 1
3 2 2
2
2 3
输出
3 2

编程题 3：环上两点间最短路被破坏的概率

n 个城市、n 条无向边成环：边 i 连 i 与 i+1（i < n），边 n 连 n 与 1，边 i 的通行时间为 a_i。每条边被破坏的概率相等（1/n）。q 次询问 s_i → e_i，问破坏后通行时间变大的概率，输出最简分数；分子为 0 输出 0/1。

输入
3 3
1 1 1
1 2
2 3
1 3
输出
1/3
1/3
1/3

样例 2 输入 4 2 / 1 2 3 4 / 1 3 / 2 4，输出 1/2 和 0/1（破坏任何一条边时间都不会增加）。

《参考解析》

第一题：完全照公式算，别去想 AUC 的排序意义。把 (score, label) 配对后按 score 升序排序，给每个位置编号 1…n；累加所有 label = 1 的位置编号，减去 M(M+1)/2（这是「正样本全排在最后」时的编号和，等价于扣掉正样本之间的配对），再除以 M*N。输入用 eval(sys.stdin.readline()) 直接把那一行解析成二维列表最省事（题目允许）；如果输入跨多行，先 sys.stdin.read() 再对整段做 eval。输出用 print(f"{auc:.3f}")，注意 Python 的 round 是银行家舍入，格式化输出能避开这类差异。

第二题：倒过来想——「染色」等价于「按操作顺序逐步加入节点」，连通块数量可以用并查集增量维护：初始红色格子数为 0、连通块数为 0；每次把一个白格染红时，连通块数先 +1，然后看它的四个邻居，若邻居已是红色且不属于同一集合，就合并并把连通块数 −1。为了让「每次操作只碰等于 x 的格子」，先按值建 value → [(r,c)] 的哈希表；每个格子只会被染色一次，染过的从表里删掉或打标记，总代价是 O(nm·α)。这题的关键是「已红保持红」让操作变成单向的加点，而不是每次重新 flood fill。

第三题：环上两点只有两条路径，长度分别记为 d1（沿顺时针）和 d2（总长 − d1）。只有「较短的那条路径上恰好只有一条边、且它被破坏」时，通行时间才会变大。更一般地：设最短路径用了 c 条边，若 c = 0（s = e）概率为 0；若两条路径长度相等（d1 = d2）则任何一条边被破坏都不影响最短路，概率为 0；否则只有最短那条路径上的 c 条边被破坏才会变大，概率为 c/n，约分成最简分数输出，分子为 0 时输出 0/1。

求 c 与比较两条路径长度都用前缀和：把 a 复制一份接到后面，pre[i] 为前 i 条边之和，d1 = pre[max(s,e)] - pre[min(s,e)]，d2 = total - d1，边数同理用下标差。每组询问 O(1)，总复杂度 O(n + q)。

备考提示：这三题分别考「照公式实现 + 输入解析」「离线加点的并查集」「环上前缀和 + 分类讨论」。第一题最容易丢分在输入格式上，刷题时顺手练一下 eval / ast.literal_eval 读整行结构体；第二、三题都属于「先想清楚不变量再写代码」，落笔前把连通块计数怎么增减、什么时候概率为 0 这两种边界写在纸上。