涉及的知识点

第九周主要是当堂题目的练习，涉及的知识点有差分、BFS、Map/排序、并查集

拓展：双向BFS、平面分治最小点对、离散化

基础训练

差分

例题

题目大意：每次对区间操作，求操作结果

思路：差分，标记区间，累和

代码

#include <iostream>
#include <cstring>
using namespace std;
int value[121212],paint[121212],N,a,b;
int main()
{while(cin >>N&&N){for(int i=1; i<=N; i++){cin >>a>>b;value[a]++;value[b+1]--;}int t=0;for(int i=1; i<=N; i++){t+=value[i];cout <<paint[i]+t;if(i!=N)cout <<" ";}cout <<endl;memset(value,0,sizeof(value));memset(paint,0,sizeof(paint));}return 0;
}

BFS

例题

题目大意：马走日，每次能走8个方向，给出起点和终点，判断最短几步能够到达

思路：直接暴力BFS

代码

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N,l;
typedef pair<int,int>PR;
PR start,last;
int Chess[300][300];
bool visited[300][300];
int Next[8][2]= {-2,1,-2,-1,2,1,2,-1,1,-2,1,2,-1,-2,-1,2};
typedef struct node
{int x,y,level;node(int _x,int _y,int t){level=t;x=_x;y=_y;}
} node;
void BFS()
{node t(start.first,start.second,0);queue<node>Q;Q.push(t);while(!Q.empty()){t=Q.front();Q.pop();if(visited[t.x][t.y])continue;if(visited[last.first][last.second])break;Chess[t.x][t.y]=t.level;visited[t.x][t.y]=true;for(int i=0; i<8; i++){int x=t.x+Next[i][0],y=t.y+Next[i][1];if(x>=0&&x<l&&y>=0&&y<l&&!visited[x][y])Q.push(node(x,y,t.level+1));}}
}
int main()
{scanf("%d",&N);while(N--){scanf("%d",&l);scanf("%d%d%d%d",&start.first,&start.second,&last.first,&last.second);if(start.first==last.first&&start.second==last.second)Chess[last.first][last.second]=0;elseBFS();printf("%d",Chess[last.first][last.second]);if(N!=0)printf("\n");memset(Chess,0,sizeof(Chess));memset(visited,0,sizeof(visited));}return 0;
}

Map/排序

例题

题目大意：给出一个字符串集合，随后给出多个单词，判断每个单词是否能由集合中某个单词变化顺序而得，如果有多个则从小到大按照字典序输出集合中符合定义的单词

思路：直接Map存储，以集合中每个单词自身按照字典序变化后的字符串为索引，存入可变化成索引的单词，最后将输入的单词同等变化进行查找

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
map<string,vector<string>>Map;
map<string,vector<string>>::iterator p;
int main()
{string input;while(1){cin >>input;if(input=="XXXXXX")break;string t=input;sort(input.begin(),input.end());Map[input].push_back(t);}while(1){cin >>input;if(input=="XXXXXX")break;sort(input.begin(),input.end());p=Map.find(input);if(p!=Map.end()){int t=Map[input].size();sort(Map[input].begin(),Map[input].end());for(int i=0; i<t; i++)cout <<Map[input][i]<<endl;}elsecout <<"NOT A VALID WORD"<<endl;cout <<"******"<<endl;}return 0;
}

并查集

例题

题目大意：给出N个点，M条边，代表M次相连（可能有重复），最后判断还需要几条边才能使所有点连通

思路：使用并查集+路径压缩，最后判断有几个集合，输出集合数-1

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int N,M;
int Orign[1212];
int seek(int x)
{if(Orign[x]==x)return x;return Orign[x]=seek(Orign[x]);
}
void Union(int x,int y)
{int _x=seek(x),_y=seek(y);if(_x!=_y)Orign[_x]=Orign[_y];
}
int main()
{while(scanf("%d%d",&N,&M)&&N){for(int i=1;i<=N;i++)Orign[i]=i;int ans=0;while(M--){int a,b;cin >>a>>b;Union(a,b);}for(int i=1; i<=N; i++){int x=seek(Orign[i]);if(x==i)ans++;}cout <<ans-1<<endl;}return 0;
}

拓展

双向BFS

平面分治最小点对

思想&概念讲解详见寻找距离最小的平面点对——分治方法

例题

题目大意：给出N个A种点，N个B中点，求出距离最小的点对AB，输出其距离

思路：平面分治最小点对的思想，首先把所有点平分成两部分，求出两部分中的最小值，之后再找出两部分相互成对的前提下的最小值，最后比较出最小值

