2023暑假知行进阶营第三周题解

2023暑假知行进阶营第三周题解 | HBUACMHBUACM

markdown 文章内容

7-1词典

这道题用map写很快的，有些同学是用字符串数组遍历查找做的，数据量大的话会超时，建议大家好好学一下c++，很好用。

#include <iostream>
#include <map>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    map<string,string>mp;
    while(n--){
        string s1,s2;
        cin>>s1>>s2;
        mp[s2]=s1;
    }
    while(m--){
        string s;
        cin>>s;
        if(mp.count(s)) cout<<mp[s]<<endl;
        else cout<<"eh"<<endl;
    }
    return 0;
}

7-2镖局运镖

将所有城市连成一个图，要求花费最低，就是在考最小生成树嘛。这里给大家介绍两个算法，kruskal算法和prime算法。

kruskal算法

1、将权重最小的边和两个结点加入树；

2、剩下边中选择权重最小的边，如果两个结点不在同一个连通分支（并查集），就将此边加入树，否则跳过；

3、不断重复2。

prime算法

1、选取一个点s（从该点开始构建树），初始化其余点到点s的距离
2、选取不在树中，且距离树最近的点p，点p放入树中
3、查看点p可到达的点，利用点p，尝试缩短它们和树的距离
4、不断重复2、3

kruskal代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100010
#define M 200020
using namespace std;

struct node {
	int x, y, z;
	bool operator < (const node &a) const{
		return z < a.z;
	}
}st[M];

int fa[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]);}

int main() {
	int n, m, cnt, ans = 0;
	scanf("%d%d", &n, &m);
	cnt = n;
	for(int i = 1; i <= n; ++i) fa[i] = i;
	for(int i = 1; i <= m; ++i) scanf("%d%d%d", &st[i].x, &st[i].y, &st[i].z);
	sort(st + 1, st + m + 1);//按权重升序排列
	for(int i = 1; i <= m; ++i) {
		if(find(st[i].x) != find(st[i].y)) {//不是同一个连通分支，就加入此边
			fa[find(st[i].x)] = find(st[i].y);
			--cnt;//记录加入边数，这里cnt初始为0，每次+1也OK
			ans += st[i].z;
		}
	}
	if(cnt > 1) printf("impossible\n");//最小生成树的边数应为n-1，n为结点数；或者可以遍历fa数组，求连通分支个数是否为1
	else printf("%d", ans);
	return 0;
}

prime代码

#include <iostream>
#include <string.h>
using namespace std;
const int N=1005;
const int F=0x3f3f3f;
int n,m,w[N][N];
void prime(){
    int dis[N],ret=0;
    for(int i=1;i<=n;i++) dis[i]=w[1][i];
    bool vis[N]={false};
    vis[1]=true;
    for(int i=1;i<=n-1;i++){//还有n-1个点没有加入树，循环n-1次
        int cnt=F,p=-1;
        for(int j=1;j<=n;j++){//找到距离树最近的点
            if(!vis[j]&&dis[j]<cnt){
                cnt=dis[j];
                p=j;
            }
        }
        if(p==-1){//有部分点是不连通的，建不了最小生成树
            cout<<"impossible"<<endl;
            return;
        }
        vis[p]=true;
        ret+=dis[p];
        for(int j=1;j<=n;j++){
            if(!vis[j]&&w[p][j]<dis[j])//更新其他点到树的距离
               dis[j]=w[p][j];
        }
    }
    cout<<ret<<endl;
}
int main(){
    cin>>n>>m;
    memset(w,F,sizeof w);
    for(int i=0;i<m;i++){
        int a,b,c; cin>>a>>b>>c;
        w[a][b]=w[b][a]=c;
    }
    prime();
    return 0;
}

7-3并查集【模板】

这道题的第十个测试点，如果用标准的并查集模板，时而过时而不过的，可以试试下面的快速读入方法。

