PAT复习自用——做题解和写过代码的搬运工
//基础数据结构（二）：树
/*
前言：反复训练，核心章节，拿到问题先去考虑是搜索还是研究性质
*/
---------------------------------
//基本工具
struct Node
{
int lchild,rchild;
}Btree[N];
struct Node
{
vector<int>child;//树和图的存储结构都可以使用邻接表，这种存储方式十分好用
}tree[N];
int l[N],r[N],p[N];//当没有给出根节点的时候，需要通过遍历p数组看看谁没有祖先，就是根节点
****//核心考点：遍历序列建树
vector<int>seq,pre,post,in;//常用seq存储节点访问序列
unordered_map<int,int> pos;//元素在中序序列中的位置，哈希做法快速建树
int build(int inL,int inR,int preL,int preR);
int build(int inL,int inR,int poL,int poR);
void inorder();//下面这三种遍历都是基于递归的
void preorder();
void postorder();
void layorder();
void bfs();//通常情况下就是layorder函数
void dfs(int root);//dfs求树高
//求连通块个数：用并查集最方便
--------------------------------------------
/*
（一）树的bfs和dfs---搜索问题
*/
//模板
void bfs(int root)
{
queue<int>q;
q.push(root);
while(!q.empty())
{
int top = q.front();
q.pop();
//访问当前结点的语句
for(auto c:tree[top].child)//这里如果使用邻接矩阵访问可能会超时
{
q.push(c);
/*修改孩子节点性质的语句*/
}
}
}
void dfs(int root)
{
//先定义属性值
//定义返回条件
for(auto c:child[root])dfs(c);
//return;
}
//二叉树dfs---遍历序列
void inorder(int root)
{
if(root==-1)return;
inorder(l[root]);
cout<<seq[root]<<" ";
inorder(r[root]);
}
//前序和后序遍历同inorder递归，修改递归顺序即可
//层序遍历同bfs
----------------------------------
//典型bfs和dfs问题
//dfs求树高，每一次遍历需要重置st数组
//注意要使用st数组防止无向边的回溯引发的内存超限（因为无向边会走回来）
int dfs(int root)
{
int deepth = 0;
st[root] = true;
for(auto c:child[root])
if(!st[c])deepth = max(deepth,dfs(c)+1);
return deepth;
}
//可以增加一个标记来标识不会向上搜索
int dfs(int root,int father)
{
int deepth = 0;
if(child[root].size()==0)return deepth;
for(auto c:child[root])
if(c!=father)deepth = max(deepth,dfs(c,root)+1);
return deepth;
}
//bfs求树高,每一次遍历需要重置st数组,时空复杂度均略高于dfs
int bfs(int root)
{
queue<int>q;
q.push(root);
int deepth = 0;
d[root] = 0;
while(!q.empty())
{
int top = q.front();
q.pop();
deepth = max(deepth,d[top]);
st[top] = true;
for(auto c:child[top])
if(!st[c])q.push(c),d[c] = d[top]+1;
}
return deepth;
}
//PAT-1021 最深的根 揭示了树和图的关系，无环图是树，因此先用并查集检测环，再做dfs或者bfs
bool check_cycle()
{
int cnt = n;
for(int i = 0;i<m;i++)//遍历边
{
int a = e[i].x,b = e[i].y;
if(find(a)!=find(b))cnt--,p[find(a)] = find(b);
}
if(cnt>1)return false;
else return true;
}
//PAT-1004 数叶子节点 bfs模板题（求树的各层宽度变体）
//PAT-1127 Z字形遍历二叉树 bfs模板题+序列建树模板题
//PAT-1138 后序遍历 序列建树模板题
//PAT-1094 最大的一代 bfs模板题
//PAT-供应链家族题 1079（供应链销售总额）、1090（整个树最大值）、1106（叶节点最小值）
//皆为bfs模板题，只需要改几个参数即可
//简便写法为树形dp，又叫记忆化搜索，需要初始化所有节点的f[u] = -1
//以供应链销售总额为例，计算树中可以销售节点的深度
int dfs(int u)
{
if(f[u]!=-1)return f[u];//当前结点计算过
if(p[u]==-1)return f[u] = 0;//未达到根节点，不能出售
return f[u] = dfs(p[u])+1;//这里无法保证按照顺序进行dp，故只能dfs(p[u])，而不是f[p[u]]
}
for (int i = 0; i < n; i ++ )
if (c[i])
res += c[i] * P * pow(1 + R / 100, dfs(i));
//1090-供应链最大值
int dfs(int u)
{
if(u==-1)return 0;
if(f[u]!=-1)return f[u];
return f[u] = dfs(p[u])+1;
}
for(int i = 0;i<n;i++)maxlay = max(dfs(i),maxlay);
for(int i = 0;i<n;i++)if(f[i]==maxlay)cnt++;
printf("%.2lf %d",P*pow(1+r/100,maxlay-1),cnt);
-----------------------------
//PAT-1053 等重路径 dfs搜索,记录方案
int dfs(int weight,int root)
{
temp.push_back(w[root]);//dfs记录路径典型操作
if(weight==s&&child[root].size()==0)res.push_back(temp);
if(weight<s&&child[root].size())
for(auto c:child[root])
dfs(weight+w[c],c);
temp.pop_back();//容易忘记
}
//PAT-1155 堆路径 dfs搜索
bool gt,lt;//使用两个标记标明路径上序列的性质是否存在递增或递减，若都存在，则不为堆
bool dfs(int u)
{
path.push_back(tree[u]);
if(u*2>n)//到达叶节点
{
for(int i = 0;i<path.size();i++)
{
cout<<path[i];
if(i!=path.size()-1)cout<<" ";
if(i&&path[i]>path[i-1])lt = true;//检查递增或递减
else if(i&&path[i]<path[i-1])gt = true;
}
cout<<endl;
}
if(u*2+1<=n)dfs(u*2+1);
if(u*2<=n)dfs(u*2);
path.pop_back();
}
-----------------------------
//前缀表达式，中缀表达式，后缀表达式分别对应前序遍历，中序遍历，后序遍历
//注意括号在递归遍历该表达式树时，要打印出来，这类题目在命制的时候都要自己找根节点，使用p数组记录即可
void dfs(int u)
{
if((tree[u].rchild!=-1||tree[u].lchild!=-1)&&
u!=root)cout<<"(";
if(tree[u].lchild!=-1)dfs(tree[u].lchild);
cout<<tree[u].c;
if(tree[u].rchild!=-1)dfs(tree[u].rchild);
if((tree[u].rchild!=-1||tree[u].lchild!=-1)&&
u!=root)cout<<")";
}
void postorder(int root)//后缀表达式
{
cout << "(";
if (Tree[root].lchild==-1&&Tree[root].rchild!=-1)//针对数据中的'-'特例耍点小聪明，特判一下，这个单目运算符
{
cout << Tree[root].data;
if (Tree[root].lchild != -1)postorder(Tree[root].lchild);
if (Tree[root].rchild != -1)postorder(Tree[root].rchild);
}
else
{
if (Tree[root].lchild != -1)postorder(Tree[root].lchild);
if (Tree[root].rchild != -1)postorder(Tree[root].rchild);
cout << Tree[root].data;
}
cout << ")";
}
//镜像遍历--- PAT-1102 反转二叉树
//PAT-1110 完全二叉树的判断 dfs搜索，找到最大id看是否==n
void dfs(int u,int id)
{
maxcnt = max(id,maxcnt);
if(l[u])dfs(l[u],id*2);
if(r[u])dfs(r[u],id*2+1);
}
/*
树的宽度
*/
void bfs()
{
queue<int>q;
q.push(root);
while(!q.empty())
{
int len = q.size();
width = max(len,width);
while(len--)
{
int p = q.front();
q.pop();
if(l[p])q.push(l[p]);
if(r[p])q.push(r[p]);
}
}
}
/*
树的重心
*/
#include<iostream>
#include<vector>
using namespace std;
const int N = 1001;
int n,pos,ans = 0x3f3f3f3f,num[N];
vector<int> child[N];
void dfs(int x)
{
num[x] = 1;
int max_part = 0;
for(auto c:child[x])
{
dfs(c);//自底向上计算
num[x]+=num[c];
max_part = max(max_part,num[c]);//统计子树的最大个数
}
max_part = max(n-num[x],max_part);//当前结点祖先的子树个数=n-num[x]
if(max_part<ans)
{
ans = max_part;
pos = x;
}
}
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{
int cnt;
cin>>cnt;
while(cnt--)
{
int x;cin>>x;
child[i].push_back(x);
}
}
dfs(1);
cout<<pos<<endl;
}
------------------------------------------
/*
（二）序列建树---不必使用动态方式，只需要静态维护数组即可，基本操作，通常为解题第一步
*/
//模板
for(int i = 0;i<n;i++)cin>>po[i];
for(int i = 0;i<n;i++){cin>>in[i];pos[in[i]] = i;}//哈希建树
//后序+中序建树
int build(int il,int ir,int pol,int por)
{
int root = po[por],k = pos[root];
if(k>il)l[root] = build(il,k-1,pol,pol+k-1-il);
if(k<ir)r[root] = build(k+1,ir,pol+k-il,por-1);
//类似的写法还有,如果只需要维护祖宗节点（如LCA问题求解）
//if(k>il) p[build(il,k-1,pol,pol+k-1-il)] = root;
//if(k<ir) p[build(k+1,ir,pol+k-i-il,por-1)] = root;
return root;
}
//PAT-1020 树的遍历 模板题
------------------------------------
//PAT-1119 前序和后序遍历 使用序列建树和dfs搜索结合，在考虑dfs的时候，枚举孩子区间的长度，同时要求
//两个序列对应的根相同，在出现多组解的时候及时剪枝，另外，递归的最初子结果是当为空树时返回1，表明一定存在
********************************
int dfs(int pl,int pr,int pol,int por,string &res)
{
if(pl>pr)return 1;
if(pre[pl]!=post[por])return 0;
int cnt = 0;
for(int i = pl;i<=pr;i++)
{
string lin,rin;
int lcnt = dfs(pl+1,i,pol,pol+i-pl-1,lin);
int rcnt = dfs(i+1,pr,pol+i-pl,por-1,rin);
if(lcnt&&rcnt)
{
res = lin+to_string(pre[pl])+" "+rin;
cnt+=lcnt*rcnt;
if(cnt>1)break;
}
}
return cnt;
}
//树的同构——只要祖先一样就可以，本题源自浙大教材的上机练习，麻烦之处在于处理字母映射的输入
#include<iostream>
#include<map>
using namespace std;
const int N = 100;
map<char,char>p;
struct edge
{
char a,b,c;
}e[N];
int main()
{
int n1,n2;cin>>n1;
char t;
for(int i = 0;i<n1;i++)
{
char a,b,c;cin>>a>>b>>c;
e[i] = {a,b,c};
if(n1==1)t = a;
}
for(int i = 0;i<n1;i++)
{
char a = e[i].a,b = e[i].b,c = e[i].c;
int db = b-'0',dc = c-'0';
if(db<=9&&db>=0)p[e[db].a] = a;
if(dc<=9&&dc>=0)p[e[dc].a] = a;
}
cin>>n2;
for(int i = 0;i<n2;i++)
{
char a,b,c;cin>>a>>b>>c;
e[i] = {a,b,c};
}
bool flag = true;
for(int i = 0;i<n2;i++)
{
char a = e[i].a,b = e[i].b,c = e[i].c;
int db = b-'0',dc = c-'0';
if(db<=9&&db>=0&&p[e[db].a]!=a)flag = false;
if(dc<=9&&dc>=0&&p[e[dc].a]!=a)flag = false;
}
if(n1!=n2)flag = false;
if(n1==n2&&n1==1)if(e[0].a!=t)flag = false;
if(flag)puts("Yes");
else puts("No");
return 0;
}
------------------------------------
/*
（三）搜索树----用性质解题
*/
/*
重要性质：
注意搜索树的定义是左子树小于等于还是小于
二叉搜索树的典型结构----STL的set，可以直接输出前驱后继
二叉搜索树的中序遍历为有序序列，故建立二叉搜索树的时候隐含了一个中序序列
（题目一般给出前序序列，sort一下得到中序）根据这两个序列可以建树
完全二叉搜索树用一维数组存储，如典型的堆，这个一维数组存储层序序列
*/
/*
如何构建这棵二叉树呢？
总的来说，第一种思路就是按照插入序列，还原这棵树，还原方式有两种
1）使用一维数组，按照层序存储节点值，-------如PAT-1043 判断二叉搜索树
根为0的时候每次插入到左子树的下标为u*2+1，右子树为u*2+2
根为1的时候每次插入到左子树的下标为u*2，右子树为u*2+1
插入即按照搜索树的定义，当查找到空节点（tree[idx]==0）时给他赋值
这种方法时间复杂度较高，空间复杂度也较高（优化方法使用map-PAT-1115二叉搜索树的最后两层节点）
2）事先sort一下插入序列，得到中序序列，得到了前序序列（即插入序列）和中序序列，可以建树
维护的结构是l[N],r[N] -------PAT-1043 判断二叉搜索树可以使用该方法，效率比1高一点
另外，如果给出了树的形态：需要按照中序序列按照顺序填这棵树，填的方法就是中序遍历,tree[pos] = seq[idx++]
如给出的树是完全二叉树（对应上述的（1）情况），则按照层序的编号递归-----如PAT-1064 构建完全二叉搜索树
如给出具体的节点信息，则按照原先的位置关系递归----如PAT-1099 构建二叉搜索树
*/
/*
PAT-1043 判断二叉搜索树 探究二叉搜索树的层序存储方式和二叉树的递归遍历序列的关系，重点题型
当定义为左子树小于根节点的时候，哈希中序位置要取第一个位置，故记录的时候要记录第一个出现的位置，即较小的下标
如 1 2 3 4 5 5 6 7 8 pos[5] = 4;
而定义为左子树小于等于的时候，两个位置均可，当然此时题目答案不唯一了
*/
bool build(int il, int ir, int pl, int pr, int type)
{
if (il > ir) return true;
int root = preorder[pl];
int k;
if (type == 0)
{
for (k = il; k <= ir; k ++ )
if (inorder[k] == root)
break;
if (k > ir) return false;
}
else
{
for (k = ir; k >= il; k -- )
if (inorder[k] == root)
break;
if (k < il) return false;
}
bool res = true;
if (!build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), type)) res = false;
if (!build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr, type)) res = false;
postorder[cnt ++ ] = root;
return res;
}
----------------------------------------
const int N = 10100;//需要设大一点，因为题给的可能达到2^n
int n, tree[N * N];//层序存储搜索树
void insert(int x, int pos)//插入序列就是先根的顺序，这一点莫名的符合了
{
if (tree[pos] == 0)tree[pos] = x;
else if (tree[pos] <= x)insert(x, pos * 2+1);
else insert(x, pos * 2);
}
void postorder(int u,int type)//需要根据题意输出是镜像还是原来顺序
{
if(type==0){
if (tree[u] == 0)return;
postorder(u * 2,type);
postorder(u * 2 + 1,type);
cout << tree[u] << " ";
}
else
{
if (tree[u] == 0)return;
postorder(u * 2+1,type);
postorder(u * 2,type);
cout << tree[u] << " ";
}
}
void preorder(int u, vector<int>& seq,int type)
{
if (tree[u] == 0)return;
seq.push_back(tree[u]);
if(type==0)//顺序序列
{
preorder(u * 2, seq,type);
preorder(u * 2 + 1, seq,type);
}
else//镜像序列
{
preorder(u*2+1,seq,type);
preorder(u*2,seq,type);
}
}
int main()
{
cin >> n;
vector<int> input, seq, reseq;
memset(tree, 0, n + 1);
for (int i = 1; i <= n; i++)
{
int x; cin >> x;
insert(x, 1);
input.push_back(x);
}
preorder(1, seq,0);
if (seq == input)
{
cout << "YES" << endl;
postorder(1,0);
}
else
{
preorder(1, reseq,1);
if (reseq == input)
{
cout << "YES" << endl;
postorder(1,1);
}
else cout << "NO" << endl;
}
return 0;
}
--------------------------
//PAT-1064 完全二叉搜索树
/*
和上题不同的是，如果给定一系列点的权值，得到的完全二叉树却是唯一的，而不再需要插入序列的辅助
只需要根据节点权值便可以重建完全二叉搜索树
本题抓住了中序序列是升序，而每一个元素唯一对应完全二叉搜索树的位置，故只需要按照上题的递归方式
深入到正确位置，按顺序填入升序序列的值即可
*/
int idx = 0,n;
vector<int>seq;
const int N = 10010;
int res[N*N];
void inorder(int pos)
{
if(pos>=n)return ;
inorder(pos*2+1);
res[pos] = seq[idx++];
inorder(pos*2+2);
}
int main()
{
cin>>n;
for(int i = 0;i<n;i++){int x;cin>>x;seq.push_back(x);}
sort(seq.begin(),seq.end());
inorder(0);
for(int i = 0;i<n;i++)cout<<res[i]<<" ";
return 0;
}
-------------------
//PAT-1086 再次树遍历，考查非递归版本树的遍历，需要复习
***************************************
//解法一：前序遍历是push顺序，中序遍历是pop顺序，抓住这个性质，建树即可
int l[100],r[100];
stack<int>s;
unordered_map<int,int>pos;
vector<int> pre,in;
int build(int il,int ir,int pl,int pr)
{
int root = pre[pl],k = pos[root];
if(il<k)l[root] = build(il,k-1,pl+1,pl+1+k-1-il);
if(k<ir)r[root] = build(k+1,ir,pr-(ir-k-1),pr);
return root;
}
void postorder(int root)
{
if(l[root])postorder(l[root]);
if(r[root])postorder(r[root]);
cout<<root<<" ";
}
int main()
{
int n;cin>>n;
for(int i = 0;i<n*2;i++)
{
string q;cin>>q;
if(q=="Push")
{
int x;cin>>x;
s.push(x);
pre.push_back(x);
}
else
{
int top = s.top();
s.pop();
in.push_back(top);
pos[in[in.size()-1]] = in.size()-1;
}
}
int root = build(0,n-1,0,n-1);
postorder(root);
return 0;
}
//解法二：熟知非递归求解方法就可以发现规律，每次push之后，下个节点是左孩子，pop之后，下个节点是右孩子
//这个思路很难想到，需要已知非递归求解方法
//https://www.acwing.com/activity/content/code/content/279748/
*****************************
/*代码待补充*/
//非递归中序遍历版本
/*
这里的思路在于按照树的递归遍历方式，第一次访问的元素是先序遍历，第二次访问元素是中序遍历
第三次访问是后序遍历，按照这个顺序定义标记数组，第二次访问到的元素放入
浙大课件上的操作是使用一个指针描述当前访问结点，第一次访问入栈，第二次访问出栈并查看右子树
而我下面的实现方式第一个是第一次写不确定正确性的版本
第二个比较好理解的课本操作
*/
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int N = 100;
int n,l[N],r[N],p[N];
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{
cin>>l[i]>>r[i];
if(l[i]!=0)p[l[i]] = i;
if(r[i]!=0)p[r[i]] = i;
}
int root = 0;
for(int i = 1;i<=n;i++)
if(p[i]==0)root = i;
stack<int> stk;
stk.push(root);
bool st[N];vector<int>res;
while(stk.size())
{
int t = stk.top();
if(!st[t])st[t] = true;
else res.push_back(t),stk.pop();
if(l[t])
{
if(!st[l[t]])stk.push(l[t]);
else if(r[t])stk.push(r[t]);
}
else if(l[t]==0&&r[t]&&!st[r[t]])stk.push(r[t]);
}
for(auto c:res)cout<<c<<" ";
cout<<endl;
return 0;
}
----------//正确版
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int N = 100;
int n,l[N],r[N],p[N];
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{
cin>>l[i]>>r[i];
if(l[i]!=0)p[l[i]] = i;
if(r[i]!=0)p[r[i]] = i;
}
int root = 0;
for(int i = 1;i<=n;i++)
if(p[i]==0)root = i;
stack<int> stk;
stk.push(root);
bool st[N];vector<int>res;
while(stk.size())//可以保证每次只压入一个节点，也就相当于dfs访问的模拟
{
int t = stk.top();
if(!st[t])
{
st[t] = true;
if(l[t])stk.push(l[t]);
}
else
{
res.push_back(t);
stk.pop();
if(r[t])stk.push(r[t]);
}
}
for(auto c:res)cout<<c<<" ";
cout<<endl;
return 0;
}
-----------------------
//非递归先序遍历版本
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int N = 100;
int n,l[N],r[N],p[N];
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{
cin>>l[i]>>r[i];
if(l[i]!=0)p[l[i]] = i;
if(r[i]!=0)p[r[i]] = i;
}
int root = 0;
for(int i = 1;i<=n;i++)
if(p[i]==0)root = i;
stack<int> stk;
stk.push(root);
bool st[N];vector<int>res;
while(stk.size())
{
int t = stk.top();
if(!st[t])
{
res.push_back(t);
st[t] = true;
if(l[t])stk.push(l[t]);
}
else
{
//res.push_back(t);
stk.pop();
if(r[t])stk.push(r[t]);
}
}
for(auto c:res)cout<<c<<" ";
cout<<endl;
return 0;
}
//非递归后序遍历版本
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int N = 100;
int n,l[N],r[N],p[N];
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{
cin>>l[i]>>r[i];
if(l[i]!=0)p[l[i]] = i;
if(r[i]!=0)p[r[i]] = i;
}
int root = 0;
for(int i = 1;i<=n;i++)
if(p[i]==0)root = i;
stack<int> stk;
int st[N],u = root;vector<int>res;
while(stk.size()||u)
{
while(u!=0)
{
st[u]=1;
stk.push(u);
u = l[u];
}
u = stk.top();
if(st[u]==1)
{
st[u] = 2;
u = r[u];
}
else
{
u = stk.top();
stk.pop();
res.push_back(u);
u = 0;
}
}
for(auto c:res)cout<<c<<" ";
cout<<endl;
return 0;
}
-----------------------
//PAT-1099 构建二叉搜索树
/*
这里建立二叉搜索树的方式同1064，只不过这里递归的线索是事先建立好的l[N],r[N]
给定树的形态，填二叉搜索树仅仅需要中序遍历序列
使用了map存储原节点对应的值
*/
unordered_map<int,int>value;
const int N = 10100;
int seq[N],idx = 0,l[N],r[N];
void inorder(int id)
{
if(id==-1)return;
inorder(l[id]);
value[id] = seq[idx++];
inorder(r[id]);
}
void bfs()
{
queue<int>q;
q.push(0);
while(!q.empty())
{
int top = q.front();
q.pop();
cout<<value[top]<<" ";
if(l[top]!=-1)q.push(l[top]);
if(r[top]!=-1)q.push(r[top]);
}
}
int main()
{
int n;cin>>n;
memset(l,-1,sizeof l);
memset(r,-1,sizeof r);
for(int i = 0;i<n;i++)cin>>l[i]>>r[i];
for(int i = 0;i<n;i++)cin>>seq[i];
sort(seq,seq+n);
inorder(0);
bfs();
return 0;
}
--------------
//PAT-1115二叉搜索树的最后两层节点
unordered_map<int,int> tree;
void insert(int x,int idx)
{
if(!tree.count(idx)){tree[idx] = x;return;}
if(tree[idx]>x)insert(x,idx*2);
else insert(x,idx*2+1);
}
bfs()......//维护d数组，存储每一层的叶子节点个数，还需要维护最大深度
--------------------------------------------------
//新定义题型：PAT-2019 winter-笛卡尔树，背景仍然是二叉搜索树，但是插入操作的动态调整需要手动模拟去探索
//定义是整棵堆序树的中序序列是插入顺序
/*
笛卡尔树的构造：
（1）从第一个元素开始，从左往右遍历数组L
（2）将元素L[0]作为树的根节点R
（3）for i in [a[1], a[2]...a[n]]
（4）如果a[i]小于根节点R，则将a[i]作为根节点R的父节点
（5）如果a[i]大于根节点R，则将a[i]从根节点的右节点开始寻找位置
（6）从右寻找的逻辑同根节点的对比方法
笛卡尔树的性质：若key表示插入序列的下标，value表示值，则key的性质满足二叉搜索树，value的性质满足堆
笛卡尔树的应用---HDU 1506
*/
void dfs(int now,int next)
{
if(seq[now]<seq[next])
{
if(rchild[now]!=-1)dfs(rchild[now],next);
else {rchild[now] = next;father[next] = now;}
}
else
{
if(now!=root)
{
int p = father[now];
rchild[p] = next;
father[now] = next;
lchild[next] = now;
rchild[next] = -1;
father[next] = p;
}
else
{
root = next;
father[now] = next;
lchild[next] = now;
rchild[next] = -1;
}
}
}
--------------------------------------------------
/*
（四）平衡搜索树
*/
/*
重点是AVL树的基本操作，一般把模板默写出来即可
*/
//AVL 模板
int l[N],r[N],v[N],h[N],idx;
void update(int u)
{
h[u] = max(h[l[u]],h[r[u]])+1;
}
void R(int &u)
{
int p = l[u];
l[u] = r[p],r[p] = u;
update(u),update(p);
u = p;
}
void L(int &u)
{
int p = r[u];
r[u] = l[p],l[p] = u;
update(u),update(p);
u = p;
}
int get_balance(int u)
{
return h[l[u]]-h[r[u]];
}
void insert(int &u,int w)
{
if(!u)u = ++idx,v[u] = w;
else if(w<v[u])
{
insert(l[u],w);
if(get_balance(u)==2)
{
if(get_balance(l[u])==1)R(u);
else L(l[u]),R(u);
}
}
else
{
insert(r[u],w);
if(get_balance(u)==-2)
{
if(get_balance(r[u])==-1)L(u);
else R(r[u]),L(u);
}
}
update(u);
}
----------------------------------------------
//红黑树---曾考过一次模拟红黑树的题目，不要求掌握直接实现红黑树的代码
//PAT-1135 判断红黑树
/*
它具有以下 5 个属性：
节点是红色或黑色。
根节点是黑色。---条件1
所有叶子都是黑色。（叶子是 NULL节点）---条件2 不用判断，因为叶子节点是NULL
每个红色节点的两个子节点都是黑色。 ---条件3
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。---条件4
*/
//后序遍历判断子树上的黑色节点是否一致
int postorder(int u)
{
if(u==0)return 0;
int lnum = postorder(l[u]);
int rnum = postorder(r[u]);
if(l<0||r<0||l!=r)return -1;//-1表示黑色节点不平衡，三个条件分别对应左节点不平衡，右节点不平衡，当前结点不平衡
else if(v[u]<0)return lnum;//当前是红色节点
else return lnum+1;//当前是黑色节点
}
//前序遍历判断是否有两个连续的红色节点
int preorder(int u)
{
if(u==0)return 0;
if(v[u]<0)
{
if(l[u]&&v[l[u]]<0)return 1;
if(r[u]&&v[r[u]]<0)return 1;
}
return preorder(l[u])||preorder(r[u]);
}
------------------------------------------------
//浙大 2019保研上机考试：Is It An AVL Tree
/*
如果只需要判断这棵树是否是AVL树，则只需要建立这棵树之后遍历每个节点判断高度差是否小于1即可
*/
int build(int il,int ir,int pl,int pr,int deepth)
{
int root = pre[pl],k = pos[root];
h[root] = deepth;
if(il<k)l[root] = build(il,k-1,pl+1,pl+1+k-1-il,deepth+1);
if(k<ir)r[root] = build(k+1,ir,pl+k-il+1,pr,deepth+1);
return root;
}
bool flag = true;
void dfs(int u)
{
if(h[l[u]]-h[r[u]]<-1||h[l[u]]-h[r[u]]>1)flag = false;
if(l[u])dfs(l[u]);
if(r[u])dfs(r[u]);
}
if(flag==false)puts("No");
else puts("Yes");
------------------------------------------------
/*
（五）LCA 最近公共祖先
*/
/*
只需要掌握朴素做法，即维护p和深度，因此建树的操作可以如下修改实现
*/
//PAT-1143 最近公共祖先
int build(int inL,int inR,int preL,int preR,int depth)
{
int root = preorder[preL];
int k = root;
d[root] = depth;
if(inL<k)p[build(inL,k-1,preL+1,preL+1+k-1-inL,depth+1)] = root;
if(k<inR)p[build(k+1,inR,preL+k-inL+1,preR,depth+1)] = root;
return root;
}
//在main函数中需要做离散化数据处理----因为题给节点的值在int范围内，静态存储不合适
for (int i = 0; i < n; i ++ )
{
cin >> pre[i];
seq[i] = pre[i];//seq[i]存储 idx---value
}
sort(seq, seq + n);//即索引方式为value的排名
for (int i = 0; i < n; i ++ )
{
pos[seq[i]] = i;//记录在中序遍历中的位置
in[i] = i;//中序的下标就是自然序列
}
for (int i = 0; i < n; i ++ ) pre[i] = pos[pre[i]];//离散化
build(0, n - 1, 0, n - 1, 0);
//使用直接插入建树，需要维护index和value的两张表，以及深度表，祖先直接使用idx关系即可
//时间可能会超限---使用map较费时
#define parent(idx) idx%2==0?idx>>1:(idx-1)>>1
unordered_map<int,int> i2v;//idx---value
unordered_map<int,int> v2i;//value---idx
unordered_map<int,int> deepth;//value---deepth
void insert(int x,int idx,int deep)
{
if(!i2v.count(idx))i2v[idx] = x,v2i[x] = idx,deepth[x] = deep;
else
{
if(i2v[idx]>x)insert(x,idx*2,deep+1);
else insert(x,idx*2+1,deep+1);
}
}
int main()
{
int n,m;scanf("%d %d",&m,&n);
for(int i = 0;i<n;i++)
{
int x;scanf("%d",&x);
insert(x,1,0);
}
while(m--)
{
int x,y;scanf("%d %d",&x,&y);
if(v2i.count(x)&&v2i.count(y))
{
int a = v2i[x],b = v2i[y];
while(a!=b)
{
if(deepth[i2v[a]]>deepth[i2v[b]])
a = parent(a);
else b = parent(b);
}
if(a==v2i[x])printf("%d is an ancestor of %d.\n",x,y);
else if(b==v2i[y])printf("%d is an ancestor of %d.\n",y,x);
else printf("LCA of %d and %d is %d.\n",x,y,i2v[a]);
}
else
{
if(!v2i.count(x)&&!v2i.count(y))
printf("ERROR: %d and %d are not found.\n",x,y);
else if(!v2i.count(x))
printf("ERROR: %d is not found.\n",x);
else
printf("ERROR: %d is not found.\n",y);
}
}
return 0;
}
//PAT-1151 二叉树的最近公共祖先--同上题
//LCA 的写法需要因输入输出的条件判别，例如PTA数据结构练习直接给出二叉树的顺序存储，我们只需要存储value-pos
//和 pos-value 即可
#include<iostream>
#include<unordered_map>
using namespace std;
int n;
unordered_map<int, int> pos, value,d;
void dfs(int deepth, int u)
{
d[u] = deepth;
if (value.count(u * 2))dfs(deepth + 1, u * 2);
if (value.count(u * 2 + 1))dfs(deepth + 1, u * 2 + 1);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int x; cin >> x;
if(x)pos[x] = i, value[i] = x;
}
dfs(0,1);
int x, y; cin >> x >> y;
if (!value.count(x))printf("ERROR: T[%d] is NULL\n", x);
else if (!value.count(y))printf("ERROR: T[%d] is NULL\n", y);
else
{
int a = x, b = y;
while (a != b)
{
if (d[a] > d[b])a /= 2;
else b /= 2;
}
cout << a << " " << value[a] << endl;
}
return 0;
}
/*
huffman编码的检查问题
棘手原因：
huffman编码是不唯一的，但是最优编码不一定是由Huffman方法进行编码
条件：
1）总长度最小
2）前缀码——每个字符都放在叶子节点上
3）没有度为1的节点（由1，2的条件天然满足）
同时满足条件2和3，不一定满足条件1
思路：
1）先计算出最优编码的长度
2）判断是否是前缀码
*/
//AC代码
#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
const int N = 10010;
typedef pair<int,string>PIS;
int n;
string code[N], word[N];
unordered_map<string, PIS> l, r;
unordered_map<string, int> freq;
unordered_map<int, string> huffman;
//计算最优编码长度WPL，递归计算，当遍历的节点是叶子节点时，返回深度和频度的乘积，否则返回左子树和右子树WPL的和
int WPL(PIS root,int deepth)
{
int res = 0;
if (l.count(root.second) && r.count(root.second))
res = WPL(l[root.second], deepth + 1)+WPL(r[root.second],deepth+1);
else res = root.first * deepth;
return res;
}
//判断前缀码——编码对应的终点对应是否为叶节点，编码路径上是否都是空节点，如果都满足则返回true，否则返回false
bool check()
{
bool flag = true;
for (int i = 0; i < n; i++)
{
string a = word[i], b = code[i];
int idx = 1;
for (auto c : b)
{
if (c == '1')idx = idx * 2 + 1;
else idx = idx * 2;
if (huffman.count(idx))return false;
}
if (huffman.count(idx * 2) || huffman.count(idx * 2 + 1))return false;
else huffman[idx] = a;
}
return flag;
}
int main()
{
priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
cin >> n;
for (int i = 0; i < n; i++)
{
string a; int b;
cin >> a >> b;
freq[a] = b;
heap.push({ b,a });
}
while (heap.size()>1)
{
auto h1 = heap.top();
heap.pop();
auto h2 = heap.top();
heap.pop();
PIS combine = { h1.first + h2.first,h1.second + h2.second };
l[combine.second] = h1;
r[combine.second] = h2;
heap.push(combine);
}
auto t = heap.top();
int correct = WPL(t, 0);
int cnt; cin >> cnt;
while (cnt--)
{
int res = 0;
huffman.clear();
for (int i = 0; i < n; i++)
{
string a, b; cin >> a >> b;
res += b.size() * freq[a];
code[i] = b, word[i] = a;
}
if (res != correct)puts("No");
else
{
if (check())puts("Yes");
else puts("No");
}
}
return 0;
}
