Loading...
欧几里得算法与扩展欧几里得算法 注：本节可以独立阅读，但同时也是 《具体数学》(原书第二版) 4.1 整除性 的旁注。 一个基本事实 记 $n = am + b$，其中 $n,m,a,b \in \mathbb Z$，则 $d$ 为 $m,n$ 的公因数当且仅当 $d$ 为 $m,b$ 的公因数。 证明： 充分性： 若 $d \mid m$，$d \mid n$ 则必有 是一个等价结论，所...
为了证明 leetcode 的 hard 题完全不 hard，想要抨击唯 leetcode 是论的思想，昨天给可靠大先辈讲子集枚举DP的时候随便找了道 leetcode 的题，今天随手写一发。 p.s. leetcode 不用 stdin / stdout 是什么傻逼 OJ （暴论） Leetcode 600 不含连续1的非负整数 题面 给定一个正整数n，找出小于或等于n的非负整数中，其二进...
Preface 之前做过很多最短路的题，基本上都使用堆优化的dijkstra，包括建立分层图等高级建图方法，但是一直没有系统地写过dijkstra本身是怎么推导的。今天重点想要形象地写一下以前金牌教练以前教最短路的方法。 单源最短路问题 我们先来简单地描述一下最短路问题：对于一张图 $G$，我们欲求起点 $S$ 到各点地最短距离。 要解决这个问题，我们不妨来先了解一下图论基本方程：对于每个点...
今天起正式进入高三了。为了夯实基础，遂决定每天刷一题，希望别放弃。我记得去年这个时候也干过同样的事情，那今天就文艺复兴一下吧，写归并排序。虽然我是看着去年的代码写的。 归并排序 看下图的 Merge 使用分治的思想 主要分为三个步骤 将数列对半分 递归对子数列排序 合并两个子数列 重点肯定在于如何正确地合并两个子序列。双指针线性扫一遍即可，必定有一个先被扫完，然后直接添加没被扫完的...
310-02-ACOJ-1873-限制数字 题目描述： 一个长度为n的大数，用$S_1,..S_n$表示，其中$S\_i$表示数的第i位，$S_1$是数的最高位。 现告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串$S_{l_1} … S_{r_1}$与$S_{l_2} … S_{r_2}$完全相同。 给定限制条件后，问满足以上所有...
310-01-ACOJ-0864 : 奶牛赛跑 题目大意： 有$n$头奶牛，在一个圆形的赛跑场地里赛跑。所有奶牛同时从起点出发，奶牛的速度都是匀速的，其中第$i$头牛的速度为$v_i$，跑道的长度为单位$1$。当跑得最快那头奶牛跑完$k$圈之后，比赛就结束了。 有时候，跑得快的奶牛可以比跑得慢的奶牛多绕赛场几圈，从而在一些时刻超过慢的奶牛。这就是最令观众激动的套圈事件了。请问在整个比赛过程中...