题解：UVA1329 Corporative Network
UVA1329 Corporative Network 题目大意 给定一张无向图，要求支持下面两种操作（初始状态没有边）： I x y：将 y 设为 x 的父节点，边 x -> y 的长度为 ∣x−y∣|x-y|∣x−y∣ 对 100010001000 取模后的值； E x：查询 x 到其根节点的距离。 解题思路 方法一 在本题的数据范围下，基础的模拟+递归可以在不使用任何优化的情况下通
题解：UVA599 The Forrest for the Trees
UVA599 The Forrest for the Trees 题目大意 给定一个森林，分别求其中“树”和“孤立顶点”的个数。下图中，有 222 棵树和 111 个孤立顶点。 解题思路 注意到边的个数 EEE 和顶点的个数 VVV 都已经给出，因此可以求出连通分量的个数，即树和孤立顶点的总数， N=V−EN = V - EN=V−E。其中度数为 000 的所有顶点为孤立顶点，其余为树。 参考代
题解：UVA11991 Easy Problem from Rujia Liu?
UVA11991 Easy Problem from Rujia Liu? 刘汝佳的简单题 题目大意 给定一列数，给出若干次询问，每次询问从左到右第 kkk 个 uuu 的下标。 解题思路 数据范围较大，直接用 O(n2)\mathcal O(n^2)O(n2) 的 ad-hoc 会超时。考虑使用邻接表优化，将复杂度降至 O(n)\mathcal O(n)O(n)。 对每一个数建立一个邻接表，第
题解：Kattis - Weak Vertices
Weak Vertices (weakvertices) 题目大意 给定一张无向图 GGG，找出所有不属于任何一个三元环的顶点。 解题思路 使用邻接矩阵记录图中所有的边，使用邻接表记录每个顶点的“邻居”顶点 某顶点 VVV 在一个三元环上，当且仅当： deg(V)≥2\deg(V) \ge 2deg(V)≥2 （但这一点不用显式判断） ∃(V,V1),(V,V2)∈G⇒(V1,V2)∈G\ex
题解：UVA1197 The Suspects
UVA1197 The Suspects 题目大意 有某种传染性很强的神秘疾病在某校学生中传播。学校里有若干团体，只要有一人是“密接”，那么团体内的其他所有人都是“密接”。一个学生可能属于多个团体。现给出学校内所有团体的成员信息，并已知学生 000 是“密接”，求校内“密接”的个数。 解题思路 可以说是并查集的模板题。每次将一个团体内的同学的所在组合并，最后检查和 000 在一组的同学个数即为答案
大整数运算 BigInteger class 的 Python 实现
本文档为 SJTU《计算导论》课程的个人作业 BigInteger 类 技术报告 综述 模块目的: 实现一个支持任意长度整数的类 BigInteger，提供加、减、乘、整除、幂运算以及若干辅助函数，避免 Python 内置整型在教学场景中不可见的实现细节。 实现语言/文件: Python, 文件 lab3.py。 “BigInteger 类”详述 说明: 用字符串表示大整数的数
题解：UVA11496 Musical Loop
UVA11496 Musical Loop 题目大意 给定一段循环音乐每个音符的音高，询问有多少个音符位于“峰”（相邻音符音高均低于它）或“谷”（相邻音符音高均高于它）。数据保证没有两个相邻音符的音高相同。 解题思路 直接模拟即可。 记录每个音符的音高分别为 a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an。为了模拟出“循环”的效果，赋值 a0=an,an+1
题解：UVA414 Machined Surfaces
UVA414 Machined Surfaces 题目大意 给出一个零件的左右两半，用 X 表示零件，用空格表示空隙。询问如果将左右两边拼合起来后空隙（即空格）的数目。 解题思路 考虑使用 minnminnminn 记录两部分在每行上的最短间隔，即每行上空格的最少数目，并用 tottottot 记录空格的总数。显然两个零件最多可以“相互靠近” minnminnminn 格而不发生重叠。定义行数 N