各种内容转载以及PS

xiaoxiao2025-02-07 44

快速幂,矩阵快速幂原理介绍

背包问题总结

最大流学习内容

EK算法：

FF算法

Dinic算法

ACM：悬线法

康托展开&逆康托展开

数码问题

多项式

A*算法

IDA*算法

DFS序

快速幂,矩阵快速幂原理介绍

https://blog.csdn.net/Anxdada/article/details/73544695

背包问题总结

https://blog.csdn.net/qq_39826163/article/details/81156012

最大流学习内容

https://blog.csdn.net/x_y_q_/article/details/51999466（最大流）

EK算法：BFS来寻找增广路 Dinic：(用到层次图) FF算法：DFS来寻找增广路

https://blog.csdn.net/qq_41357771/article/details/79416899（三种算法）

https://blog.csdn.net/weixin_40673608/article/details/86707598（EK和FF的不同，FF比较慢）

https://blog.csdn.net/chinacoy/article/details/45040897（最大流就是最小割）

EK算法：

FF算法

Dinic算法

ACM：悬线法

https://blog.csdn.net/DBC_121/article/details/77503611

康托展开&逆康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成不同(n!种)的排列组合，康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。

https://blog.csdn.net/wbin233/article/details/72998375

https://blog.csdn.net/qq_15015129/article/details/71023779

数码问题

n*n的网格，如果n为奇数，当奇数码游戏两个局面可达，当且仅当两个局面下网格中的数依次写成1行n*n-1个元素的序列后（不考虑空格），逆序对个数的奇偶性相同。

证明：空格左右移动时，写成的序列显然不变；空格上（下）移动时，相当于某个数与它后（前）边的n-1个数交换了位置，因为n-1是偶数，所以逆序对的变化也只能是偶数。

如果n为偶数，两个局面可达，当且仅当两个局面对应网格写成序列后，“逆序对数之差”和“两个局面下空格所在的行数只差”奇偶性相同。事实上，n*m网格上(n,m>=2)也服从上述两个结论之一（根据列数奇偶性分情况讨论）

总而言之，n*m数码问题的有解性判定，可以转化为归并排序求逆序对来解决。

多项式

三次以上的多项式一定可以因式分解

https://www.zybang.com/question/48224e25d4c663da44829a6045be7373.html

A*算法

https://blog.csdn.net/hitwhylz/article/details/23089415

https://blog.csdn.net/liudongdong19/article/details/79998852

自己写的，也没怎么测试，错了勿怪

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #define rep(i,s,e) for(int i=s;i<=e;i++) #define rep1(i,s,e) for(int i=s;i<e;i++) #define rep2(i,s,e,c) for(int i=s;i>=e;i--) #define pfi(x) printf("%d\n",x) #define pfl(x) printf("%lld\n",x) #define pfn() printf("\n") #define pfs() printf(" ") #define sfi(x) scanf("%d",&x) #define sfi1(x,y) scanf("%d%d",&x,&y) #define sff(x) scanf("%lf",&x) #define sfl(x) scanf("%lld",&x) #define memset1(x) memset(x,0,sizeof(x)) using namespace std; typedef long long ll; const int MAX = 8e3+50; const int mod = 996873654; int n,m;//n行m列 //假设可以走八个方向，而且直走cost为10，斜走cost为14(简单) int xy[][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}}; struct vis{ int walkable; bool close_list; bool open_list; //int cost;//题目中可能会出现的代价，比如在沼泽中花费更多的体力 int fromX,fromY; int f,g,h;//f=g+h,用曼哈顿距离估算h,g为移动代价 }mmap[MAX][MAX]; struct node{ int x,y; node(): x(0), y(0){} void init(int _x,int _y){ x=_x; y=_y; } void calculate(node des){ mmap[x][y].g=mmap[mmap[x][y].fromX][mmap[x][y].fromY].g; if(x==mmap[x][y].fromX || y==mmap[x][y].fromY) mmap[x][y].g+=10; else mmap[x][y].g+=14; mmap[x][y].h=abs(x-des.x)+abs(y-des.y); mmap[x][y].f=mmap[x][y].g+mmap[x][y].h; } bool judge(node p,node des){ if(!mmap[x][y].walkable || mmap[x][y].close_list) return false; if(x>=1&&x<=n&&y>=1&&y<=m){ if(!mmap[x][y].open_list){ mmap[x][y].open_list=true; mmap[x][y].fromX=p.x; mmap[x][y].fromY=p.y; calculate(des); return true; } else{ int newg=mmap[p.x][p.y].g; if(p.x==x || p.y==y) newg+=10; else newg+=14; if(newg<mmap[x][y].g){ mmap[x][y].fromX=p.x; mmap[x][y].fromY=p.y; mmap[x][y].g=newg; mmap[x][y].f=mmap[x][y].g+mmap[x][y].h; return true; } else return false; } } } bool operator == (const node& temp) const{ if(x==temp.x && y==temp.y) return true; else return false; } bool operator < (const node& temp) const{ return mmap[x][y].f>mmap[temp.x][temp.y].f; } }src,des,p,p1; priority_queue<node> q; void Astar(){ while(!q.empty()) q.pop(); q.push(src); mmap[src.x][src.y].open_list=true; while(!q.empty()){ p = q.top(); q.pop(); mmap[p.x][p.y].close_list=true; mmap[p.x][p.y].open_list=false; if(p==des) break; rep1(i,0,8){ p1.init(p.x+xy[i][0],p.y+xy[i][1]); if(p1.judge(p,des)){ q.push(p1); } } } } int main(){ while(cin>>n>>m){ rep(i,1,n){ rep(j,1,m){ sfi(mmap[i][j].walkable); } } int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; src.init(x1,y1); des.init(x2,y2); Astar(); if(mmap[des.x][des.y].walkable && mmap[des.x][des.y].close_list){ stack<node> st; p.init(des.x,des.y); while(1){ st.push(p); if(p==src) break; p.init(mmap[p.x][p.y].fromX,mmap[p.x][p.y].fromY); } while(st.size()){ p=st.top(); st.pop(); cout<<p.x<<" "<<p.y<<"\n"; } } } return 0; } /* 5 7 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 3 2 3 6 */