#include <iostream>
using namespace std;
const int N=10005;
int f[N];
int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void merge(int a,int b){
    int x=find(f[a]),y=find(f[b]);
    f[x]=y;
}
int read() {//快速读入
	int x = 0;
	char ch = getchar();
	while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
	return x;
}
int main(){
    int n,m;
    n = read(); m = read();
    for(int i=0;i<n;i++)
        f[i]=i;
    while(m--){
        int z,x,y;
        z = read(); x = read(); y = read();
        if(z==1) merge(x,y);
        else{
            if(find(x)==find(y)) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }
    return 0;
}

7-4冗余连接

这道题也是考察在并查集，题目说找到最后出现的可以删除的边，所以可以从第一条边开始遍历，如果两个结点不在同一个连通分支，合并；如果在，那这条边是没用的，也就是我们要找的可以删除的边，用一个变量记录。

#include <iostream>
using namespace std;
int f[110];
int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void merge(int a,int b){
    int fa=find(a),fb=find(b);
    if(fa!=fb) f[fa]=fb;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        f[i]=i;
    int p=0;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        if(find(a)==find(b)) p=i;
        else merge(a,b);
    }
    cout<<p;
    return 0;
}

7-5求最短路径-flyod算法

这道题不算难，认真读题，flyod算法在其他数学规划题目中应用也很多，可以去了解一下。

思路：建图，求任意两节点间的最小距离

#include <iostream>
#include <cstring>
using namespace std;
const int F=0x3f3f3f3f,N=11;
int n,m,k;
int mp[N][N];
int main(){
    cin>>n>>m>>k;
    memset(mp,F,sizeof mp);
    for(int i=1;i<=n;i++) mp[i][i]=0;
    while(m--){
        int a,b,w;
        cin>>a>>b>>w;
        mp[a][b]=w;
        if(!k) mp[b][a]=w;
    }
    for(int k=1;k<=n;k++)//通过k点更新i与j的最小距离
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
    int mindis=F,p=0;
    for(int i=1;i<=n;i++){
        int dis=0;
        for(int j=1;j<=n;j++) dis=max(dis,mp[i][j]);//求dis也可用dijkstra算法,令i为起点，不断更新其他点到i的距离
        if(dis<mindis){
            p=i;
            mindis=dis;
        }
    }
    cout<<p;
    return 0;
}

7-6单源最短路径

dijkstra，迪杰斯特拉算法
计算带权图中某一点（记为源点，一般用s命名）到其他点的最短距离
1、将图中的点看作两部分，一部分是已经找到了最短路的点集合A，另一部分是没有找到最短路的点集合B
2、起初集合A 中只有s，B集合中为剩余的（n-1）个点
3、初始化其余点到点s的距离（邻接矩阵的s行），不断进行4、5以更新其余点到点s的最短距离
4、在B 集合中寻找距离s最近的点p，将p放入集合A（s到p的最短路已经求出来了）
5、查看点p可到达点，试探是否能够通过点p缩短距离（s->p->点）

这道题n比较大，但m很小，二维数组会爆内存，所以我们用两个vector数组分别存边的终点和权重。

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

const int F=0x3f3f3f3f;
const int N=20005;
vector<int> v[N];//边的终点
vector<int> w[N];//边的权重
int n,m;

void dijkstra(int s){
    bool book[N]={false};
    int dis[N];
    memset(dis,F,sizeof dis);
    for(int i=0;i<v[s].size();i++){//更新每个点到s的距离
        dis[v[s][i]]=w[s][i];
    }
    book[s]=true;
    for(int i=1;i<=n-1;i++){
        int cnt=F,p=-1;
        for(int j=0;j<n;j++){
            if(!book[j]&&dis[j]<cnt){//在剩余点中找距离s最近的点
                p=j;
                cnt=dis[j];
            }
        }
        if(p==-1) break;
        book[p]=true;//标记p点
        for(int j=0;j<v[p].size();j++){//通过p点尝试更新其他点到s的最短距离
            if(!book[v[p][j]]&&dis[p]+w[p][j]<dis[v[p][j]])
                dis[v[p][j]]=dis[p]+w[p][j];
        }
    }
    for(int i=1;i<n;i++){
        if(dis[i]!=F)
            cout<<dis[i]<<" ";
    }
}
int main(){
    cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back(b);
        w[a].push_back(c);
    }
    dijkstra(0);
    return 0;
}

7-7有向图的拓扑排序

1、在有向图中选择一个没有入度的点输出；
2、从图中删除该顶点和所有以它为起点的边，对应边的终点入度-1；
3、重复1、2，直到所有顶点输出。

