文章目录
前言
考PAT也算是复习下数据结构辣,不算摸鱼把，考前两天突击写了几题树的遍历和AVL树,然而都没有考到（）,晚上写下题目算是记录下。趁着还有点记忆把下午的代码复现一些。有些题可能思路复杂了，见谅。
郑重声明：代码均为第一时间复现，错了自己写去，溜
一、第一题 1A
题目大意:
有两个人, 每个人按yesterday today tomorrow的顺序说出星期几, 星期日到星期六编号为 0~6，而每个人说的数字中只有一个是符合逻辑关系的, 输出今天是星期几（英文）,题目保证了结果唯一,然后每个人对的那个数字是对应的yesterday today tomorrow中的哪个。
输入（大概是这个例子 记不太清）
3 5 6
4 6 2
输出
Friday
today
yesterday
题目思路:
枚举今天是星期几就好了, 其中两者都只有一个对的则为答案。
赛后评价
我会说这题目读了15min么，单词都认识, 意思不理解，我不信真的没人读题的时候卡住QAQ
二、第二题 1A
题目大意
有一个序列长度为M, 块大小为N的LRU, 当LRU块大小满的时候会删除一个在块内最久未被使用的数值,让你输出所有被删除的数值。
（M<=1e5, N<=1e4）数据范围记错了别打我（反正暴力写是肯定不能满分的
题目思路
考虑用数据结构维护, 优先队列不能查询和删除, 而set记录信息又太少。所以可以考虑用map来写, 怎么在O(logN)的复杂度内实现找到最久未被使用的数值呢？
如果我们用map<int,int>, mp.first记录时间节点cnt, mp.second记录在时间点cnt下放入块的数值val。我们让时间id循环的时候自增, 那么查询的mp.begin(), 其first是升序第一个时间节点也就是最久未被使用的,对应的second就是我们要找到的删除的数值。这样还不够, 如果当前数值id[i]在块中, 我们要更新id[i]，如果不在块中，则要删除一个，插入一个。我们需要快速知道数值在不在块中, 那就可以再来一个map<int,int> rev,记录的信息和第一个相反。
关键代码
复现之后的代码差不多是酱紫
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
void solve(){
map<int,int> mp;
map<int,int> rev;
int n, m;
cin >> n >> m;
vector<int> id(m);
for(int i = 0; i < m; i++){
cin >> id[i];
}
int siz = 0; // 记录块中的个数
int cnt = 0; // 时间节点
vector<int> ans;
for(int i = 0; i < m; i++){
cnt++;
if(siz < n){
if(rev.count(id[i])){ // 数值在块中, 更新mp和rev, mp删除之前对应的值
int precnt = rev[id[i]];
mp.erase(precnt);
mp[cnt] = id[i];
rev[id[i]] = cnt;
}else{
mp[cnt] = id[i];
rev[id[i]] = cnt;
siz++;
}
}else{
if(rev.count(id[i])){ // 满的时候, 数值在块中, 只需要更新 不需要删除
int preid = rev[id[i]];
mp.erase(preid);
mp[cnt] = id[i];
rev[id[i]] = cnt;
}else{
map<int,int>::iterator it = mp.begin();
int delcnt = it->first, delval = it->second;
rev.erase(delval);
mp.erase(it);
mp[cnt] = id[i];
rev[id[i]] = cnt;
ans.push_back(delval);
}
}
}
for(int i = 0; i < ans.size(); i++){
if(i) cout << ' ';
cout << ans[i];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
三、第三题 1A
题目大意
给你一张图, 再给你q个dfs序列, 判断每个给定的dfs序列是否合法。并且当dfs到链的底部时，可以选择其他节点作为起点继续dfs, 而不是返回。例如 给你这样一个图 1->2->3->4->5，dfs序3,4,5,1,2是合法的，因为dfs走到5的时候没有边给它走了，可以重新选取一个没走过的节点。题目范围明显是要你按照题意模拟下是否可行。
题目思路
大概的关键代码如下，代码为处理一次dfs序列的合法性。只提供参考, 全部代码想不起来Orz
vector<int> vec[maxn];
vector<int> path; // path为一个dfs序列
vector<bool> vis; // vis为节点的标记, false为未遍历过, true为遍历过
int p;
bool ans = true;
void dfs(int u, int p){
if(p == n - 1){
return;
}
int cnt = 0;
bool ok = false; // ok来标记节点u能不能遍历下一个dfs序的节点v
for(int i = 0; i < vec[u].size(); i++){
int v = vec[u][v];
if(vis[v]) continue;
cnt++;
if(path[p + 1] == v){
ok = true;
vis[path[p + 1]] = 1;
dfs(v, p + 1);
}
}
if(!ok && cnt > 0){ // 如果有其他顶点没遍历但没有走dfs序的下一个点, 说明序列不合法
ans = false;
return;
}else if(!ok && cnt == 0){ // 说明走到头了, 可以选取其他节点作为dfs的起点,看下一个dfs序的节点有没有走过
if(!vis[path[p + 1]]){
vis[path[p + 1]] = 1;
dfs(path[p + 1], p + 1);
}
}
}
int main(){
p = 0;
vis[p] = 1;
dfs(path[p],p);
}
赛后评价
写的时候细节蛮多的, 铸币犯了个经典错误, 定义全局，变量调用了局部导致运行崩溃, 楞了好几分钟
四、第四题 4A
题目大意
题目讲了完全k叉树, N个顶点, 给你这个完全k叉树的前序遍历, 要求输出层序遍历的顺序, 并依据层序遍历的顺序(下标为0~n-1) 询问下标为q[i]的节点, 从它到根节点的路径。（N<=50, 2<=k<=5）
题目思路
记得二叉树是能数组实现，但是多叉树这个下标就很难搞，所以还是老老实实写指针的写法。考虑k叉树, 每一层的个数, 分别是1, k, k^2…,又是完全k叉树，所以我们能算出树的最大深度maxdep, 在前序建树的时候建的深度不能大于maxdep。而如果建树的时候写假了就可能会出现上一层不是满的,而那个缺的节点接到下一层了。（说的就是本人, 假思路写了1小时wa3发）
上图中蓝色的节点为正确的接法，而在建树的时候可能会建到红色的节点。原因是我们没有正确检验能否在那个位置插入节点。考虑按树的层序顺序对节点进行编号，因为是完全的树,如下图。
这个图有9个节点, 而红色的节点位置编号为10,显然是大于了n。那么我们只需要考虑计算插入节点的编号是否<=n即可正确建树。
对于当前节点root, 插入的节点为它的child, 计算节点的编号就为, 前几层树满节点时候的个数 + 当前层有的个数 + 1 <= n, 为此我们需要计算一个 前i层满节点的个数即前缀sumcnt, 还需要计算下当前每一层的节点个数 levelcnt。
关键代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, d;
int pre[maxn]; // 前序输入
int p = 0, maxdep = 1;
vector<int> sumcnt; // k叉树前i层节点个数的前缀
vector<int> levelcnt(110, 0); // 当前每一层的节点个数
struct Node{
int value;
vector<Node*> child;
Node* fa;
Node(int value, Node* fa) : value(value), child(vector<Node*>(d, NULL)), fa(fa) {}
};
bool check(int dep, int cnt){ // 判断当前位置的节点能否生成
return sumcnt[dep] + cnt <= n;
}
void preorder(Node* &root, int dep, Node* fa){
if(root == NULL){
root = new Node(pre[p++], fa);
levelcnt[dep]++;
if(p == n + 1) return ;
}
for(int i = 0; i < d; i++){
if(dep + 1 <= maxdep && check(dep, levelcnt[dep + 1] + 1)){ /*
下一层的节点能否生成 取决于 下一个节点在这个树中的位置编号是否<= n, 即 sumcnt[dep] + levelcnt[dep + 1] + 1 <= n
*/
preorder(root->child[i], dep + 1, root);
}
}
}
void solve(){
cin >> n >> d;
long long val = 1, sum = 1;
sumcnt.push_back(0);
while(sum < n){
maxdep++;
val = val * d;
sum += val;
}
sumcnt.resize(maxdep + 5);
Node* root = NULL;
p = 1;
for(int i = 1; i <= n; i++){
cin >> pre[i];
}
preorder(root, 1, NULL);
// 剩下的层序遍历和输出路径就不写了,聪明的你动动脑筋把（）
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
都看到最后了不给点个赞嘛QAQ