IDA*算法

https://blog.csdn.net/urecvbnkuhbh_54245df/article/details/5856756

https://blog.csdn.net/yangliuy/article/details/40584869

算法题目：https://blog.csdn.net/qq_42711300/article/details/99676563

A*算法概述：采用广度优先搜索策略，在搜索过程中使用启发函数，即有大致方向的向前进虽然目标有时候不是很明确。 A*算法核心： A*算法的关键在于启发函数，启发函数的优劣直接影响A*算法的效率。 f(n)=g(n)+h(n); 这个式子中：f(n)表示从初始状态到目标状态的估测代价。 g(n)表示从初始状态到当前状态的代价（已经确定）。 h(n)表示从当前状态到目标状态的估测代价(预测）。其中：h(n)的好坏直接影响评估函数的好坏。一个好的f(n)总能明确指引算法前进的方向，可以迅速的到达目标状态。 f*(n)=g*(n)+h*(n); 我们假设的从初始状态到目标状态的实际最小代价。这个式子中：f(n)表示从初始状态到目标状态的实际代价。 g*(n)表示从初始状态到当前状态的代价（已经确定）g*(n)和g(n)是相等的。 h*(n)表示从当前状态到目标状态的实际代价。若h(n)<=h*(n),则总能找到最优解。（当h(n)<h*(n)的时候，不可能找到一条从初始状态到达目标状态的路径。在搜索过程中使得h(n)逐渐接近h*(n)，最终找到最优路径。优点：与广度优先搜索策略和深度优先搜索策略相比，A*算法不是盲目搜索，而是有提示的搜索。缺点：该算法一般要使用大量的空间用于存储已搜索过的中间状态，防止重复搜索。用途：从初始状态出发 =>经过一系列中间状态 =>最终到达目标状态（或者无法到达）。该算法用于经过中间状态时候的行进策略（其中的中间状态或者由题目给出，或者在前边已经推导得出）。

IDA*算法：迭代加深搜索算法，在搜索过程中采用估值函数，以减少不必要的搜索。 IDA*算法核心：设置每次可达的最大深度depth，若没有到达目标状态则加深最大深度。采用估值函数，剪掉f(n)大于depth的路径。优点：使用回溯方法，不用保存中间状态，大大节省了空间。缺点：重复搜索：回溯过程中每次depth变大都要再次从头搜索。用途：和A*算法大致相同。

实际上，估测函数f(n)也是剪枝的一种。

DFS序

https://blog.csdn.net/qq_24489717/article/details/50569644

最新回复(0)