目录 DFS 优化 BFS 优化 数论 + 错排通项 + 费马小定理 + 逆元 + 欧拉函数&欧拉定理 + 求解欧拉函数 + 扩展欧几里得 + GCD&am...
题目描述：连通图是指任意两个顶点都有路径可互相到达的图。 读入一个无向的连通图，输出最多能删掉多少条边，使这个图仍然连通。 输入格式： 第一行为图的顶点数N（1<=N<=100）和边...
思路 这道题既不是求路程最优值, 也不是求时间最优值, 而是求速度最优值, 乍一看还以为是最优比率生成树, 感觉难度又太高了, 不像。 仔细想想算算, 是一个隐藏着的二分+SPFA。 题目要求...
二分的正确写法 整数二分 int l = 0, r = n; while (l <= r) { int nMid = (l + r) >> 1; if (Judge(x...
【问题描述】 有N个数，随机选择一段区间，如果这段区间的所有数的平均值在[l, r]中则 你比较厉害。求你比较厉害的概率。 【输入格式】 第一行有三个数N, l, r，含义如上描述。 接下来一行...
【问题描述】 一张长度为N的纸带，我们可以从左至右编号为0 - N（纸带最左端标号为 0） 。现在有M次操作，每次将纸带沿着某个位置进行折叠，问所有操作之后纸带 的长度是多少。 【输入格式】...
【题目描述】 给你两个日期，问这两个日期差了多少毫秒。 【输入格式】 两行，每行一个日期，日期格式保证为“YYYY-MM-DD hh:mm:ss”这种形式。第二个日期时间一定比第一个日期时间要大...
【问题描述】 背包是个好东西，希望我也有。 给你一个二维的背包，它的体积是。现在你有一些大小为和的物品，每个物品有自己的价值。你希望往背包里面装一些物品，使得它们的价值和最大，问最大的价值和是多...
题目链接： 加分二叉树 2003年NOIP全国联赛提高组 思路 首先想到搜索， 显然会超时(╮(╯▽╰)╭)， 因为没有什么强有力的剪枝(或者我没有想到)。 考虑 DP(树形DP, 区间划分...
【问题描述】 现在有m个位置可以打 sif，有n + 1个人在排队等着打 sif。现在告诉你前n个人每个人需要多长的时间打 sif，问你第n + 1个人什么时候才能打 sif。（前n个人必须按照...
【问题描述】 栈是一种强大的数据结构，它的一种特殊功能是对数组进行排序。例如，借 助一个栈，依次将数组 1,3,2 按顺序入栈或出栈，可对其从大到小排序： 1 入栈；3 入栈；3 出栈；2 入...
题目链接：数字串 思路 本以为是一道DP题， 结果是一道乱搞题， 关键就是如何想到 优化 。 开始很容易的就想到暴力枚举： 确定一个左边界开始向右扫， 当找到所有 1-m 数字后， 比较答案...
【问题描述】 小 Q 对计算几何有着浓厚的兴趣。他经常对着平面直角坐标系发呆，思考 一些有趣的问题。今天，他想到了一个十分有意思的题目： 首先，小 Q 会在x轴正半轴和y轴正半轴分别挑选n个点...
题目链接：数字串 定义 匹配 ： 一个边的集合，其中任意两条边都没有公共顶点. 最大匹配 ： 一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配. 完美匹配 ： 如果一个图的某个...
题目链接: 关押罪犯 思路 题目中的很多地方都在引导OIer使用 二分+二分图, 比如： 两座监狱, 求最大怨气值的最小值 等等, 这种方法虽然好想, 但是却不好写, 稍微处理不好就会超时。...
题目链接： 单词接龙 2000年NOIP全国联赛提高组 很简单的一道搜索题， 但是我交了3遍才AC， 主要是细节， 一个细节不注意或者一个环节没有考虑到就会WA， 但是联赛的时候只有一次机会，...
题目链接：玛丽卡 思路 第一时间想到的就是枚举每一条边使其堵塞， 然后跑SPFA， 求一个最大值。这样肯定不行(╮(╯▽╰)╭)， 再想一下， 既然是影响最终的最短路， 那就应该在最短路上做...
矩阵乘法的计算法则不再赘述，请自行Google。 提供模板： /* * Copyright © Eliot * Date: 2016-10-26 * Author: Eliot * Descr...
题目链接: 高校排名 又是一道练习建模能力的题目， 算法同样很简单：SPFA最长路， 难在建模(也不算太难). 吐槽一下出题人的语文能力， 看了好几遍才懂题目意思 错误思路 开始的想法是这...
题目链接：宿命的PSS 定义 最小生成树 ：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 完全图 ：若一个图的每一对不...
介绍 对于不完全为0的非负整数a, b, GCD(a, b)表示 a和b 的最大公约数, 必然存在整数对(x, y), 使 ax+by=GCD(a, b). 扩展欧几里得算法就是用来求解 (x...
题目链接：YYB喋血 思路 这种题目就是考的建模能力， 算法并不难， 就一个SPFA。 看完题目， 第一反应就是改变和治愈点相连的边的权值， 但又一想又不对， 治愈点是清空喋血值， 并非改变...
一些无聊的概念之类的废话不再累赘，满满的全是干货！ Tarjan的作用就是求有向图中的强连通分量的个数， 但是在很多题目中不只是数数强连通分量的个数就完事了， Tarjan经常是帮做一些别的事...
NOIP2003 神经网络【拓扑排序、DFS】 描述 神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下面是一个例子： 图中，X1,X2,X3为信息输入渠...
信息学竞赛中，经常会遇到这样一类问题：多次对数轴上的一个区间或是数列中的连续若干个数进行一种相同的处理(查询、修改等)。常规做法是依托于线性表这种数据结构，导致只能针对各个元素逐个进行，效率低下...
素数 思考题：素数密度 给定区间[L,R] (L <= R <= 2147483647 ,R - L <= 1000000)，计算区间中素数个数。 麦森数 形如(2p-1)形...
参加竞赛的时候，将NOIP主要的算法做了一个总结，便有了现在的Class:NOIP_Algo，因为特殊性，类中大部分函数需要重载， 本类只提供参考，如果大家发现错误的话也希望和我联系。 主类：...