7-1 Arrays and Linked Lists (20 分)

在这里插入图片描述

C++ code

#include<bits/stdc++.h>
using namespace std;
struct Array{
	int beg, length;
}; 

vector<Array> vec;
int last = 1;
int main(){
	int n, k;
	cin>>n>>k;
	for(int i = 0;i<n;++i){
		int ad, len;
		cin>>ad>>len;
		vec.push_back({ad, len});
	}
	
	for(int i = 0;i<k;++i){// 查询 
		bool find = false;
		int id;
		cin>>id;
		int ctr = 0;
		for(int j = 0;j<vec.size();++j){
			ctr += vec[j].length;//统计累加长度 
			
			if(ctr >= id + 1){//能够接受 
				cout<<vec[j].beg + 4*(id - (ctr - vec[j].length))<<"\n";
				find = true;
				last = max(last, j+1);// 最多用了5个数组 
				break;
			}
		}
		if(!find) cout<<"ILLegal Access\n";
	}
	cout<<last;
}

7-2 Stack of Hats (25 分)

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;

struct Man{
	int id;
	int weight;
}man[N];

struct Hat{
	int ctr;
	int size;
	int belong;
}hat[N];

int main(){
	int n;
	cin>>n;
	for(int i = 0;i<n;++i){
		cin>>hat[i].size;
		hat[i].ctr = n - 1 - i; // 记录位置 
	}
	for(int i = 0;i<n;++i){
		man[i].id = i + 1;//记录拿取顺序 
		cin>>man[i].weight; 
	}
	
	sort(man,man+N,[](Man &a,Man &b){
		return a.weight > b.weight;
	});
	
	sort(hat,hat+N,[](Hat &a,Hat &b){
		return a.size < b.size;
	});
	
	for(int i = 0;i<n;++i){
		hat[i].belong = man[i].id;
	}
	
	sort(hat, hat+n,[](Hat &a,Hat &b){
		return a.ctr < b.ctr;
	});
	
	for(int i = 0;i<n;++i){
		if(i!=0) cout<<" ";
		cout<<hat[i].belong; 
	}
}

7-3 Playground Exploration (25 分)

在这里插入图片描述

C++ code

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
set<int> graph[N];
int ans_beg = 0, ans = 0;
int vis[N];

void DFS(int now, int num, int beg){
	if(graph[now].size()==0){//没有其他连通边 
		fin:
			if(num>ans){
				ans = num, ans_beg = beg;
			}else if(num==ans){
				beg = min(beg, ans_beg);
			}
			return;
	}
	bool no_next = true;
	for(auto to:graph[now]){
		if(!vis[to]){
			no_next = false;
			vis[to] = true;
			DFS(to, num + 1, beg);
			break; 
		}
	}
	if(no_next) goto fin;
} 

int main(){
	int n, m;
	cin>>n>>m;
	
//	建立图关系 
	for(int i = 0;i<m;++i){
		int x, y;
		cin>>x>>y;
		graph[x].insert(y);
		graph[y].insert(x);
	}
	
	for(int i = 1;i<=n;++i){
		memset(vis, false, sizeof(vis));
		vis[i] = true;
		DFS(i, 1, i);
	}
	cout<<ans_beg<<" "<<ans;
}

7-4 Sorted Cartesian Tree (30 分)

在这里插入图片描述

C++

#include<bits/stdc++.h>
using namespace std;
int lchild[50], rchild[50];

struct Node{
    int key, pri;
    Node(int _key = 0, int _pri = 0):key(_key), pri(_pri){}
}node[50];

int Build(int l, int r){
    if(l>r) return -1;
    int root = l;
    for(int i = l;i<=r;++i){
        if(node[i].pri < node[root].pri){//总是选到最小的且按照中序遍历顺序做根节点
            root = i;
        }
    }
    lchild[root] = Build(l,root-1);
    rchild[root] = Build(root+1,r);
    return root;

}
// 记录第几个答案
vector<int> ans;

// 层次遍历
void BFS(int root){
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        ans.push_back(now);

        if(lchild[now]!=-1) q.push(lchild[now]);
        if(rchild[now]!=-1) q.push(rchild[now]);
    }
}

int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;++i){
        cin>>node[i].key>>node[i].pri;
    }

// 中序遍历是增序
    sort(node, node+n, [](Node &a, Node &b){
        return a.key < b.key;
    });

    int root = Build(0,n-1);//按优先级建堆
    BFS(root);

    for(int i = 0;i<ans.size();++i){
        if(i!=0) cout<<" ";
        cout<<node[ans[i]].key;
    }
    cout<<"\n";
    for(int i = 0;i<ans.size();++i){
        if(i!=0) cout<<" ";
        cout<<node[ans[i]].pri;
    }
}