#include <iostream>
#include <vector>
#include <stack>
const int N=1005;
using namespace std;
int n,m;
vector<int> ve[N];
int count[N]={0};
void topo(){
    stack<int> s;//采用栈存储入度为0的结点
    int cnt=0;//计数
    for(int i=1;i<=n;i++){
        if(!count[i]) s.push(i);//入度为0，入栈
    }
    for(int i=1;i<=n;i++){//每次输出一个点，故循环n次
        if(s.empty()) break;//有环
        int cur=s.top(); s.pop();
        cout<<cur<<" "; cnt++;
        count[cur]=-1; //标记为-1，避免重复入栈
        for(int j=0;j<ve[cur].size();j++){
            int v=ve[cur][j];
            count[v]--;
            if(!count[v]) s.push(v);
        }
    }
    if(cnt<n) cout<<endl<<"0";
}
int main(){
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        count[b]++;//计算入度
        if(ve[a].size()) ve[a].insert(ve[a].begin(),b);//题目要求：表头插入法构造邻接表
        else ve[a].push_back(b);
    }
    topo();
    return 0;
}

7-8FBI树

给定的字符串实际是二叉树的叶子结点，该二叉树的深度为n+1。

叶子结点在一维数组中的编号从2^n开始，通过叶子结点向上不断构造树。

这里使用一维数组构造树，如果不了解一维数组如何构造二叉树的话，可以到CSDN上学。

这里采用的是边构造边遍历的方式。也可以先构造二叉树，再后序遍历。

#include <iostream>
using namespace std;
int n;
char t[3000];
void dfs(int root){//从树的根结点1开始后序遍历
    if(root>=(1<<n)){//到达叶子结点这一层也就是最后一层就没必要再往下了，输出结点值，return;
        cout<<t[root];
        return;
    }
    dfs(root*2);//后序遍历左子树
    dfs(root*2+1);//后序遍历右子树
    if(t[root*2]=='I'&&t[root*2+1]=='I')//根据左右子树构建根结点
        t[root]='I';
    else if(t[root*2]=='B'&&t[root*2+1]=='B')
        t[root]='B';
    else 
        t[root]='F';
    cout<<t[root];//后序遍历根结点
}
int main(){
    cin>>n;
    getchar();
    for(int i=0;i<(1<<n);i++){
        int p=getchar()-'0';
        if(p) t[(1<<n)+i]='I';//存储叶子结点，二叉树第n+1层，1<<n是2^n，也可写pow(2,n);
        else t[(1<<n)+i]='B';
    }
    dfs(1);
    return 0;
}

7-9堆的操作

考察小根堆，下面代码有部分注释，如果想细节学习，可以到CSDN上了解一下，或者找群内管理员。

自写函数（原理部分）

#include <iostream>
#include <cstring>
using namespace std;
int heap[2010],heap_size;
void siftdown(int i){//向下寻找正确位置
    while(i*2<=heap_size){
        int ch=i*2;//小根堆满足父结点小于等于子节点，也就是说小于等于值最小的那个结点才可以，所以下面加一句判断
        if(ch+1<=heap_size&&heap[ch+1]<heap[ch]) ch++;
        if(heap[i]<=heap[ch]) break;//当前位置已满足，退出循环
        swap(heap[i],heap[ch]);//不满足，则将父结点与子节点交换
        i=ch;//继续向下找合适位置
    }
}
void push_data(int data){//向堆内插入结点
    int cur=++heap_size;
    heap[cur]=data;//先放到堆的最末端
    while(cur!=1&&heap[cur]<heap[cur/2]){//向上寻找正确位置
        swap(heap[cur],heap[cur/2]);
        cur/=2;
    }
}
void pop_data(){//移除堆顶
    if(!heap_size) return;
    heap[1]=heap[heap_size--];//将最后一个结点放到首端，堆长度-1
    siftdown(1);//向下寻找正确位置
}
int main(){
    int n,k;
    cin>>n>>k;
    while(k--){
        int p,x;
        cin>>p;
        if(p==-1) pop_data();
        else{
            cin>>x;//记得判断堆的容量，题目规定容量为n
            if(heap_size<n) push_data(x);
        }
        for(int i=1;i<=heap_size;i++){
            if(i>1) cout<<" ";
            cout<<heap[i];
        }
        cout<<endl;
    }
    memset(heap,0,sizeof heap);
    int m;
    cin>>m;
    heap_size=m;
    for(int i=1;i<=m;i++) cin>>heap[i];
    for(int i=m/2;i>=1;i--)  siftdown(i);//从数组中间位置开始调整
    for(int i=1;i<=heap_size;i++){
        if(i>1) cout<<" ";
        cout<<heap[i];
    }
    return 0;
}

c++自带函数

（1）make_heap将一个可迭代容器变成堆，默认大根堆