代码

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define INF 1e80
using namespace std;
struct node
{double x,y;bool flag;
} points[1000000],ope[1000000];
bool cmpx(node&a,node&b)
{return a.x<b.x;//判断横坐标大小
}
bool cmpy(node&a,node&b)
{return a.y<b.y;//判断纵坐标大小
}
double dist(node&a,node&b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));//返回距离
}
double mindist(int low,int high)
{if(low==high)//只有一个点，距离为无穷大return INF;if(high==low+1)//找到一对点{if(points[low].flag^points[high].flag)//如果异类，返回距离return dist(points[low],points[high]);return INF;}int mid=(low+high)/2;//得到中点，划分成两个区域double d1=mindist(low,mid),d2=mindist(mid,high),dis=min(d1,d2);//获得左右区域中的最小值int K=0;for(int i=low;i<=high;i++)if(fabs(points[i].x-points[mid].x)<=dis)//如果横坐标之差小于当前最短距离，则该点对可能有更短的距离，记录ope[K++]=points[i];sort(ope,ope+K,cmpy);//按照纵坐标从小到大排序for(int i=0;i<K;i++)for(int j=i+1;j<K;j++){if(ope[j].y-ope[j].y>dis)//如果纵坐标之差大于当前最短距离，后面的纵坐标之差都大于当前最短距离break;if(ope[j].flag^ope[i].flag)//如果异类，更新最短距离dis=min(dis,dist(ope[i],ope[j]));}return dis;
}
int main()
{int T,N;cin >>T;while(T--){cin >>N;for(int i=0;i<N;i++){cin >>points[i].x>>points[i].y;//记录A种点points[i].flag=false;}for(int i=0;i<N;i++){cin >>points[i+N].x>>points[i+N].y;//记录B种点points[i].flag=true;}N<<=1;sort(points,points+N,cmpx);//按照横坐标排序，如果不排序，就无法划分成两个分布类似且对称的区域printf("%.3lf\n",mindist(0,N-1));//输出最小点对对应距离}return 0;
}

离散化

离散化，即将所给集合中分散的点进行“紧凑”，使其更密集，便于操作，如在$1-10^9$范围内给出$10^3-10^4$个点进行种种操作，我们无需用一个类似桶的数组来存储，可以直接将这些点存入另一个数组，排序进行“紧凑”，最后我们获得了这些点的相对大小关系，有时我们只需要这样的关系。

离散化分为两类，第一种为重复元素离散化后数字相同，第二种为重复元素离散化后数字不同。

第一种

第二种

例题

题目大意：有N个科学家，每个科学家会一种语言，用编号来表示，编号$1\le a_i\le 10^9$,有M部电影，每部电影有一种音频和一种字幕，编号分别$1\le b_i\le 10^9、1\le c_i\le 10^9$，如果音频和科学家语言对应，科学家满意度高，字幕与语言对应，科学家满意度中，字幕和音频都不与语言对应，科学家满意度低，求出能使满意度高的人数最多的电影，如果人数一样，则求出满意度中更多的电影，输出它是第几个。

思路：如果按照桶的思想，开一个数组去存取各编号出现的次数，显然一个10亿的数组是天方夜谭，可以采用哈希/离散化的思想，仍然采用桶的思想，将编号变化成更小的、可存储的索引（例如排序后所处的下标），之后统计各个编号对应出现的次数。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int INF=(int)2e6;
int N,M,a[INF+12],b[INF+12],c[INF+12],d[INF*3+12],ans[INF+12],len;
void discreatize()//离散化
{len=0;for(int i=1; i<=N; i++)d[++len]=a[i];for(int i=1; i<=M; i++)d[++len]=b[i];for(int i=1; i<=M; i++)d[++len]=c[i];//将所有数据存入同一个数组sort(d+1,d+len+1);//排序，为构造索引准备len=unique(d+1,d+len+1)-d-1;//获得除去重复值后的长度，即有多少种语言，将每个语言编号所处的下标设为索引
}
int seek(int x)
{return lower_bound(d+1,d+len+1,x)-d;//获取索引值
}
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);//取消同步，加快速度cin >>N;for(int i=1; i<=N; i++)cin >>a[i];//存科学家语言编号cin >>M;for(int i=1; i<=M; i++)cin >>b[i];//存音频for(int i=1; i<=M; i++)cin >>c[i];//存字幕discreatize();//离散化//离散化后，d数组的索引对应着语言编号for(int i=1; i<=N; i++)ans[seek(a[i])]++;//桶的思想，该索引值出现的次数自增int acc=1,Vmax=0,Mmax=0;for(int i=1; i<=M; i++){int vedio=ans[seek(b[i])],movie=ans[seek(c[i])];//同上，获取索引值对应编号出现的次数进行判断if(vedio>Vmax||vedio==Vmax&&movie>Mmax)//找到符合题设要求的最大值{Vmax=vedio;Mmax=movie;acc=i;}}cout <<acc;return 0;
}

参考文献

1. 寻找距离最小的平面点对——分治方法
2. 《挑战程序设计竞赛》
3. SDNU_ACM_ICPC_2020_Winter_Practice_2nd C 离散化， lower_bound
4. 离散化：两种离散化方式详解
5. 搜索算法——双向bfs