66 给定一个二维列表形式的输入,其中包含打分列表和真实标签列表,请实现AUC计算,输出保留3位小数。考察候选人能否正确理解AUC的秩公式,处理非标准输入格式,并在预测值不重复的前提下完成排序、正负样本计数和浮点格式化。 查看学习思路
67 给定n行m列正整数矩阵,初始全白,q次操作每次将所有等于x的格子染红,每次操作后输出红色四连通块数量。请设计并实现算法。考察候选人能否将染色过程转化为并查集动态合并问题,利用值到坐标的哈希表避免重复扫描,并在每次染色后正确维护全局连通块数量。 查看学习思路
68 n个城市n条边构成环,每条边等概率被破坏,q次询问s到e在破坏后通行时间变大的概率,输出最简分数。请给出算法。考察候选人能否把环上两点间路径拆成两条,利用前缀和比较两条路径长度,并统计“最短路径上边被破坏会导致时间变大”的概率,最后输出最简分数。 查看学习思路