- 博客(291)
- 收藏
- 关注
RSS订阅原创 第五章 贪心算法
在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心算法不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。活动安排问题活动安排问题就是要在所给的活动集合中选出最...
2020-05-16 12:21:59
430
原创 第四章 动态规划
动态规划的基本思想将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解...
2020-05-16 12:21:43
516
原创 第四章 分治法例题
例题（最大子段和问题）给定由n个整数组成的序列(a1, a2, …, an)，最大子段和问题要求该序列形如 的最大值（1≤i≤j≤n），当序列中所有整数均为负整数时，其最大子段和为0。例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和为思路： ① a1, …, an的最大子段和＝a1, …,a 的最大子段和；② a1, …, ...
2020-05-16 12:21:26
641
原创 第三章 递归与分治策略
递归算法程序直接或间接调用自身的编程技巧称为递归算法。递归算法优点它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归算法缺点：递归算法解题的运行效率较低。在递归调用过程中，系统为每一层的返回点、局部变量等开辟了堆栈来存储。递归次数过多容...
2020-05-16 12:21:06
586
原创 第二章 递推算法
递推法的特点一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。递推算法的首要问题是得到相邻的数据项间的关系（即递推关...
2020-05-16 12:20:48
387
原创 第一章 绪论
算法理论的两大论题：1. 算法设计---对于一个问题如何设计一个有效的算法2. 算法分析---如何评价或判断一个算法的优劣算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。算法的五大特性：⑴ 输入：一个算法有零个或多个输入。⑵ 输出：一个算法有一个或多个输出。⑶ 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完...
2020-05-16 12:20:24
219
原创 Educational Codeforces Round 69 (Rated for Div. 2)
A：代码：#include<stdio.h>#include<algorithm>using namespace std;int t,n,a[100005];int main(){ scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) s...
2020-02-06 23:27:09
121
原创 学习总结
近来这段时间，大概的学习步骤是白天通过做数论的题目巩固已经会的数论知识，以及学习一些新的数论知识。都是靠题目带动学习，否则光看效率不太高，看不下去。但这几天做题很懈怠，总是看着别人过了什么题，自己才去跟着。导致给自己心理放松，别人没做的自己看一眼，啊，好难，就放过去啦。正好，今天，老师发了数论1-数论5的题目博客，可以催促自己把前面的题目没做的看一遍补上。晚上除了继续做数论的题目，有时...
2020-02-06 01:35:32
123
原创 Codeforces Round #574 (Div. 2) //A:map用法 //
A（map用法）:代码：#include<bits/stdc++.h>using namespace std;int main(){ ios::sync_with_stdio(false); int n, k, temp; cin >> n >> k; map<int, int> cnt; for(int i=...
2020-02-06 01:22:48
135
原创 Educational Codeforces Round 68 (Rated for Div. 2) //B:数组标记法 C:map用法//
A:题意：黑板上写上1~n的数字，第i次操作删掉第i个数（在剩余里数删），保证剩下的数的个数>=i,否则终止，问第x个数为多少？代码：#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>using namespace std;...
2020-02-05 00:40:42
119
原创 Codeforces Round #573 (Div. 2) //B:二维数组标记法 C:直接模拟//
A:代码：#include<cstdio>#include<iostream>#include<algorithm>using namespace std;int main(){ int n; scanf("%d",&n); n%=4; if(n==1) { printf("0 A"); } else if(n==2...
2020-02-04 23:06:37
125
原创 Codeforces Round #570 (Div. 3)
Codeforces Round #570 (Div. 3)A：题意：求每一位数字之和，然后开始遍历直到能被4整除即可代码：#include<cstdio>#include<iostream>#include<algorithm>using namespace std;int main(){ int a,i,s=0; scan...
2020-02-02 01:04:01
202
原创 学习总结
今天看的，老师把整个寒假要做的数论练习题都放了出来，告诉我们不仅要做题，重要的是锻炼出做题的思维，总结出思考问题的方法规律。感觉老师总结的好正确啊。现在做的数论的题目，很多都是把题目经过转化，数学公式的推算最后转变到我们数论常用的知识点上面来。进而应用数论知识。而且数论真的很锻炼思维，很多题目自己想不到往哪一方面去化，但看到别人的做法就是那样。本来觉得数论涉及到的知识点太多啦，太杂啦，...
2020-01-19 23:01:30
154
原创 欧拉降幂
欧拉降幂公式：对于a^b mod c当b达到10^6时，就无法使用快速幂，需利用欧拉降幂公式求解2^987654321%1000000的值这么大的幂方，是快速幂算法无法求解的，这时我们将使用欧拉降幂算法，它的特点就是能够降低幂方的值且不影响最终结果#include<iostream>#include<cstdio>#include&l...
2020-01-15 20:34:29
668
原创 同余定理
同余定理：a ≡ b (mod m) (即 a%m == b%m)1.若 a-b == m 那么 a%m == b%m2.若a ≡ b (mod m)，则a-b==km同余定理的除法原则：
2020-01-15 19:52:16
293
原创 HDU 2588 GCD（欧拉函数）
Problem DescriptionThe greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.(a,b) can be...
2020-01-15 15:18:03
119
原创 HDU 2824 The Euler function（欧拉函数）
Problem DescriptionThe Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function ha...
2020-01-14 17:21:40
182
原创 欧拉函数
欧拉定理：若n,a为正整数，且n,a互质，即gcd(a,n) = 1，则a^φ(n) ≡ 1 (mod n)其中的φ(n) 即欧拉函数欧拉函数是求小于等于n的数中与n互质的数的数目 （即欧拉函数是求 1到n-1 中 与n互质的数 的数目）如果n是质数，那么1到n-1所有数都是与n互质的，所以φ(n) = n-1如果n是合数，例如φ(8)=4，因为1,3,5,...
2020-01-14 17:13:14
270
原创 学习总结
最近做的数论的老师给的第一套题目主要就是关于数论前面基本知识的。很多题目都是用打表找出题目规律的，像打表筛素数，打表找各种规律等。另外一点要注意的是：要注意时间复杂度。另外还要考虑到题目涉及到的特殊情况，不然又白WA上几遍。...
2019-12-22 21:22:25
97
原创 学习总结
这周发了一套数论练习题，做了一些发现自己前段时间学的数论有所遗忘，所以在做题前先又复习了一遍，边做题边复习前面学过的知识，但自己掌握的还是不深入，就是看到有些题目想不到具体用学过的知识点怎么靠，所以有时一看别人的题解又豁然开朗，所以不愧是短时间内“速成数论”。没有那么强的自悟能力，还是多见题目，多做题目吧，否则真的学过的数论知识不知道如何灵活应用啊。...
2019-12-18 22:49:51
90
原创 一个数的因子、因数的区别
因子就是所有可以整除这个数的数,不包括这个数自身.而因数就是所有可以整除这个数的数,但包括这个数自身.一个数的因子、因数的区别因数包括这个数本身而因子不包括例：15的因子是1,3,5 而因数为1,3,5,15. 20的因子是1,2.4,5 ,10而因数为1,2.4,5 ,10,20完数完数是指此数的所有因子之和等于此数,例如：...
2019-12-17 09:35:53
8549
原创 HDU—2136 Largest prime factor（问你一个数的最大质因子的素数表中的位置）
Problem DescriptionEverybody knows any number can be combined by the prime number. Now, your task is telling me what position of the largest prime factor. The position of prime 2 is 1, prime 3 is 2...
2019-12-17 09:09:58
176
原创 选择排序
输入二行第一行数据个数n第二行n个数据输出从小到大的数据样例输入532 45 67 21 54样例输出21 32 45 54 67代码：#include<iostream>#include<cstring>int r[110];void selectSort(int r[ ],int n){ f...
2019-12-16 20:40:51
91
原创 归并排序
输入第一行为数列的总个数，第二行为待排序的数列输出排序后的数列样例输入810 4 6 3 8 2 5 7样例输出2 3 4 5 6 7 8 10代码：#include<iostream>#include<cstring>int r[110];int r1[110];void Merge(int r[]...
2019-12-16 20:36:49
160
1
原创 快速排序
输入第一行为数列的总个数，第二行为待排序的数列输出排序后的数列样例输入810 4 6 3 8 2 5 7样例输出2 3 4 5 6 7 8 10代码：#include<iostream>#include<cstring>int r[110];int Partition(int r[ ],int f...
2019-12-16 20:32:43
95
原创 插入排序
描述采用插入排序对数据进行从小到大排序输入二行第一行数据个数n第二行：具体数据输出从小到大排序样例输入512 45 32 86 10样例输出10 12 32 45 86代码：#include<iostream>#include<cstdio>int a[110];us...
2019-12-09 20:24:07
149
原创 折半查找
描述使用折半查找找出目标值所在位置。输入一个整数nn个整数要找的目标值输出要找的目标值在序列中的位置，如果找不到，输出"no answer"样例输入样例1输入31 2 32样例2输入41 5 6 84样例输出样例1输出2样例2输出no answer代码：#include<iost...
2019-12-09 20:21:02
453
原创 学习总结
最近几天看的主要看的佩尔方程，扩展欧几里得算法，中国剩余定理和欧拉函数应用的题目，以及一些数论在ACM中常用技巧。这两天看的实在比较急，感觉有点囫囵吞枣，不是十分细致。过错啊，因为实在感觉要看不完啦。我还有莫比乌斯反演没有看那，感觉我要凉凉啦。下周既要看四级，还得把莫比乌斯反演看完，加油，祝我幸福。...
2019-12-08 22:36:19
92
原创 学习总结
这两天一直在看发的数论有关的知识点，的确在学的前期感觉定理很多，很杂，但后面还会反复提及到并应用，所以就又感觉没有想象中的那么多，那么难（可能我现在看到的都是一些对于定理的比较简单的基础应用，哈哈哈，所以才会有这样的感慨）。还有一个关于做必要的总结的事，不总结吧就感觉就过了一遍自己的脑子，但总归不是自己的。但如果见到自己不太会的就整理就有点浪费时间，所以，回来还是要注意一下整理的问题。加油看。...
2019-12-04 22:33:39
86
原创 同余定理
同余定理:若 a-b == m 那么 a%m == b%m例题：http://poj.org/problem?id=2769代码：#include<iostream>#include<cstdio>#include<cstring>#include<stdlib.h>#define mem(a,x) mems...
2019-12-03 20:42:52
128
原创 逆元（数论中的倒数）
满足求余的运算(a + b) % p = (a%p + b%p) %p （对）(a - b) % p = (a%p - b%p) %p （对）(a * b) % p = (a%p * b%p) %p （对）(a / b) % p = (a%p / b%p) %p （错）除法不满足求余取模运算a*x = 1 (mod p)...
2019-12-03 19:17:53
1571
原创 费马小定理
假如p是质数，若p不能整除a，则 a^(p-1) ≡1（mod p），若p能整除a，则a^(p-1) ≡0（mod p）。即：若p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1。费马大定理：当整数n >2时，关于x, y, z的方程 x^n + y^n = z^n 没有正整数解。...
2019-12-03 14:17:33
341
原创 欧拉定理
提示：（mod p）表示这个公式是在求余p的条件下成立互质,若N个整数的最大公因数是1，则称这N个整数互质。例如8,10的最大公因数是2，不是1，因此不是整数互质。7,11,13的最大公因数是1，因此这是整数互质。5和5不互质，因为5和5的公因数有1、5。1和任何数都成倍数关系，但和任何数都互质。欧拉定理：若n,a为正整数，且n,a互质，即gcd(...
2019-12-03 14:12:30
577
原创 扩展欧几里得算法
首先，ax+by = gcd(a, b) 这个公式肯定有解（我们令a,b的最大公因数为gcd,那么我们一定可以找到一组x,y满足此式，这个是欧几里德定理一）所以ax+by = gcd(a, b) * k 也肯定有解 （即在上式基础上把x和y都乘k倍）所以，这个公式我们写作ax+by = d，(gcd(a, b) | d)gcd(a, b)|d，表示d能整除gcd，这个符号在数...
2019-12-03 13:52:51
211
原创 求素数(质数)的方法及时间复杂度的比较
素数，又叫质数，定义是除了1和它本身以外不再有其他的因数时间复杂度O(n)bool prime(int x){//判断x是不是质数，是返回true，不是返回false if(x<=1) return false; for(int i=2;i<x;i++) { if(x%i==0) return fal...
2019-12-03 10:55:24
5176
5
原创 埃氏筛法的具体应用
预处理每个数的所有质因数#include<cstdio>#include<vector>using namespace std;const int N=100000+5;vector<int>prime_factor[N];void init(){ for(int i=2;i<N;i++) { if(pri...
2019-12-03 10:55:13
148
原创 树表的查找技术
二叉排序树（BST）二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：⑴若它的左子树不空，则左子树上所有结点的值均小于根结点的值；⑵若它的右子树不空，则右子树上所有结点的值均大于根结点的值；⑶ 它的左右子树也都是二叉排序树。 二叉排序树...
2019-12-02 20:26:13
210
原创 折半查找判定树
判定树：折半查找的过程可以用二叉树来描述树中的每个结点对应有序表中的一个记录结点的值为该记录在表中的位置通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。判定树的构造方法⑴ 当n=0时，折半查找判定树为空；⑵ 当n＞0时， 折半查找判定树的根结点为mid=(n+1)/2， 根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查...
2019-12-02 20:04:22
8788
原创 HDU 3374 String Problem（KMP中求最小循环节出现的次数+最大最小表示法）
Problem DescriptionGive you a string with length N, you can generate N strings by left shifts. For example let consider the string “SKYLONG”, we can generate seven strings:String RankSKYLONG 1KY...
2019-12-02 19:49:25
285
原创 二分查找(折半查找)
适用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。折半查找的基本思想（mid=(1+n)/2）[ r1 … … … rmid-1 ] rmid [ rmid+1 … … … rn ] 如果k<rmid 如果k>rmid 查找左半区...
2019-12-02 19:47:12
175
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人