已知了最小费用流和最小割的性质，写写最大流的各种变体。 READ MORE →
图论：最小费用流与Bellman-Ford算法
最小传输费用问题
稀疏矩阵转置之快速转置法
数据结构作业题目 = =
前情回顾：矩阵转置-简单代码
一个简单的约瑟夫环代码
动态链表的课后作业。直接上代码：
READ MORE →
矩阵转置-简单代码
利用数组对两个矩阵进行转置。附上简单代码：
READ MORE →
区间调度问题
题目描述：
有n项工作，每项工作分别在si时间开始，ti时间结束。对于每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与，即参与工作的时间段不能有重叠(即使开始的瞬间和结束的瞬间重叠也是不允许的)。
你的目标是参与尽可能多的工作，那么你最多能参与多少项工作呢？
限制条件：
1<=n<=100000
1<=si<=ti,=10^9
这个问题首先想到的就是贪心算法。但设计算法时容易出现错误。
比较容易想到的算法如：
- 在可选工作中，每次选取最先开始的工作
- 在可选工作中，每次选取用时最短的工作
- 在可选工作中，每次选取与最少可选工作有重叠的工作
- 在可选工作中，每次选取结束时间最早的工作
而很显然，前三项算法都不具有普适性（例如：一项开头早，持续时间长的工作和两项开头晚的工作）。
关于最后一种算法的解释：
结束时间早，对应的可选工作就越多。当然也可以用归纳法来证明。
代码实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <stdio.h> #include <tchar.h> #include <queue> using namespace std; const int N = 5; int s[N]={1,2,4,6,8}; int t[N]={3,5,7,9,10}; int solve() { pair<int, int> itv[N]; for(int i = 0; i < N; i ++) { itv[i].first = s[i]; itv[i].second = t[i]; } sort(itv, itv + N); int count = 0; int t = 0; for(int i = 0; i < N; i ++) { if(t < itv[i].first) { count ++; t = itv[i].second; } } return count; } int main() { cout << solve() << endl; return 0; } |
栈
栈是支持push和pop的数据结构。
push是在栈的顶端放入一组数据；pop是在栈的顶端取出一组数据。
Last in first out(LIFO):最后进入栈的一组数据会被最先取出.
样例：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include #include using namespace std; int main() { stack s;//声明int类型数据存储的栈 s.push(1);//『』→『1』 s.push(2);//『1』→『1,2』 s.push(3);//『1,2』→『1,2,3』 printf("%dn",s.top());//3 s.pop();//栈顶移除3，下同 printf("%dn",s.top()); s.pop(); printf("%dn",s.pop()); s.pop();//『1』→『』 return 0; } |
返回栈顶元素：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// test_stack.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <stack> #include <vector> #include <deque> #include <iostream> using namespace std; int _tmain(int argc, _TCHAR* argv[]) { stack<int> mystack; mystack.push(10); mystack.push(20); mystack.top()-=5; cout << "mystack.top() is now " << mystack.top() << endl; return 0; } |
快速幂取余算法例题
问题描述:
求 B ^ P % M = ?
代码实现:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <cstdio> using namespace std; int main() { freopen("input.txt","r",stdin); int B,P,M; while (~scanf("%d%d%d",&B,&P,&M)) { int ans = 1; B = B % M; while (P > 0) { if (P%2) ans = ans * B % M; P /= 2; B = (B*B) % M; } printf("%dn",ans); } } |
辗转相除法
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式。
例题：
ACM常用算法
转载自知乎，原作者：王晓。原文链接：http://www.zhihu.com/question/19719698/answer/13045301
- 感谢邀请。
- 网络上流传的答案有很多，估计提问者也曾经去网上搜过。所以根据自己微薄的经验提点看法。
- 我ACM初期是训练编码能力，以水题为主（就是没有任何算法，自己靠动脑筋能够实现的），这种题目特点是麻烦，但是不难，30-50道题目就可以了。
- 然后可以接触一下基础的算法，我感觉搜索方向的比较不错，可以解决很多问题，深搜，广搜，然后各种剪枝能力的锻炼。
- 搜索感觉不错了就可以去看看贪心，图论，和动态规划方向的了。图论有最短路径，最小生成树，网络流，拓扑排序等等很多，动态规划先去书上看经典例子，最长公共子序列等。各种变形的题目。
- 数学是ACM中极具杀伤力的武器，我一向很羡慕数学好的队友，精力有限自己数学方面的算法只能说入门。这方面经典的数论，组合数学方面的比较多，计算几何是很重要的，经典模型要熟悉，最近点对，二维三维，凸包以及各种应用。
- 数据结构方面的就比较多了，基础的堆，栈，队列，并查集，二叉查找树，红黑树，trie树，hash表等等。
- 用C++参赛的话STL要熟悉，有时候很有帮助，里面的queue,list,map,stack等。
- ACM到后来算法就成了工具，不断的靠自己意淫一个新的解法来解决问题是最开心的事情了。我们学校ACM一直是一届带一届的，老师只提供经济上的援助,上面的内容是我在大三当队长时教给大一的新队员的入门内容，再深的就靠每个人自己发掘了。