make_heap(begin,end,less<>());//大根堆
make_heap(begin,end,greater<>());//小根堆
//begin和end分别是指向开始元素和末尾元素的迭代器

（2）push_heap在堆的基础上进行插入，要求前面的区间满足堆结构

第一步将插入数据放到容器末尾
push_heap(begin,end,greater<>());

（3）pop_heap将第一个元素和最后一个元素交换位置，对前n-1个元素构造堆

push_heap(begin,end,greater<>());
第二步对数组进行pop_back()操作，删除末尾元素（原来的堆顶）

#include <iostream>
#include <vector>
#include <functional>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    vector<int> ve;
    while(k--){
        int p,x;
        cin>>p;
        if(p==1){
            cin>>x;
            if(ve.size()<n){//记得判断
                ve.push_back(x);
                push_heap(ve.begin(),ve.end(),greater<>());//在堆的基础上进行插入
            }
        }
        else{
            pop_heap(ve.begin(),ve.end(),greater<>());//删除堆顶
            ve.pop_back();//删除末尾元素
        }
        for(int i=0;i<ve.size();i++){
            if(i) cout<<" ";
            cout<<ve[i];
        }
        cout<<endl;
    }
    int m,t;
    cin>>m;
    vector<int> v;
    while(m--){
        cin>>t;
        v.push_back(t);
    }
    make_heap(v.begin(),v.end(),greater<>());//构造小根堆
    for(int i=0;i<v.size();i++){
        if(i) cout<<" ";
        cout<<v[i];
    }
    return 0;
}

7-10哈夫曼编码

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
const int MAX=400;
typedef struct{
    int weight;
    int parent;
    int Lchild;
    int Rchild;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
void select(HuffmanTree ht,int n,int *s1,int *s2){//选择两个weight最小的节点
    int min1=MAX,min2=MAX;
    *s1=0; *s2=0;
    for(int i=1;i<=n;i++){
        if(!ht[i].parent){
            if(ht[i].weight<min1){
                min2=min1;
                *s2=*s1;
                min1=ht[i].weight;
                *s1=i;
            }
            else if(ht[i].weight<min2){
                min2=ht[i].weight;
                *s2=i;
            }
        }
    }
}
void create(HuffmanTree ht,int n){//建树
    for(int i=n+1;i<=2*n-1;i++) //非叶节点初始化
        ht[i].weight=ht[i].parent=ht[i].Lchild=ht[i].Rchild=0;
    int s1,s2;
    for(int i=n+1;i<=2*n-1;i++){//创建非叶节点
        select(ht,i-1,&s1,&s2);//选择两个weight最小的节点，合为一棵树
        ht[i].weight=ht[s1].weight+ht[s2].weight;
        ht[s1].parent=i;
        ht[s2].parent=i;
        ht[i].Lchild=s1;
        ht[i].Rchild=s2;
    }
}
void code(HuffmanTree ht,HuffmanCode &hc,int n){//编码
    char *cd=new char[n];
    cd[n-1]='\0';
    for(int i=1;i<=n;i++){
        int start=n-1,c=i,p=ht[c].parent;//从叶子结点到根，逆向求编码，c为当前节点，p为c的父结点
        while(p){
            --start;//逆序存储
            if(ht[p].Lchild==c) cd[start]='0';//左孩子记0
            else cd[start]='1';//右孩子记1
            c=p;//向上编码
            p=ht[p].parent;
        }
        hc[i]=new char[n-start];//申请空间并存储该字母的哈夫曼编码
        strcpy(hc[i],&cd[start]);
    }
    free(cd);
}
int main(){
    string str;
    while(cin>>str){
        map<char,int> mp;
        for(int i=0;i<(int)str.size();i++){
            mp[tolower(str[i])]++;//统计出现次数
        }
        int n=mp.size();
        HuffmanTree ht=new HTNode[2*n];
        HuffmanCode hc=new char* [n+1];
        int i=1;
        for(auto it=mp.begin();it!=mp.end();it++,i++){//[1,n]存放叶子结点，初始化
            ht[i].parent=ht[i].Lchild=ht[i].Rchild=0;
            ht[i].weight=it->second;
            it->second=i;//标记每个字母在哈夫曼树中对应的位置，便于后续输出
        }
        create(ht,n);
        code(ht,hc,n);
        for(int i=0;i<(int)str.size();i++){
            cout<<hc[mp[tolower(str[i])]];
        }
        cout<<endl;
    }
    return 0;
}