Part 2.5.1 负环 当一张图中有负环时，这张图中经过负环的两点间最短路就不存在。因为可以无限次经过这个负环，使代价不断减小。 在三种最短路算法中，SPFA是唯一一种可以处理负环的算法。 由SPFA的过程，每个点最多会被其他点各更新一次，即入队次数不会超过 n n n。 因此如果一个点的入队次数达到了 n + 1 n+1 n+1，就说明图中存在负环。 SPFA判负环的复杂度是 O ( n m ) O(nm) O(nm)。 例题2.5.1 [FAIOJ30086]判断负环 模板题。 例题2.5.2 [FAIOJ30085]虫洞 本题判断的就是起点到起点的距离是否小于0。 ...

【疯狂gcd】的推式子过程 ∑ i = 1 n ∑ j = 1 n g c d ( i , j ) \sum_{i=1}^n\sum_{j=1}^ngcd(i,j) ∑i=1n​∑j=1n​gcd(i,j) = 2 ∑ i = 1 n ∑ j = 1 i g c d ( i , j ) − ∑ 1 = 1 n i =2\sum_{i=1}^n\sum_{j=1}^igcd(i,j)-\sum_{1=1}^ni =2∑i=1n​∑j=1i​gcd(i,j)−∑1=1n​i f ( n ) = ∑ j = 1 n g c d ( n , j ) f(n)=\sum_{j=1}^ngcd...

「NOI大纲」 【X】表示难度系数 2.1 入门级 2.1.1计算机基础与编程环境 【1】计算机的基本构成（CPU、内存、I/O设 备等） 【1】Windows、 Linux等操作系统的基本概念及其常见操作 【1】计算机网络和Internet的基本概念 【1】计算机的历史及其在现代社会中的常见应用 【1】 NOI以及相关活动的历史 【1】进制的基本概念与进制转换、字节与字 【1】程序设计语言以及程序编译和运行的基本概念 【1】使用图形界面新建、复制、删除、移动文件或目录 【1】使用Windows系统下的集成开发环境（例如 Dev C++等） 【1】使用L...

题目描述 幻方是一种很神奇的 N∗N 矩阵：它由数字 构成，且每行、每列及两条对角线上的数字之和都相同。 当 N 为奇数时，我们可以通过下方法构建一个幻方： 首先将 1 写在第一行的中间。 之后，按如下方式从小到大依次填写每个数 若 (K−1)  在第一行但不在最后一列，则将 K 填在最后一行， (K−1)  所在列的右一列； 若 (K−1)  在最后一列但不在第一行，则将 K 填在第一列， (K−1)  所在行的上一行； 若 (K−1)  在第一行最后一列，则将 K 填在 (K−1) 的正下方； 若 (K−1)  既不在第一行，也不在最后一列，如果 ...

例题1 组成平方数 题目描述 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 输入输出描述 输入描述 一个整数n,表示要组成的数字 输出描述 一个正数表示最少需要几个完全平方数才能组成 输入输出样例 输入格式#1： 4 输出格式#1： 1 输入格式#2： 10 输出格式#2： 2 输入格式#3： 19 输出格式#3： 3 输入格式#4： 245 输出格式#4： 2 输入格式#5...