Floyd判圈算法
用来求链表是否存在环并且找到环的起点和长度。也可以用来寻找数组的重复元素的（技巧算法）
快指针速度为2,慢指针速度为1。如果两个指针走着走着相交于A。则链表存在环。
求环长度：指针走一圈回到焦点，长度就是全长
求环起点：一个慢指针和交点位置慢指针分别从链表头和交点出发。第一次相交位置就是环的起点！
证明略：
//给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
int findDuplicate(vector& nums) {
int t=0,h=0;
do{
t=nums[t];
h=nums[nums[h]];
}while(h!=t);
h=0;
do{
t=nums[t];
h=nums[h];
}while(h!=t);
return h;
}
二分查找法
二分查找的排除法
可以用来解决排序后的查找问题和一些限制n求最小m的问题。
二分查找法
二分查找的排除法
可以用来解决排序后的查找问题和一些限制n求最小m的问题。
详见：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
模板:
搜索一个大于target的元素
left=0,right=size;//如果target过大，就是size
while(left<right){
mid=left+((right-left)>>1);
if(v[mid]<target)left=mid+1;
else right=mid;
}
1
2
3
4
5
6
搜索一个小于target的元素
left=0,right=size-1;
while(left<right){
mid=left+((right-left+1)>>1); //注意+1防止陷入死循环
if(v[mid]>target)right=mid-1;
else left=mid;
}
1
2
3
4
5
6
当然可以使用库函数lower_bound和upper_bound
假定是否可行
//有N条绳子，长度Li。从中切割出K条长度相同绳子，K最长多长
int N,K;
double L[MAX_N];
bool C(double x){
int num=0;
for(int i=0;i<N;i++)num+=(int)(L[i]/x);
return num>=K;
}
void solve(){
double lb=0,ub=INF;
for(int i=0;i<100;i++){
double mid=(lb+ub)/2;
if(C(mid))lb=mid;
else ub=mid;
}
printf(“%.2f\n”,floor(ub*100/100));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
最大化最小值
//N个屋子，在Xi位置，放入N个牛，最大化每个牛距离
int N,M;
int x[MAX_N];
bool C(int d){
int last=0;
for(int i=1;i<M;i++){
int crt=last+1;
while(crt<N&&x[crt]-x[last]<d)crt++;
if(crt==N)return false;
last=crt;
}
return true;
}
void solve(){
sort(x,X+N);
int lb=0,ub=INF;
while(ub-lb>1){
int mid = (lb+ub)/2;
if(C(mid))lb=mid;
else ub=mid;
}
printf(“%d\n”,lb);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
##最大化平均值
//有n物品重量Wi价值Vi，选出k个使得单位重量价值最大
//sum(Vi - x*Wi) >=0时，x满足大于等于最大平均价值
int n,k;
int w[MAX_N],v[MAX_N];
double y[MAX_N]; //v=xw
bool C(double x){
for(int i=0;i<n;i++){
y[i]=v[i]-xw[i];
}
sort(y,y+n);
double sum=0;
for(int i=0;i<k;i++){
sum+=y[n-i-1];
}
return sum>=0;
}
void solve(){
double lb=0,ub=INF;
for(int i=0;i<100;i++){
double mid = (lb+ub)/2;
if(C(mid))lb=mid;
else ub=mid;
}
printf(“%.2f\n”,ub);
}
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
尺选法
经常求连续数组元素问题。这里省略
反转问题
//N个开关关或者开，每一次可以使K个连续的开关反转。求为了让所有开关全开 所需要最少操作次数M和对应的K值
//思路：反转顺序无关紧要，而且同一个区间进行两次以上反转是没有意义的。考虑最左端开关：包含这个开关区间只有一个，我们可以通过它判断最左端区间是否需要反转。这样问题规模缩小了1。不断重复这个过程，就可以求出最小反转次数了。
int N;
int dir[MAX_N]; //开关状态，是0:开，还是1关
int f[MAX_N]; //区间[i,i+K-1]是否需要反转
int calc(int k){
memset(f,0,sizeof(f));
int res=0;
int sum=0; //一个区间的f的总和
for(int i=0;i+K<=N;i++){
if((dir[i]+sum)%2==0){
res;
f[i]=1;
}
sum+=f[i];
if(i-K+1>=0)sum-=f[i-K+1];
}
//检查剩下有没有关闭的情况
for(int i=N-K+1;i<N;i){
if((dir[i]+sum)%2 !=0)return -1;//无解
if(i-K+1>=0)sum-=f[i-K+1];
}
return res;
}
void solve(){
int K=1;M=N;
for(int k=1;k<=N;k++){
int m=calc(k);
if(m>=0 && M>m)M=m,K=k;
}
printf(“%d %d\n”,K,M);
}
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
34
35
//有一个MxN的各自，格子可以反转正反面。他们一面是黑色，另一面是白色。黑色反转后就是白色，反之白色反转就是黑色。你每次反转一个格子，他的上下左右所有格子都会翻成白色。现在给定每个格子颜色，求出把所有格子反转成白色时候的每个格子的最小反转次数。如果最小步数有多个解，输出字典序最小的一组。不存在输出IMPOSSIBLE
//问题分析：1. 同一个格子反转两次就会恢复。所以多次反转是多余的。 2. 反转格子相同的话，反转的次序无关紧要。 所以一共有2^(MxN)组解。 方法就是先指定最上方一行的翻转方法，然后直接判断(2,1)是否需要翻转。类似进行(2,1)~(2,N)。反复直到所有格子指定为止
//相邻格子坐标
const int dx[5]={-1,0,0,0,1};
const int dy[5]={0,-1,0,1,0};
//input
int M,N;
int title[MAX_N][MAX_N];
int opt[MAX_N][MAX_N]; //保存最优结果
int filp[MAX_N][MAX_N]; //保存中间结果
//查询x,y颜色
int get(int x,int y){
int c=tile[y];
for(int d=0;d<5;d++){
int x2=x+dx[d],y2=y+dy[d];
if(0<=x2&&x2<M&&0<=y2&&y2<N){
c+=flip[x2][y2];
}
}
return c%2;
}
//第一样确定情况下最小操作次数。如果不存在返回-1。0表示白色，1表示黑色
int calc(){
for(int i=1;i<M;i++){
for(int j=0;j<N;j++){
if(get(i-1,j)!=0){
flip[i][j]=1;
}
}
}
//判断最后一行是否是全白
for(int j=0;j<N;j++){
if(get(M-1,j)!=0)return -1;
}
//统计反转次数
int res=0;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
res+=flip[i][j];
}
}
return res;
}
void solve(){
int res=-1;
for(int i=0;i< 1<<N ;i++){
memset(flip,0,sizeof(flip));
for(int j=0;j<N;j++){
flip[0][N-j-1]= i>>j &1;
}
int num=calc();
if(num>=0&&(res<0 || res>num)){
res=num;
memcpy(opt,flip,sizeof(flip));
}
}
if(res<0)printf(“IMPOSSIBLE\n”);
else{
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
printf(“%d%c”,opt[i][j],j+1==N?‘\n’:’ ');
}
}
}
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
图论问题总结
最短路径问题
Bellman-Ford算法 O(VxE) 常用判断负圈情况
记从s出发到顶点i的最短路径是d[i]。则一下成立：
d[i] = min{d[j]+(从j到i的边的权重)|e=(j,i)}
1
如果图是一个DAG，就可以先拓扑排序（通过不断取出入度为０的节点实现），然后利用这个递推关系计算d。但是如果图中有圈，就无法使用特定顺序计算。这种情况，设置d[s]=0,d[i]=INF不断更新d。
Bellman-Ford算法的特点是可以检查这个图中是否存在负圈。
下面是不存在负圈的情况：
struct edge{int from,to,cost};
edge es[MAX_E];
int d[MAX_V];
int V,E; //顶点和边数
void shortest_path(int s){
for (int i=0;i<V;i++) d[i] = INF;
d[s] = 0;
while(true){
bool update = false;
for(int i=0;i<E;i++){
edge e = es[i];
if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost){
d[e.to] = d[e.from] + e.cost;
update = true;
}
}
if(update == false)break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
如果图中不存在从s可达的负圈，那么最短路径不会经过同一个顶点两次。也就是外层while循环最多不会循环V次。所以我们可以通过计数while循环次数是否超过V判断是否存在负圈。
Dijkstra算法
该算法不能存在负圈。
下面使用最小堆实现实现O(|E|log|V|)
struct edge {int to,cost;};
typedef pair<int,int> P; //first是最短距离，second是顶点编号
int V;
vector G[MAX_V];
int d[MAX_V];
void dijkstra(int s){
//按照first排序的小顶堆
priority_queue<P,vector
,greater
> que;
> fill(d,d+V,INF);
> d[s]=0;
> que.push(P(0,s));
> while(!que.empty()){
> P p = que.top();que.pop();
> int v= p.second;
> if(d[v] < p.first)continue;
> for(int i=0;i<G[v].size();i++){
> edge e = G[v][i];
> if(d[d.to]>d[v]+e.cost){
> d[e.to]=d[v]+e.cost;
> que.push(P(d[e.to],e.to));
> }
> }
> }
> }
> 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
> floyd-warshall算法 任意两点最短问题 O(V^3)
> int d[MAX_V][MAX_V]; //d[u][v]表示e(u,v)权重，不存在时候为INF,d[i][i]=0
> int V;
void warshall_floyd(){
for(int K = 0; k < V; k++)
for(int i = 0; i< V;i++)
for(int j= 0;j<V;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
1
2
3
4
5
6
7
8
最小生成树
prim 算法
思路就是每次选取已包含的顶点和未包含的顶点之间的最短边，加入到其中。
以下是O(V^2)实现，如果是使用小顶堆就是O(|E|log|V|)
int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];
int prim(){
for(int i=0;i<V;i){
mincost[i]=INT_MAX;
used[i]=false;
}
mincost[0]=0;
int res=0;
while(true){
int v=-1;
//从不属于已包含顶点中选取到已包含顶点权值最小的顶点
for(int u=0;u<V;u){
if(!used[u]&&(v==i||mincost[u]<mincost[v]))
}
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
kruskal 算法
每次找到最小边插入其中，使用并查集实现
struct UFTree{
vector par;
UFTree(int n):par(n){
for(int i=0;i<n;i++)par[i]=i;
}
int find(int x){
if (parx)return x;
return par=find(par);
}
void unite(int x,int y){
x=find(x);y=find(y);
if(xy)return;
par=y;
}
};
struct edge{int u,v,cost;};
bool comp(const edge&e1,const edge&e2){return e1.cost < e2.cost;}
edge es[MAX_E];
int V,E; //顶点数和边数
int kruskal(){
sort(es,es+E,comp);
UFTree uf(V);
int res=0;
for(int i=0;i<E;i++){
edge e=es[i];
if(!same(e.u,e.v)){
unite(e.u,e.v);
ret+=e.cost;
}
}
return res;
}
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
34
35
查并集
//连续性
struct UFTree{
vector par;
UFTree(int n):par(n){
for(int i=0;i<n;i++)par[i]=i;
}
int find(int x){
if (parx)return x;
return par=find(par);
}
void unite(int x,int y){
x=find(x);y=find(y);
if(xy)return;
par=y;
}
};
//哈希型
struct UFTree{
unordered_map<int,int> par;
UFTree()=default;
UFTree(int n){
par.reserve(n);
}
int find(int x){
if (par.find(x)par.end())return x;
return par=find(par);
}
void unite(int x,int y){
x=find(x);y=find(y);
if(xy)return;
par=y;
}
};
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
34
数学窍门
辗转相除法
举例：
给定平面上面两个格点：P1(x1,y1)和P2(x2,y2)。线段上面除了P1,P2还有几个格点？
-109<=x1,x2,y1,y2<=109
1
2
3
这道题就是求最大公约数
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a % b);
}
1
2
3
4
素数
关键定理：x以内的所有合数的最小质因数都不超过x^0.5
//素数测试
bool is_prime(int n){
for(int i=2;i*i<=n;i++){
if(n%i==0)return false;
}
return n!=1;
}
//约数枚举
vector divisor(int n){
vector res;
for(int i=1;i*i<=n;i++){
if(n%i==0){
res.push_back(i);
if(i!=n/i)res.push_back(n/i);
}
}
return res;
}
//整数分解
map<int,int> prime_factor(int n){
map<int,int> res;
for(int i=2;i*i<=n;i++){
while(n%i==0){
++res[i];
n/=i;
}
}
if(n!=1) res[n]=1;
return res;
}
//筛子
int prime[MAX_N];//第i个素数
bool is_prime[MAX_N+1]; //is_prime[i]表示i是不是素数
int sieve(int n){
int p=0;
for(int i=0;i<=n;i++)is_prime[i]=true;
is_prime[0]=is_prime[1]=false;
for(int i=2;i<=n;i++){
if(is_prime[i]){
prime[p++]=i;
for(int j=2*j;j<=n;j+=i)is_prime[j]=false;
}
}
return p;
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
模运算
注意：
a是负数时候a%m也是负数。所以a%m + m就可以保证结果在0~m-1范围内。
假设ac(mod m) && bd(mod m)，以下成立：
a+b == c+d(mod m)
a-b == c-d(mod m)
ab == cd(mod m)
1
2
3
快速幂
typedef long long ll;
ll mod_pow(ll x,ll n,ll mod){
ll res=1;
while(n>0){
if(n&1)res=resx % mod;
x=xx % mod;
n>>=1;
}
return res;
}
也是只懂皮毛，涉入不深 可不可以告诉我怎么达到版主a？（jiu zhe goushi haixiang jin zhen banzhu!
