ACM笔记初探ACMGCD / LCM 求法快速幂循环节贪心算法常见模型Havel Hakimi 定理快速排序递推问题简单递推条件递推Catalan数动态规划DP经典1:数塔问题DP经典2:最长递增子序列问题DP经典3:最长公共字符串子序列问题背包问题01背包完全背包多重背包二维背包搜索BFS二分查找三分查找DFS优化筛选法求N以内所有素数筛选法+统计 求N以内素数的个数并查集与最小生成树Kruskal算法Prim算法计算几何拓扑排序博弈最短路 - Dijkstra二分图-匈牙利算法复习心得
int gcd(int a,int b)
{
return a % b == 0 ? b : gcd(a % b, b);
}
求LCD的方法: LCM = a * b / gcd(a, b)
幂次拆分,提升效率。
非递归形式实现:
xxxxxxxxxx
int qsm(int a, int n ) {
int ans = 1;
while(n) {
if (n&1) ans *= a;
a *= a;
n >>= 1;
}
return ans;
}
抽屉原理:总共n个抽屉,往里面随便放n+1个物体,则必然存在一个抽屉,它包含两个物体
一般看到 mod 就要想到用循环节做。
问题1:FatMouse Trade 问题,解法:求性价比,降序排列,从性价比最高的开始买,钱不够时全部按比例折算购买。(hdu FatMouse's Trade)
问题2:最长事件序列问题,解法:最长的事件序列必然包含最早结束的事件序列。(hdu 今年暑假不Ac)
问题3:田忌赛马问题,策略:
A的慢马比B的慢马慢:让他和B的快马比赛,输的代价最小!
A的慢马比B的慢马快:让他和B的慢马比赛,赢的代价最小!
A的慢马和B的慢马一样快:
来源: https://blog.csdn.net/liangbopirates/article/details/10035865
问题3:求图的连通性,给出连通性关系矩阵。(poj 1659)
Havel-Hakimi算法的依据:给出G,G是一个递减序列:
并且G是连通图,那么当且仅当递减序列G alt中的数是非负整数且G alt 也连通。G alt 序列是递减的,并且从第一个数 S1 开始的连续 S1 个数都减少 1:
根据 Havel 定理,如果 G 连通,那么不断向前递推,必然能得到一个全部是 0 的序列。否则 G 不能连通。
解法:
x
typedef struct {
int index;
int weight;
}Point;
void selection_sort(Point* a, int start, int end) {/*排序,省略*/}
int main()
{
int count;
Point map[20];
scanf("%d", &count);
while(count--){
int matrix[20][20]={0};
int pcount;
scanf("%d", &pcount);
for(int i=0; i<pcount; i++) {
map[i].index = i;
scanf("%d", &map[i].weight);
}
int flag = 1;
//--核心代码--
for(int i=0; i<pcount; i++) {
selection_sort(map, i, pcount);
if(map[pcount-1].weight<0){
//降序排列后,如果最后一个数都小于0,则图不能连通
flag = 0;
break;
}
if(map[i].weight == 0){
//降序排列后,如果第一个数是0,则序列全为0,图连通
break;
} else {
//如果不是结束的情况,则从第i个数开始,与向后i个数做点的连接(假设能连通)
int j = i+1;
while(map[i].weight > 0){
map[i].weight -= 1;
map[j].weight -= 1;
matrix[map[i].index][map[j].index] = 1;
matrix[map[j].index][map[i].index] = 1;
j++;
}
}
}
//--核心代码结束--
if(flag == 1){
printf("YES\n");
for(int i=0; i<pcount; i++) {
for(int j=0; j<pcount; j++) {
printf("%d ",matrix[i][j]);
}
printf("\n");
}
} else {
printf("NO\n");
}
if(count!=0) {
printf("\n");
}
}
}
后来我发现用选择排序效率低导致超时,因此使用快速排序,成功Ac,快速排序如下:
直接用#include <algorithm>
的 sort()
最好。
xxxxxxxxxx
//降序的快速排序,参数左右都包含
void quick_sort(int s[], int l, int r)
{
if (l < r)
{
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] <= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] > x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i + 1, r);
}
}
求Fibonacci数列的第n项:应使用递推 O (n) 而不是递归 O (2^n)
求n条直线能把平面分成多少部分:F(n) = F(n-1) + n
求n条折现能把平面分成多少部分:F(n) = F(n-1) + 4(n-1) + 1 (新增一条折线增加四个点,增加点数+1个段数)(HDUOJ 2045)
Children's Queue 问题:女生必须两个以上连着排在一起,求n个人有几种可能的排法?
Lele的RPG难题:有RPG三种颜色,填在一行中,每一格颜色不同且首位颜色不同,求n个格子有几种可能的排法?
思路:以 前面合法 + 前面不合法 为分析基础,得出递推公式:
思路解释:第n种情况由两种类型组成:
大兔生小兔问题:F(n) = F(n-1) + F(n-2)
骨牌拼接问题:有2x1,2x2两种骨牌,铺2xn的房间,如果最后一块放2x1,只有一种方法,而当最后一块放2x2则有两种方法(横着的两块2x1,或者一块2x2),所以F(n) = F(n-1) + 2 x F(n-2)
前几项Catalan数:1 2 5 14 42 132 429 ... ...
前几项Catalan数:1 2 5 14 42 132 429 ... ...
Catalan数 模板题1: HDUOJ 1134 一圈上的点连线,线不相交(划分子问题)
xxxxxxxxxx
typedef long long ll;
int main(){
ll c[100] ={0};
c[0] = 1;
int a;
for(int i=1; i<100; i ++){
for(int j=0; j<i; j++){
c[i] += (c[j] * c[i-j-1]);
}
}
while(scanf("%d", &a), a!=-1){
printf("%lld\n", c[a]);
}
}
注意:上面的代码不能 Ac,因为后面数字太大,即便是 long long都放不下。建议用 Java bigInteger类实现。
Catalan数 模板题2: HDUOJ 2067 只允许下三角行走方格的最短路线数(也可用Dp)
其他题目
加括号的方式
N行N列网格路线(只允许下三角行走)
N个节点的二叉树的形态种类
HDOJ 1133 Buy the Ticket
相关练习 1023 1130 1131 1134 1133 1267 2067**
DP问题适用的条件:
1.重叠子问题
2.无后效性
3.最佳子结构
问题描述:有一个数塔,每个节点有一个权值,怎么走路线长度最大?
分析:贪心算法会导致短视,应当采用DP,自顶向下分析,自底向上计算,从已知最优解推未知最优解。
xxxxxxxxxx
int main(){
int count, height;
int num[N][N];
int dp[N][N];
scanf("%d", &count);
while(count--){
//input
scanf("%d", &height);
for(int i=0; i<height; i++){
for(int j=0; j<i+1; j++){
scanf("%d", &num[i][j]);
}
}
//dp init
for(int i=0; i<height; i++){
dp[height-1][i] = num[height-1][i];
}
//dp begin
if(height == 1){
printf("%d\n", num[0][0]);
continue;
}
for(int i=height-2; i>=0; i--){
for(int j=0; j<=i; j++){
int tmpmax;
int lchild, rchild;
lchild = dp[i+1][j], rchild = dp[i+1][j+1];
tmpmax = lchild>rchild? lchild: rchild;
dp[i][j] = tmpmax + num[i][j];
}
}
printf("%d\n", dp[0][0]);
}
return 0;
}
HDUOJ 免费披萨 作为例题参考:
问题描述:有一个一维坐标0~10,Gameboy在坐标5,每单位时间只能左右移动一格或者不动。输入的数据是披萨出现的时间点和位置,问Gameboy最多能抢到多少披萨?
分析:输入的数据可以转换成 时间 + 位置 的数塔,而GameBoy的移动策略则正好成为状态转移方程的一部分(数塔层之间的关联)。因此这个问题本质上就是DP模板。
xxxxxxxxxx
int main(){
int a;
int data[N][11];
int dp[N][11];
while(scanf("%d", &a), a!=0){
memset(data, 0, sizeof(data));
memset(dp, 0, sizeof(dp));
int maxtime=1;
for(int i=0; i<a; i++){
int time, pos;
scanf("%d%d", &pos, &time);
maxtime = max(time, maxtime);
data[time][pos] ++;
}
for(int i=maxtime; i>=0; i--){
for(int j=0; j<=10; j++){
if(j==0){dp[i][j] = data[i][j] + max(dp[i+1][j],dp[i+1][j+1]);}
else if(j<10){dp[i][j] = data[i][j] + max(dp[i+1][j], max(dp[i+1][j-1], dp[i+1][j+1]));}
else {dp[i][j] = data[i][j] + max(dp[i+1][j-1],dp[i+1][j]);}
}
}
printf("%d\n", dp[0][5]);
}
return 0;
}
问题描述:给定一个数组,求数组最长递增子序列的所有序列元素的和。
分析:求n个元素的最长子序列之和,可以化为求n-1个中最长子序列之和加上某个元素,并可以继续向小规模问题转化。求1个元素的最长子序列之和是最小的子问题。方法仍然是自顶向下分析,自底向上递推。
xxxxxxxxxx
int main(){
int count;
int data[N];
int dp[N];
while(scanf("%d", &count), count != 0){
for(int i=0; i<count; i++){
scanf("%d", &data[i]);
dp[i] = data[i];
}
//dp start
int m = 0;
for(int i=0; i<count; i++){
for(int j=0; j<i; j++){
if(data[j]<data[i] && dp[j]+data[i]>dp[i]){
dp[i] = dp[j] + data[i];
}
}
if(dp[i]>m){
m = dp[i];
}
}
printf("%d\n", m);
}
return 0;
}
问题描述:给出老鼠速度和质量,要求找出最长序列,要求老鼠速度递增但质量递减,并给出老鼠ID。
分析:本质是最长递增子序列,但要求回溯路径。
xxxxxxxxxx
using namespace std;
typedef struct {
int s,w,index;
} mice;
int comp(mice a, mice b){
return a.w < b.w;
return a.s > b.s;
}
int main(){
mice mouse[N];
int dp[N], pre[N], res[N];
int a, b, ind=1;
pre[0] = -1;
while(scanf("%d%d", &a, &b) && a != 0 && b != 0){
mouse[ind].w = a;
mouse[ind].s = b;
mouse[ind].index = ind;
dp[ind] = 1;
pre[ind] = 0;
ind ++;
}
sort(mouse+1, mouse+1+ind, comp);
//Dp progress
int maxlen = 0;
int maxend = 0;
for(int i=1; i<ind+1; i++){
for(int j=1; j<i; j++){
if(mouse[j].w < mouse[i].w && mouse[j].s > mouse[i].s && dp[j] + 1 > dp[i]){
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if(dp[i] > maxlen){
maxlen = dp[i];
maxend = i;
}
}
//Dp backtrace
int t=maxend;
int i=0;
while(t != 0){
res[i++] = t;
t = pre[t];
}
printf("%d\n", i);
while(i>0){
i--;
printf("%d\n", mouse[res[i]].index);
}
return 0;
}
问题描述:给定两个字符串,求最长公共字符串子序列。
分析:状态转移方程如下:
xxxxxxxxxx
int max(int a, int b){
return a > b? a: b;
}
int main(){
char str1[N], str2[N];
int a, b;
while(a = scanf("%s", str1), b = scanf("%s", str2), a != EOF && b != EOF){
int len1 = strlen(str1);
int len2 = strlen(str2);
int dp[N][N];
for(int i=0; i<=len1; i++){
dp[0][i] = 0;
}
for(int i=0; i<=len2; i++){
dp[i][0] = 0;
}
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
char c1 = str1[i-1];
char c2 = str2[j-1];
if(c1 == c2){
dp[i][j] = dp[i-1][j-1]+1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
printf("%d\n", dp[len1][len2]);
}
return 0;
}
有一个容量为V的背包和若干个物品,在一定限制条件下,最多能放多少物品?
每种物品有且仅有一个,可以选择买或者不买。
状态转移方程:
式中,F ( i , v ) 表示前 i 件物品装入容量为 v 的背包的价值。c( i ) 表示费用,w ( i ) 表示价值。
01样板代码:
注意要从 j 要从0开始,要考虑 0 背包大小。
xxxxxxxxxx
int main(){
int dp[itemNumber][capacity];
int cost[itemNumber], value[itemNumber];
memset(dp, 0);
//input
//... ... ...
//end input
for(int i=1; i<=itemNumber; i++){
for(int j=0; j<capacity; j++){
if(j < cost[i]){
//cant load !
dp[i][j] = dp[i-1][j];
} else {
//can load, choose: 1.buy 2.dont buy
dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i]] + value[i]);
}
}
}
}
01背包优化代码,不容易理解但使用推荐这个:
xxxxxxxxxx
for(int i=1; i<=number; i++){
for(int j=capacity; j>=volume[i]; j--){
dp[j] = max(dp[j], dp[j-volume[i]]+value[i]);
}
}
一个物品可以取无数个,此外和01背包一样。
xxxxxxxxxx
int main(){
int dp[itemNumber][capacity];
int cost[itemNumber], value[itemNumber];
memset(dp, 0);
//input
//... ... ...
//end input
for(int i=1; i<itemNumber; i++){
for(int j=0; j<capacity; j++){
for(int k=1; k*cost[i]<capacity ;k++){
dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*cost[i]]+value[i]);
}
}
}
}
优化代码,建议使用这个:
xxxxxxxxxx
for(int i=1; i<itemNumber; i++){
for(int j=cost[i]; j<=capacity; j++){
dp[j] = max(dp[j], dp[j-cost[i]]+value[i]);
}
}
一个物品可以买特定的数量。一种方法是逐个将堆叠的物品转化为独立的数量为1的物品,从而变为01背包;优化的方法是将堆叠物品用2的倍数分割。
以下样板代码,将情况分为多重背包 + 01背包。
xxxxxxxxxx
//dp
for(int i=0; i<type; i++){
if(stock[i] * cost[i] >= capacity){
//Comp DP, because
for(int j=cost[i]; j<=capacity; j++){
dp[j] = max(dp[j], dp[j-cost[i]]+value[i]);
}
} else {
//One Zero DP Transform
int k = 1;
int _num = stock[i];
//item seperation
while(k < _num){
for(int j=capacity; j>=k*cost[i]; j--){
dp[j] = max(dp[j], dp[j-k*cost[i]]+k*value[i]);
}
_num -= k;
k *= 2;
}
//One Zero DP for rest items
for(int j=money; j>=_num*cost[i]; j--){
dp[j] = max(dp[j], dp[j-_num*cost[i]]+_num*value[i]);
}
}
}
物品的限制有两种,如背包的承重,背包的容量两类限制。
状态转移方程变为三维:
BFS是基于队列的。下面的代码是二叉树的层次遍历:
xxxxxxxxxx
Status LevelFristTraverse(BTree T){
if(T == null){return ERROR;}
queue<int> Q;
Q.push(T);
while(queue.empty() == false){
BTree tmp = Q.front();
printf("%d", tmp.data);
Q.pop();
Q.push(T.lchild);
Q.push(T.rchild);
}
return True;
}
前提是单调性。
xxxxxxxxxx
//Recursive B-Search.
//assume arr[] is ascend.
int binarySearch(int tgt, int arr[], int left, int right){
if(left >= right){return -1;}
int pos = (left+right)/2
if(arr[pos] - tgt == 0){
return (left+right)/2;
} else if (tgt < arr[pos]) {
return binarySearch(tgt, arr, left, (left+right)/2);
} else {
return binarySearch(tgt, arr, (left+right)/2, right);
}
}
xxxxxxxxxx
//B-Search using WHILE.
//assume arr[] is ascend.
int binarySearch2(int tgt, int arr[], int left, int right){
while(right - left != 0){
int pos = (right + left)/2;
if(arr[pos] == tgt){return (left + right) / 2;}
else if(arr[pos] > tgt){left = pos;}
else {right = pos;}
}
return -1;
}
前提是求导一次后符合单调性。
xxxxxxxxxx
double solve(){
// solve value of a function ...
}
double trinarySearch(int arr[], int left, int right, int eps){
while(right-left > eps){
int k = (right - left)/3;
int lmid = l + k;
int rmid = r - k;
if(solve(lmid) > solve(rmid)){
right = lmid;
} else {
left = rmid;
}
}
return left;
}
深度优先搜索是基于栈的。
xxxxxxxxxx
int allPrime(int N){
int a[MAX_N];
for(int i=1; i<=N; i++){
a[i] = 1;
}
for(int i=2; i<=sqrt(N); i++){
if(a[i] == 1){
//下面可以这样写,是因为j<i*i的部分一定在之前的循环中判断过了
for(int j=i*i; j<=N; j+=i){
a[j] = 0;
}
}
}
a[1] = 1;
for(int i=1; i<=N; i++){
if(a[i] == 1){
printf("%d\n", i);
}
}
}
From | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
Master | 1 | 1 | 3 | 3 | 3 | 6 | 7 | 7 | 7 | 7 |
每个元素都用其所属集合中最小的元素来标记。
xxxxxxxxxx
//查找元素x的最终所属集合
int findMaster(int bin[], int x){
while(x != bin[x]){
x = bin[x];
}
return x;
}
//查找元素x的最终所属集合的树深度压缩法,减少时间复杂度
int findMasterBetter(int bin[], int x){
if(bin[x] == x){
return x;
} else {
int tmp = findMasterBetter(bin[x]);
bin[x] = tmp;
return tmp;
}
}
//合并x所在集合与y所在集合
int merge(int bin[], int from, int to){
int fromMaster = findMaster(bin, from);
int toMaster = findMaster(bin, to);
if(fromMaster < toMaster){
bin[toMaster] = fromMaster;
} else {
bin[fromMaster] = toMaster;
}
}
利用并查集实现。
先把所有边从小到大排序,依次选择从小到大的边,如果边的两个顶点不在一个集合中,则合并两个集合并作记录,否则放弃选择。按上述步骤得到的即为最小生成树。
增加一个方法,判断是否属于同一个集合:
xxxxxxxxxx
int isSame(int a, int b){
if (findMaster(a) == findMaster(b)){
return 1;
}
return 0;
}
因为有count个点,所以最少需要c-1条路。每个循环中,先在邻接矩阵中找到不在同一集合中的最小距离的两个点,进行合并。
xxxxxxxxxx
//kruskal
int sum = 0;
for(int p=0; p<count-1; p++){
int min = 200;
int xpos = -1, ypos = -1;
for(int i=1; i<=count; i++){
for(int j=1; j<=count; j++){
if(map[i][j] < min && !isSame(i, j)){
min = map[i][j];
xpos = i;
ypos = j;
}
}
}
if(xpos != -1){
sum += map[xpos][ypos];
mergeSet(xpos, ypos);
}
}
给定两条有向线段 A-->B,B-->C:
问题1:求A-->B在B-->C的顺时针方向还是逆时针方向:
(A-->B) x (B-->C) = (A-->B)(B-->C) sin(theta) > 0 ==> sin(theta) > 0 ==>
Assert theta < rad90, then theta > 0 ==> (A-->B) clockwise (B-->C), vice versa, qed.
问题2:A-->B-->C,判断B点是左转还是右转:
(B-->C) x (B-->A) > 0 ==> (B-->C)(B-->A) sin(theta) > 0 ==> sin(theta) > 0 ==>
Assert theta < rad90, then theta > 0 ==> (B-->C) clockwise (B-->A) ==> B - LeftTurn qed.
问题3:判断A--B && B--C是否相交:
若不存在某个点位于某条线段的相交情况,则有:
if (A-->B) x (A-->C) * (A-->C) x (A-->D) < 0 && (C-->D) x (C-->A) * (C-->D) x (C-->B) < 0 then A--B intersect B--C
若存在某个点位于某条线段上的相交情况,则在上面情况的基础上,增加:
if (A-->B) x (A-->C)
问题4:多边形面积计算:
原理是三角形划分,用到了叉乘的带符号面积,且以原点为中心。
问题5:凸包问题算法
Graham Scan Algorithm --- O(nlogn)
Jarvis March Algorithm --- O(n^2)
选y值最小的点,开始从0rad顺时针旋转,每次第一个相遇的点作为新的点,加入容器后继续上述操作,直到与第一个点相遇,即得到凸包。
找入度为0的点,找到后删除,继续查找,若不存在入度为0的点,并且已经找完所有点,则原有向无环图可以进行拓扑排序,反之,原图存在环,不能进行拓扑排序。
xxxxxxxxxx
int aa[505][505]; //邻接矩阵的形式表示图
int in_degree[505]; //存放各个节点的入度
int ans[505]; //存放排列的顺序
int n,m;// 顶点个数,边的数目
//读入并存储图
void scanG()
{
// 初始化
memset(aa, 0, sizeof(g));
memset(in_degree, 0, sizeof(in_degree));
memset(ans, 0, sizeof(ans));
int u, v;
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &u, &v);
aa[u][v] = 1;
in_degree[v]++; //计算入度
}
}
void topsort()
{
for(int i=1;i<=n;i++) {
int k=1;
while(in_degree[k]!=0) k++;
ans[i]=k;
in_degree[k]=-1;
for(int j=1;j<=n;j++) {
if(aa[k][j]) in_degree[j]--;
}
}
}
必胜点N点:上一个人将取胜的点。
必败点P点:下一个人将失败的点。
终结点必定是必败点;必胜点至少有一种方法可以进入必败点;必败点只能进入必胜点。
组合游戏解法:
[例] 假设某取子游戏一次只能取1、3、4张牌,先取完的人获胜,则 N P 标注方式如下:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|
P | N | P | N | N | N | N | P | N | N | P | N |
定理1:对于nim游戏的某个位置(x1 x2 x3)当且仅当各部分的 nim-sum = 0时,当前位置是必败点。
状态转移图
Sprague-Grundy函数
关键:更新最短路径的方式——两边之和小于第三边:
distance[j] = Math.min(distance[minpos] + map[minpos][j],distance[j])
例如上图,A --> C 的最短路径从100更新到50+10=60
xxxxxxxxxx
int dijkstra(int map[MAX][MAX], int len, int start, int end){
int distance[MAX];
int fin[MAX];
int minpos;
//fill distance
for(int i=0; i<len; i++){
distance[i] = map[start][i];
fin[i] = 0;
}
fin[start] = 1;
distance[start] = 0;
//start dijkstra
for(int i=0; i<len; i++){
//find min
int min=INF;
minpos=0;
for(int j=0; j<len; j++){
if(!fin[j] && distance[j]<min){
min = distance[minpos=j];
}
}
if(min == INF) {break;}
fin[minpos] = 1;
//update
for(int j=0; j<len; j++){
if(!fin[j] && distance[j] > min + map[minpos][j]){
distance[j] = min + map[minpos][j];
}
}
}
return (distance[end] == INF? -1: distance[end]);
}
xxxxxxxxxx
int edge[MAXN][MAXN];
int visited[MAXN];
int cx[MAXN], cy[MAXN];
int nx, ny;
int path(int u){
//扫描Y点集
for(int v=0; v<ny; v++){
//如果能访问并且能连通
if(edge[u][v] && !visited[v]){
visited[v] = 1;
if(cy[v] == -1 || path(cy[v])){
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
int maxmatch(){
int res = 0;
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
//扫描X点集
for(int i=0; i<nx; i++){
if(cx[i] == -1){
memset(visited, 0, sizeof(visited));
res += path(i);
}
}
return res;
}