127道甲级题 好像数据结构搭边的 有四十道左右吧
1003. Emergency (25)（最短路）
题意：给一个无向图，每个顶点有一个价值，求解从s到t有几条最短路，然后求出这几条最短路中，价值最高的一条。
思路：直接建图，最短路
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn_v = +;
typedef pair<int, int>pii; int vis[maxn_v], dis[maxn_v], nodePeople[maxn_v], ansPeople[maxn_v], ansNum[maxn_v]; struct edge
{
int to, co;
bool operator < (const edge &other)const//比较函数反着写，因为优先队列默认权值大的
{
if(co != other.co) return co > other.co;
return to < other.to;
}
};
vector<edge>G[maxn_v]; void dijkstra(int s, int vs)
{
//初始化
for(int i = ; i <= vs; i++)
{
vis[i] = ;
dis[i] = INF;
ansPeople[i] = ;
ansNum[i] = ;
} //给起点s更新数据
dis[s] = ;
ansPeople[s] = nodePeople[s];
ansNum[s] = ;//有用的最短路条数 //入队
priority_queue<edge>que;//因为默认的时候是取最大的，所以重载运算符的时候反过来写
que.push({s, dis[s]}); while(que.size())
{
edge cur = que.top();que.pop();
int u = cur.to; if(vis[u]) continue;
vis[u] = ; for(auto e : G[u])
{
int v = e.to, edgeCost = e.co;
//计算有几条最短路
if(dis[v] > dis[u] + edgeCost)//能更新，说明v的最短路条数和u相同
{
ansNum[v] = ansNum[u];
}
else if(dis[v] == dis[u] + edgeCost)//发现从u走到v的最短路径长度和 起点s从别的路去v的最短路径长度 相同，说明ansNum[v] = ansNum[v] + ansNum[u]
{
ansNum[v] += ansNum[u];
} if(dis[v] > dis[u] + edgeCost
|| (dis[v] == dis[u] + edgeCost && ansPeople[v] < ansPeople[u] + nodePeople[v]))
{
dis[v] = dis[u] + edgeCost;
ansPeople[v] = ansPeople[u] + nodePeople[v];//v的总人员 = 到u时的总人员 + v的人员
que.push({v, dis[v]});
}
}
}
} int main()
{
int vs, es, sg, eg;//vs顶点数 es边数 sg起点 eg终点
scanf("%d%d%d%d", &vs, &es, &sg, &eg);
for(int i = ; i < vs; i++) scanf("%d", &nodePeople[i]);
//初始化地图
for(int i = ; i < es; i++)
{
int u, v, co;
scanf("%d%d%d", &u, &v, &co);
G[u].push_back({v, co});//无向图建图
G[v].push_back({u, co});
} dijkstra(sg, vs);
printf("%d %d\n", ansNum[eg], ansPeople[eg]);
return ;
}
1004. Counting Leaves (30)（dfs）
题意：好像是求一下每层结点中，没有孩子的结点数分别是多少。
思路：n才一百，随便搜一下就好了吧。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = +;
typedef pair<int, int>pii; int maxlv;
int level[maxn];
int cnt[maxn];
vector<int>G[maxn]; void dfs(int cur, int lv)
{
level[cur] = lv;
maxlv = max(maxlv, lv);
if(G[cur].size() == ) cnt[lv]++;//如果它没有孩子，说明它这一层没有孩子的结点数++
for(auto o : G[cur]) dfs(o, lv + );
} int main()
{
int n, m;
scanf("%d%d", &n, &m);
while(m--)
{
int pa, num;
scanf("%d%d", &pa, &num);
while(num--)
{
int ch;
scanf("%d", &ch);
G[pa].push_back(ch);
}
}
maxlv = ;
dfs(, );
for(int i = ; i <= maxlv; i++)
{
printf("%d%c", cnt[i], i == maxlv ? '\n' : ' ');
}
return ;
}
1013. Battle Over Cities (25)（并查集 or dfs）
题意：从一个无向图里头，取出一个顶点，至少要补几条边能够使得它联通。
思路：就相当于求它的连通分量x，需要连x-1条边。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = +;
typedef pair<int, int>pii; int attack;
int vis[maxn];
vector<int>G[maxn]; void dfs(int cur)
{
vis[cur] = ;
for(auto o : G[cur]) if(vis[o] == && o != attack) dfs(o);
} int main()
{
int vs, es, query;
scanf("%d%d%d", &vs, &es, &query); while(es--)
{
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);//无向图建图
G[v].push_back(u);
} while(query--)
{
int x;
scanf("%d", &x);
attack = x;
//计算联通分量
memset(vis, , sizeof(vis));
int scc = ;
for(int i = ; i <= vs; i++)
{
if(i == attack || vis[i]) continue;//如果已经被攻占，或者已经被dfs过了，跳过
dfs(i);
scc++;
}
printf("%d\n", scc - );
}
return ;
}
1020. Tree Traversals (25)（树的遍历序列转换）
题意：树的遍历序列转换。
思路：递归建树。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = +; typedef pair<int, int>pii;
int post[], in[], lch[], rch[];
int build(int L1, int R1, int L2, int R2)//in中序遍历 [L1，R1], post后序遍历[L2,R2]
{
if(L1 > R1) return -;
int root = post[R2];
int p = L1;
while(in[p] != root) p++;//推算出根节点在中序遍历中的位置。
int cnt = p - L1; lch[root] = build(L1, p - , L2, L2 + cnt - );//建立左子树
rch[root] = build(p + , R1, L2 + cnt, R2 - );//建立右子树
return root;
} void level_order(int root)//层序遍历
{
queue<int>que;
que.push(root);
while(que.size())
{
int cur = que.front();que.pop();
int lson = lch[cur], rson = rch[cur];
if(lson != -) que.push(lson);
if(rson != -) que.push(rson);
printf("%d%c", cur, que.size() ? ' ' : '\n');
}
} int main()
{
int n;
scanf("%d", &n);
for (int i = ; i < n; i++) scanf("%d", &post[i]);
for (int i = ; i < n; i++) scanf("%d", &in[i]);
int root = build(, n - , , n - );
level_order(root);
return ;
}
1021. Deepest Root (25)（树的直径）
题意：问你这是不是一棵树，然后求出那些顶点：满足条件，以它为根，这颗树最深。
思路：树的直径，两次dfs能计算出树的直径。其实这道题可以再快一点，把三次dfs缩到两次。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = +; int maxLevel;
int vis[maxn];
int level[maxn];
vector<int>G[maxn];
vector<int>temp; void dfs_scc(int cur)
{
vis[cur] = ;
for(auto o : G[cur]) if(vis[o] == ) dfs_scc(o);
} void dfs_level(int cur, int pa, int lv)
{//深搜层数
level[cur] = lv;
if(lv > maxLevel)
{
maxLevel = lv;
temp.clear();
temp.push_back(cur);
}
else if(lv == maxLevel)
{
temp.push_back(cur);
} for(auto o : G[cur])
{
if(o != pa)
{
dfs_level(o, cur, lv + );
}
}
} int main()
{
int vs;
scanf("%d", &vs);
for(int i = ; i < vs; i++)
{
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);//无向图建图10
G[v].push_back(u);
} int scc = ;
for(int i = ; i <= vs; i++)
{
if(vis[i] == ) dfs_scc(i), scc++;
} if(scc != )
{
printf("Error: %d components\n", scc);
}
else
{
set<int>ans;
//第一次dfs
maxLevel = ;
temp.clear();
memset(level, , sizeof(level));
dfs_level(, -, );
int root = temp[]; for(auto o : temp) ans.insert(o); //第二次dfs
maxLevel = ;
temp.clear();
memset(level, , sizeof(level));
dfs_level(root, -, );
root = temp[]; for(auto o : temp) ans.insert(o); for(auto o : ans)
{
printf("%d\n", o);
}
}
return ;
}
1030. Travel Plan (30)（最短路）
题意：
思路：...最短路呗，两个条件的那种。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn_v = +;
typedef pair<int, int>pii; int vis[maxn_v], dis[maxn_v], cost[maxn_v], pre[maxn_v]; struct edge
{
int to, dis, co;
bool operator < (const edge &other)const//比较函数反着写，因为优先队列默认权值大的
{
if(dis != other.dis) return dis > other.dis;
if(co != other.co) return co > other.co;
return to < other.to;
}
};
vector<edge>G[maxn_v]; void dijkstra(int s, int vs)
{
//初始化
for(int i = ; i <= vs; i++)
{
pre[i] = -;
vis[i] = ;
dis[i] = INF;
cost[i] = INF;
} //给起点s更新数据
dis[s] = ;
cost[s] = ;
//入队
priority_queue<edge>que;//因为默认的时候是取最大的，所以重载运算符的时候反过来写
que.push({s, dis[s], cost[s]}); while(que.size())
{
edge cur = que.top();que.pop();
int u = cur.to; if(vis[u]) continue;
vis[u] = ; for(auto e : G[u])
{
if(dis[e.to] > dis[u] + e.dis ||
dis[e.to] == dis[u] + e.dis && cost[e.to] > cost[u] + e.co)
{
pre[e.to] = u;
dis[e.to] = dis[u] + e.dis;
cost[e.to] = cost[u] + e.co;
que.push({e.to, dis[e.to], cost[e.to]});
}
}
}
} int main()
{
int vs, es, sg, eg;//vs顶点数 es边数 sg起点 eg终点
scanf("%d%d%d%d", &vs, &es, &sg, &eg); for(int i = ; i < es; i++)
{
int u, v, dis, co;
scanf("%d%d%d%d", &u, &v, &dis, &co);
G[u].push_back({v, dis, co});//无向图建图
G[v].push_back({u, dis, co});
} dijkstra(sg, vs); stack<int>sta;
int now = eg;
while(now != -)
{
sta.push(now);
now = pre[now];
}
while(sta.size())
{
printf("%d ", sta.top());sta.pop();
}
printf("%d %d\n", dis[eg], cost[eg]);
return ;
}
1032. Sharing (25)（模拟）
思路：找到两个链表相同的地方就好了。。然后输出就完事了，pat的链表都是数组+map模拟。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 +;
typedef pair<int, int>pii; struct node
{
char ch;
int nxt;
}nodes[maxn]; int main()
{
int add1, add2, n;
scanf("%d%d%d", &add1, &add2, &n);
map<int, int>ma;
for(int i = ; i < n; i++)
{
char ch;
int add, nxt;
scanf("%d %c %d", &add, &ch, &nxt);
nodes[add] = {ch, nxt};
} map<int, int>vis;//遍历第一个链表存储所有出现过的结点编号
int now = add1;
while(now != -)
{
vis[now] ++;
now = nodes[now].nxt;
} now = add2;
while(now != -)
{
if(vis[now] == )//这个结点在第一个链表中未出现
{
now = nodes[now].nxt;
}
else break;//和第一个链表中的某个结点重合。跳出即可。
}
if(now != -) printf("%05d\n", now);
else puts("-1");
return ;
}
1043. Is It a Binary Search Tree (25)（二叉搜索树）
题意：让你判断一下这棵树是否是BST。
思路：递归judge。先根据左子树小于根节点，把左右子树切分出来，然后检测一下右子树是否均大于根。然后如果是BST，那么递归建树就行了。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = +;
typedef pair<int, int>pii; struct node
{
int val;
node *left, *right;
node():left(NULL), right(NULL){}
};
int pre[maxn];//二叉搜索树的先序序列 bool judge(int L, int R, int k)
{
if(L >= R) return true;
int p = L + ;
if(k == )
{
while(p <= R && pre[p] < pre[L]) p++;//左子树小于根节点 for(int i = p; i <= R; i++)
{
if(pre[i] < pre[L]) return false;
}
}
else if(k == )//BST的镜像
{
while(p <= R && pre[p] >= pre[L]) p++;
for(int i = p; i <= R; i++)
{
if(pre[i] >= pre[L]) return false;
}
} return judge(L + , p - , k) && judge(p, R, k);
} node *build(int L, int R, int k)
{
if(L > R) return NULL; node *root = new node();
root->val = pre[L]; int p = L + ;
if(k == )
{
while(p <= R && pre[p] < pre[L]) p++;//左子树小于根节点
}
else if(k == )//BST的镜像
{
while(p <= R && pre[p] >= pre[L]) p++;
}
root->left = build(L + , p - , k);
root->right = build(p, R, k);
return root;
}
void post_order(node *x, node *root)
{
if(x->left != NULL) post_order(x->left, root);
if(x->right != NULL) post_order(x->right, root); printf("%d", x->val); if(x != root) printf(" ");
else printf("\n");
} void solve(int n)
{
if (judge(, n - , ))
{
puts("YES");
node *root = build(, n - , );
post_order(root, root);
return ;
}
if (judge(, n - , ))
{
puts("YES");
node *root = build(, n - , );
post_order(root, root);
return ;
} puts("NO");
} int main()
{
int n;
scanf("%d", &n);
for (int i = ; i < n; i++)
{
scanf("%d", &pre[i]);
}
solve(n); return ;
}
1051. Pop Sequence (25)（栈）
题意：
思路：...栈的基础题
#include <bits/stdc++.h>
using namespace std; int maxStore, len, k;
int a[]; bool solve()
{
int cnt = , B = ;
stack<int>sta;
while(sta.size() || B <= len)
{
if(a[cnt] == B)//如果和123456那个序列匹配，就去配对
{
B++;
cnt++;
}//如果不匹配那个序列
else if(sta.size() && a[cnt] == sta.top())//在看看栈顶是否匹配
{
sta.pop();
cnt++;
}//如果栈顶不匹配 只能压入栈
else if(B <= len)//检测此时压入栈的数字是否合法
{
sta.push(B);
B++;
if(sta.size() > maxStore - ) return false;//如果爆了容量了false
}
else return false;
}
return cnt == (len + );
}
int main()
{
scanf("%d%d%d", &maxStore, &len, &k);
while(k--)
{
for(int i = ; i <= len; i++)
{
scanf("%d", &a[i]);
}
if(solve()) puts("YES");
else puts("NO");
}
return ;
}
1053. Path of Equal Weight (30)（dfs+打印路径）
题意：给了一棵每个节点都有相应权值的树，规定根节点是0，从根节点向叶子节点计算，若一直走到某个叶子节点的所有权值和为给定的数s，就要保留这条路径。最后路径们按字典序输出吧好像？
思路：
因为考虑到最后输出好像比较麻烦，然后dfs又是那样的顺序，所以我用set读入了数据以后，每一层都从大到小来建树，保证到时候搜出来的路径，直接可以按顺序打印。
通过一次dfs，求出了所有满足条件的路径的终点（叶子节点），保存在ansLeftNode中，然后一条一条的回溯回去，保存在ans数组里，然后输出。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ;
typedef long long LL;
typedef pair<int, int>pii; int cnt, targetSum;
int val[maxn];
vector<int>tree[maxn];
stack<int>ans[maxn];
set<pii>temp[maxn];
vector<int>ansLeftNode;
bool dfs(int cur, int pa, LL sum)
{
int ret = ;
if(tree[cur].size() == && sum == targetSum)//leaf node
{
ansLeftNode.push_back(cur);
return true;
}
for(auto o : tree[cur])
{
if(o != pa)
{
int ok = dfs(o, cur, sum + val[o]);
ret |= ok;
}
}
return ret;
}
bool dfs_path(int cur, int pa, int eg, LL sum)
{
int ret = ;
if(cur == eg && sum + val[cur] == targetSum)//leaf node
{
ans[cnt].push(val[cur]);
return true;
}
for(auto o : tree[cur])
{
if(o != pa)
{ int ok = dfs_path(o, cur, eg, sum + val[cur]);
ret |= ok;
if(ok)
{
ans[cnt].push(val[cur]);
}
}
}
return ret;
}
int main()
{
int n, m;
scanf("%d%d%d", &n, &m, &targetSum);
for(int i = ; i < n; i++)
{
scanf("%d", &val[i]);
}
for (int i = ; i < m; i++)
{
int u, num;
scanf("%d%d", &u, &num);
while(num--)
{
int v;
scanf("%d", &v);
temp[u].insert({val[v], v});
}
}
for(int i = ; i < n; i++)
{
set<pii>::reverse_iterator it = temp[i].rbegin();
for(; it != temp[i].rend(); it++)
{
tree[i].push_back(it->second);
}
}
cnt = ;
dfs(, -, val[]);
for(auto o : ansLeftNode)
{
dfs_path(, -, o, );
cnt++;
} for(int i = ; i < cnt; i++)
{
printf("%d", ans[i].top());ans[i].pop();
while(ans[i].size())
{
printf(" %d", ans[i].top());ans[i].pop();
}
puts("");
}
return ;
}
1057. Stack (30)（线段树）
题意：有一个东西在不停的模拟栈的进退，然后在制定的操作时，要查询栈中的median value。
思路：是一个线段树的单点更新，单点查询的题。线段树查询第k大的数。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + ;
const int INF = 0x3f3f3f3f;
typedef long long LL;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1 int sum[maxn << ];//开四倍大小空间。线段树 void pushup(int rt){sum[rt] = sum[rt << ] + sum[rt << | ];}; void build(int l, int r, int rt)
{
if(l == r)
{
sum[rt] = ;
return ;
}
int m = (l + r) >> ;
build(lson);
build(rson);
pushup(rt);
} void modify(int l, int r, int rt, int p, int add)//在[l,r]区间内，当前结点编号为rt，查找一个结点编号为p的结点，更新add
{
if(l == r)
{
sum[rt] += add;//对当前结点进行更新
return ;
}
int m = (l + r) >> ;
if(p <= m) modify(lson, p, add);
else modify(rson, p, add);
pushup(rt);//更新完所需叶子结点以后，需要pushup向上传递更新后的信息
} int query(int l, int r, int rt, int k)
{
if(l == r) return l;// 查询第k大的数
int m = (l + r) >> ;
if(sum[rt << ] >= k) return query(lson, k);//如果左子树的数的数量大于等于k，显然可以左子树里
else return query(rson, k - sum[rt << ]);
} int main()
{
int n;
scanf("%d", &n);
stack<int>sta; while(n--)
{
char s[];
scanf("%s", s);
if(s[] == 'o')//pop
{
if(sta.size())
{
int temp = sta.top();
printf("%d\n", temp);
sta.pop();
modify(, maxn, , temp, -);//从线段树中清除
}
else puts("Invalid");
}
else if(s[] == 'u')//push
{
int x;
scanf("%d", &x);
sta.push(x);
modify(, maxn, , x, );//线段树更新
}
else if(s[] == 'e')//PeekMedian
{
//线段树里查
if(sta.size())
{
int x = (sta.size() + ) / ;
printf("%d\n", query(, maxn, , x));
}
else puts("Invalid");
}
}
return ;
}
1064. Complete Binary Search Tree (30)（完全二叉搜索树）
题意：把一个序列填充成一个完全二叉搜索树。输出层序遍历的结果
思路：query函数是计算左右子树的结点个数。因为完全二叉树的性质，可以算出来。
写完以后，发现。傻逼了啊！！！你们记不记得有个东西叫做堆，手写堆都会的对吧。它就是完全BST，有一个特性啊！！！它的左右儿子结点编号为2*i，2*i+1。所以这题其实。。可以很简单对吧。
/*
把一个序列填充成一个完全二叉搜索树。输出层序遍历的结果
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + ; int a[maxn], lch[ + ], rch[ +];//注意 lch和rch数组的大小 和 给出的数字的范围息息相关。写指针就无关了 void query(int n, int &lsonSize, int &rsonSize)
{//n是整棵树的总结点数
if(n == )
{
lsonSize = rsonSize = ;
return ;
}
//求出整棵树的最深层数
//显然此时层数必定大于等于2
int level = ;
while(n >= (( << level) - ))
{
level++;
}
lsonSize = rsonSize = ( << (level - )) - ;
lsonSize += min(n - (( << (level - )) - ), << (level - ));// 左子树的最后一层最多只有(2^(level - 1) / 2) 个，这里是用总的结点数，减掉前level-1层的满二叉搜索树的结点个数
rsonSize += n - - lsonSize;
} int build(int L, int R)
{
if(L > R) return -;
int totNodes = R - L + ;
int lsonSize = , rsonSize = ;
query(totNodes, lsonSize, rsonSize);
int root = a[L + lsonSize]; lch[root] = build(L, L + lsonSize - );
rch[root] = build(L + lsonSize + , R);
return root;
} void level_order(int root)
{
queue<int>que;
que.push(root);
while(que.size())
{
int cur = que.front();que.pop();
if(lch[cur] != -) que.push(lch[cur]);
if(rch[cur] != -) que.push(rch[cur]);
if(cur != root) printf(" ");
printf("%d", cur);
}
puts("");
} int main()
{
int n;
scanf("%d", &n);
for (int i = ; i < n; i++)
{
scanf("%d", &a[i]);
}
sort(a, a + n);
int root = build(, n - );
level_order(root);
return ;
}
1066. Root of AVL Tree (25)（avl树的旋转）
题意：问你最后avl树的根是谁。
思路：avl树的旋转的模拟。课本基础知识。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ; int a[maxn]; struct node
{
int val, height;
node *left, *right;
node(int x):left(NULL), right(NULL), val(x), height(){}
}; int Height(node *p)
{
if (p == NULL) return -;
else return p->height;
} node *avl_RightRotate(node *k2);//LL旋转
node *avl_LeftRightRotate(node *k3);//LR旋转
node *avl_LeftRotate(node *k2);//RR旋转
node *avl_RightLeftRotate(node *k3);//RL旋转 node *avl_RightRotate(node *k2)//LL旋转
{
node *k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2; k2->height = max(Height(k2->left), Height(k2->right)) + ;
k1->height = max(Height(k1->left), Height(k1->right)) + ;
return k1;//新的根结点
} node *avl_LeftRightRotate(node *k3)//LR旋转
{
k3->left = avl_LeftRotate(k3->left);
return avl_RightRotate(k3);
} node *avl_LeftRotate(node *k2)//RR旋转
{
node *k1;
k1 = k2->right;
k2->right = k1->left;
k1->left = k2; k2->height = max(Height(k2->left), Height(k2->right)) + ;
k1->height = max(Height(k1->left), Height(k1->right)) + ;
return k1;//新的根结点
} node *avl_RightLeftRotate(node *k3)//RL旋转
{
k3->right = avl_RightRotate(k3->right);
return avl_LeftRotate(k3);
} node *avl_insert(int x, node *T)
{
if (T == NULL)
{
T = new node(x);
}
else if (x < T->val)//要插入的元素x比当前结点的值小
{//插入T的左子树中
T->left = avl_insert(x, T->left);
if(Height(T->left) - Height(T->right) == )
{
if (x < T->left->val)//插入到T的左子树的左边，是LL旋转
T = avl_RightRotate(T);//left单旋
else if (x > T->left->val)//插入到左子树的右边，是LR旋转
T = avl_LeftRightRotate(T);//left双旋
}
}
else if (x > T->val)//要插入的元素x比当前结点的值大
{//插入T的右子树中
T->right = avl_insert(x, T->right);
if (Height(T->right) - Height(T->left) == )
{
if (x > T->right->val)//插入到右子树的右边是，RR旋转
T = avl_LeftRotate(T);//right单选
else if (x < T->right->val)//插入到右子树的左边是，RL旋转
T = avl_RightLeftRotate(T);//right双旋
}
} T->height = max(Height(T->left), Height(T->right)) + ;
return T;
} int main()
{
int n;
scanf("%d", &n);
node *root = NULL; for (int i = ; i < n; i++)
{
int x;
scanf("%d", &x);
root = avl_insert(x, root);
}
printf("%d\n", root->val); return ;
}
1074. Reversing Linked List (25)（模拟）
题意：链表每k个，一翻转。
思路：这题很恶心啊，题意没说清楚，它给的数据可能是好几条链，沃日。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + ;
typedef pair<int, int>pii; struct node
{
int val, nxt;
}nodes[maxn];
int temp[maxn]; int main()
{
int head, n, reverseLen;
scanf("%d%d%d", &head, &n, &reverseLen);
for(int i = ; i < n; i++)
{
int address, val, nxt;
scanf("%d%d%d", &address, &val, &nxt);
nodes[address] = {val, nxt};
} int now = head;
int cnt = ;
while(now != -)
{
temp[cnt++] = now;
now = nodes[now].nxt;
} //找出每一个翻转区间的起始位置
for(int i = ; i + reverseLen <= cnt; i += reverseLen)
{
reverse(temp + i, temp + i + reverseLen);
} for(int i = ; i < cnt; i++)
{
printf("%05d %d ", temp[i], nodes[temp[i]].val);
if(i == cnt - ) printf("-1\n");
else printf("%05d\n", temp[i + ]);
}
return ;
}
1076. Forwards on Weibo (30)（bfs）
思路：看清楚谁follow谁就行了，bfs。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ;
typedef pair<int, int>pii; int level[maxn];
vector<int>follower[maxn]; int bfs(int s, int L)
{
memset(level, -, sizeof(level)); level[s] = ; queue<pii>que;
que.push({s, level[s]}); int ret = ;
while(que.size())
{
pii cur = que.front();que.pop();
if(cur.second > L) continue;//只能传L层 ret++;
for(auto o : follower[cur.first])
{
if(level[o] == -)
{
level[o] = level[cur.first] + ;
que.push({o, level[o]});
}
}
}
return ret - ;//去除自身
} int main()
{
int n, L;
scanf("%d%d", &n, &L);
for(int i = ; i <= n; i++)
{
int k;
scanf("%d", &k);
while(k--)
{
int x;
scanf("%d", &x);
follower[x].push_back(i);//谁跟随谁看清楚
}
}
int query;
scanf("%d", &query);
while(query--)
{
int x;
scanf("%d", &x);
cout << bfs(x, L) << endl;
}
return ;
}
1078. Hashing (25)（哈希表的二次探测）
思路：
不是筛出10000以内的素数，要多筛一点，确保筛到了比10000大的最小的素数，同时，要小心那几个数组开的大小。其实也可以用最普通的isPrime去判。pat数据水的...
还考了一个.....哈希的二次探测。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + ; int tot;
int vis[maxn], check[maxn], prime[maxn]; void sieve(int n)
{
tot = ;
check[] = check[] = ;//check为0时是素数
for (int i = ; i <= n; i++)
{
if (!check[i])
{
prime[tot++] = i;
for (int j = i * i; j <= n; j += i)
{
check[j] = ;
}
}
} }
void modify(int &x)
{
x = *lower_bound(prime, prime + tot, x);
} int main()
{
sieve();
int Msize, n;
scanf("%d%d", &Msize, &n); modify(Msize); for (int i = ; i < n; i++)
{
int x;
scanf("%d", &x);
int pos = x % Msize;
if(vis[pos] == )
{
vis[pos] = ;
printf("%d", pos); }
else
{
int ok = ;
for (int j = ; j < Msize; j++)//哈希表的二次探测
{
int nxtPos = (j * j + pos) % Msize;
if(vis[nxtPos] == )
{
vis[nxtPos] = ;
printf("%d", nxtPos);
ok = ;
break;
}
}
if(ok == ) printf("-");
}
printf(i == n - ? "\n" : " ");
} return ;
}
1079. Total Sales of Supply Chain (25)
思路：
很简单的深搜。但是注意一点。处理零售商的加和的时候 一定要放在for(auto)遍历子节点之前，至于为什么？ 想想看
1 1.8 1
0 5
这组样例
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + ; double ans;
vector<int>tree[maxn];
int amount[maxn]; void dfs(int cur, double curPrice, double rate)
{
double netPrice = curPrice * (1.0 + rate / ); if(amount[cur])//是零售商
{
ans += amount[cur] * curPrice;
return;
} for(auto o : tree[cur])
{
dfs(o, netPrice, rate);
}
} int main()
{
int n;
double rootPrice, rate;
scanf("%d%lf%lf", &n, &rootPrice, &rate);
for(int i = ; i < n; i++)
{
int k;
scanf("%d", &k);
if(k == )
{
scanf("%d", &amount[i]);//是零售商
continue;
}
//供应商
while(k--)
{
int x;
scanf("%d", &x);
tree[i].push_back(x);
}
}
ans = 0.0;
dfs(, rootPrice, rate);
printf("%.1f\n", ans);
return ;
}
1086. Tree Traversals Again (25)（树的遍历序列转换）
思路：思考一下，可以发现入栈的顺序，是根左右，是前序序列。出栈的顺序是，左根右，是中序序列。那么就很简单了啊，求一个后序序列会的吧。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ; vector<int>pre, in;
int lch[], rch[]; int build(int L1, int R1, int L2, int R2)// pre in
{
if(L1 > R1) return -;
cout << "L1 = " << L1 << " R1 = " << R1 <<endl;
int root = pre[L1];
int p = L2;
while(in[p] != root) p++;
int cnt = p - L2;
lch[root] = build(L1 + , L1 + cnt, L2, p - );
rch[root] = build(L1 + cnt + , R1, p + , R2);
if(L1 == R1)cout << "p = " << p << " lch[root] = " <<lch[root] << " rch[root] = " << rch[root] <<endl;
return root;
}
void post_order(int x, int root)
{
if(lch[x] != -) post_order(lch[x], root);
if(rch[x] != -) post_order(rch[x], root);
printf("%d%c", x, x == root ? '\n' : ' ');
}
int main()
{
int n;
scanf("%d", &n);
stack<int>sta;
int cnt = ;
for (int i = ; i < * n; i++)
{
char s[];
scanf("%s", s); if (s[] == 'u')//push
{
int x;
scanf("%d", &x);
sta.push(x);
pre.push_back(x);
}
else
{
in.push_back(sta.top());
sta.pop();
}
}
int root = build(, n - , , n - );
post_order(root, root);
return ;
}
1091. Acute Stroke (30)（bfs）
思路：bfs，三维的宽搜，不能用深搜，会爆栈的。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ; int m, n, L, T;
int ma[][][];
#define isInside(x, y, z) (0 <= x && x < L && 0 <= y && y < m && 0 <= z && z < n) int dx[] = {-, , , , , };
int dy[] = {, -, , , , };
int dz[] = {, , -, , , };
struct node
{
int x, y, z;
};
int bfs(int x, int y, int z)
{
int ret = ;
queue<node>que;
que.push({x, y, z});
ma[x][y][z] = ;
while(que.size())
{
node cur = que.front();que.pop(); for(int kind = ; kind < ; kind++)
{
int fx = cur.x + dx[kind], fy = cur.y + dy[kind], fz = cur.z + dz[kind];
if(isInside(fx, fy, fz) && ma[fx][fy][fz] == )
{
ma[fx][fy][fz] = ;
ret++;
que.push({fx, fy, fz});
}
} }
return ret;
} int main()
{
scanf("%d%d%d%d", &m, &n, &L, &T);
for(int i = ; i < L; i++)
{
for(int j = ; j < m; j++)
{
for(int k = ; k < n; k++)
{
scanf("%d", &ma[i][j][k]);
}
}
}
int ans = ;
for(int i = ; i < L; i++)
{
for(int j = ; j < m; j++)
{
for(int k = ; k < n; k++)
{
if(ma[i][j][k] == )
{
int temp = bfs(i, j, k);
if(temp >= T) ans += temp;
}
}
}
}
cout << ans << endl;
return ;
}
1097. Deduplication on a Linked List (25)
思路：map+数组一通模拟就好了。先分类，哪些是第一次出现绝对值的，留下来left，不然要删掉delete，然后把两个容器里的东西重新串起来即可。
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + ;
const int maxn = 1e5 + ;
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int>pii;
typedef pair<LL, LL>pLL;
typedef unsigned long long ull; struct node
{
int key, nex;
}nodes[maxn]; int main()
{
int head, n;
scanf("%d%d", &head, &n); vector<int>del;
vector<int>left;
map<int, int>ma; for(int i = ; i < n; i++)
{
int add, key, nex;
scanf("%d%d%d", &add, &key, &nex);
nodes[add] = {key, nex};
} //判断其键值的绝对值是否出现过
int now = head;
while(now != -)
{
int key = abs(nodes[now].key);
if(ma[key] == ) ma[key]++, left.push_back(now);//尚未出现过 说明这个结点可以留下来，更新map
else del.push_back(now);//已经出现过 说明要delete掉
now = nodes[now].nex;
} for(int i = ; i < left.size(); i++)
{
int cur = left[i];
nodes[cur].nex = -;//当前结点cur 的 nex指针指空
if(i == ) continue;//i==0时没有前继结点 int last = left[i - ];//把前一个结点left的nex指针 指到 当前结点cur身上
nodes[last].nex = cur;
} for(int i = ; i < del.size(); i++)
{
int cur = del[i];
nodes[cur].nex = -;//当前结点cur 的 nex指针指空
if(i == ) continue;//i==0时没有前继结点 int last = del[i - ];//把前一个结点left的nex指针 指到 当前结点cur身上
nodes[last].nex = cur;
}
//输出结果
for(auto o : left)
{
printf("%05d %d ", o, nodes[o].key);//因为所有编号是五位整数，用int存，%05d输出比较方便。
if(nodes[o].nex == -) puts("-1");//但是%05d输出的时候，遇到-1，会变成-00001，所以要特判
else printf("%05d\n", nodes[o].nex);
} for(auto o : del)
{
printf("%05d %d ", o, nodes[o].key);
if(nodes[o].nex == -) puts("-1");
else printf("%05d\n", nodes[o].nex);
}
return ;
}
1099. Build A Binary Search Tree (30)（给定结构的BST的填充）
题意：建立一棵给定结构的二叉搜索树，并且进行层序遍历。
思路：利用BST的性质，左小右大，那么它的中序遍历就是一个从小到大的有序数组对吧。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + ; int cnt;
int lch[maxn], rch[maxn], a[maxn], val[maxn]; void dfs(int x)
{
int lson = lch[x], rson = rch[x]; if(lson != -)//左子树不为空，就进去
{
dfs(lson);
}
val[x] = a[cnt];
cnt++;
if(rson != -) dfs(rson);
} void level_order(int root)
{
queue<int>que;
que.push(root);
while(que.size())
{
int cur = que.front();que.pop();
int lson = lch[cur], rson = rch[cur];
if(lson != -) que.push(lson);
if(rson != -) que.push(rson); if(cur != root) printf(" ");
printf("%d", val[cur]);
}
} int main()
{
int n;
scanf("%d", &n);
for (int i = ; i < n; i++)
{
int l, r;
scanf("%d%d", &l, &r);
lch[i] = l;
rch[i] = r;
}
for(int i = ; i < n; i++)
{
scanf("%d", &a[i]);
}
sort(a, a + n);
cnt = ;
dfs();
level_order(); return ;
}
1102. Invert a Binary Tree (25)
题意：给你一个树的输入，让你把数左右互换（invert）然后对其进行层序遍历和中序遍历。
思路：...输出的时候左右儿子调换一下就行了呗。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ; int cnt, n;
int lch[], rch[], vis[]; void in_order(int x)
{
if(rch[x] != -) in_order(rch[x]);
printf("%d%c", x, cnt++ == n ? '\n' : ' ');
if(lch[x] != -) in_order(lch[x]);
} void level_order(int root)//层序遍历
{
queue<int>que;
que.push(root);
while(que.size())
{
int cur = que.front();que.pop();
int lson = lch[cur], rson = rch[cur]; if(rson != -) que.push(rson);
if(lson != -) que.push(lson); printf("%d%c", cur, que.size() ? ' ' : '\n');
}
} int main()
{
scanf("%d", &n);
for(int i = ; i < n; i++)
{
getchar();
char left, right;
scanf("%c %c", &left, &right);
if(left != '-')
{
int lson = left - '';
vis[lson] = ;
lch[i] = lson;
}
else lch[i] = -; if(right != '-')
{
int rson = right - '';
vis[rson] = ;
rch[i] = rson;
}
else rch[i] = -;
}
//如果不在各个结点的子树中出现，则这个编号为根节点
int root;
for(int i = ; i < n; i++)
{
if(vis[i] == ) root = i;
} //翻转树以后的序列，所以在这两个函数中左右倒转
level_order(root);
cnt = ;
in_order(root);
return ;
}
1110. Complete Binary Tree (25)（判断是否为完全二叉树）
题意：这是否是一个完全二叉树。
思路：基础题吧。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ; int cnt, n;
int lch[], rch[], vis[]; void in_order(int x)
{
if(rch[x] != -) in_order(rch[x]);
printf("%d%c", x, cnt++ == n ? '\n' : ' ');
if(lch[x] != -) in_order(lch[x]);
}
int isCompleteBinaryTree; int level_order(int root)//层序遍历
{//整棵树压进队列中，由完全二叉树的性质可知，第一个层序遍历的空结点就是整棵树的终点，检查此时是否n个结点都已经被遍历完全
// int flag = 0;
queue<int>que;
que.push(root);
while(que.size())
{
int cur = que.front();que.pop();
if(cur == -)
{
if(cnt != n) isCompleteBinaryTree = ;
continue;
}
cnt++;
int lson = lch[cur], rson = rch[cur];
que.push(lson);
que.push(rson);
if(cnt == n) return cur;
}
} int main()
{
scanf("%d", &n);
getchar();
for(int i = ; i < n; i++)
{
char left[], right[];
scanf("%s %s", left, right); int lson, rson;
if(left[] != '-')
{
lson = ;
for(int i = ; i < strlen(left); i++)
{
lson = lson * + left[i] - '';
}
vis[lson] = ;
lch[i] = lson;
}
else lch[i] = -; if(right[] != '-')
{
rson = ;
for(int i = ; i < strlen(right); i++)
{
rson = rson * + right[i] - '';
} vis[rson] = ;
rch[i] = rson;
}
else rch[i] = -; }
//如果不在各个结点的子树中出现，则这个编号为根节点
int root;
for(int i = ; i < n; i++)
{
if(vis[i] == ) root = i;
}
isCompleteBinaryTree = ;
int ret = level_order(root);
if(isCompleteBinaryTree)
{
printf("YES %d\n", ret);
}
else
{
printf("NO %d\n", root);
} return ;
}
1114. Family Property (25)(并查集)
题意：给出每个人的家庭成员信息和自己的房产个数与房产总面积，让你统计出每个家庭的人口数、人均房产个数和人均房产面积。第一行输出家庭个数，随后每行输出家庭成员的最小编号、家庭人口数、人均房产个数、人均房产面积。
思路：...并查集模拟题。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e4 + ; int pa[maxn], vis[maxn];
int sum[maxn], peo[maxn], num[maxn], small[maxn];//房产总面积，人数，房产套数，最小编号 void init(int n)
{
for (int i = ; i <= n; i++)
{
pa[i] = small[i] = i;
peo[i] = ;
}
}
int uf_find(int x){return pa[x] == x ? x : uf_find(pa[x]);} void join(int x, int y)
{
int fx = uf_find(x), fy = uf_find(y);
if (fx != fy)//把fy 并到fx上
pa[fy] = fx;
}
struct family
{//按人均面积降序输出，若有并列，则按成员编号的升序输出。
int id, small, peo, num, sum;
bool operator < (const family& other)
{
if (sum * other.peo != other.sum * peo)//防止浮点误差 人均面积 sum / peo other.sum / other.peo
return sum * other.peo > other.sum * peo;
return small < other.small;//试了一下 题意指的好像是最小成员编号的升序
}
}; int main()
{
init();//四位编号因此，最多10000个
int n;
scanf("%d", &n);
for (int i = ; i < n; i++)
{
int cur, fa, mo, k;
scanf("%d%d%d%d", &cur, &fa, &mo, &k);//输入自身编号 父母编号，孩子数量
vis[cur] = ;//标记i结点，可能作为某个并查集的根节点
int a[];
for (int j = ; j < k; j++) scanf("%d", &a[j]);//输入他的孩子们
scanf("%d%d", &num[cur], &sum[cur]);//输入他拥有的房产套数，住房面积 //更新完当前用户的房产情况后。join父母，孩子
//合并并查集的过程中pa[fy] = fx,也就是把后者合并到前者上，
//让每一个并查集的根节点出现在vis[i] = 1的i结点上
if (fa != -) join(cur, fa);
if (mo != -) join(cur, mo);
for (int j = ; j < k; j++)
if (a[j] != -)
join(cur, a[j]); }
for (int i = ; i <= ; i++)
{
int fi = uf_find(i);
if (i != fi)
{//如果这个编号的根结点，不是自己，把它的最小编号，人口数量，房产套数，住房面积更新到根结点去
sum[fi] += sum[i];
peo[fi] += peo[i];
num[fi] += num[i];
small[fi] = min(small[fi], small[i]);
}
} vector<family>vec;//记录所有family的根节点 for (int i = ; i <= ; i++)
{
if (vis[i] && uf_find(i) == i)//如果这个结点vis[i]==1并且它的根节点是他自身，那么压进vec
vec.push_back({i, small[i], peo[i], num[i], sum[i]});
}
sort(vec.begin(), vec.end());//按需求排序 printf("%d\n", vec.size());//输出并查集的数量
for (auto o : vec)
{//输出每个并查集的最小编号 家庭人口数 人均房产套数 人均房产面积
printf("%04d %d %.3f %.3f\n", o.small, o.peo, 1.0 * o.num / o.peo, 1.0 * o.sum / o.peo);
}
return ;
}
1115. Counting Nodes in a BST (30)（BST插入操作+dfs）
题意：给你一棵BST的插入序列，问你插完后，这颗BST的最下面两层，各有几个顶点。
思路：完成BST的插入操作，然后搜一遍就完了呗。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ; struct node
{
int val;
node *left, *right;
node():left(NULL), right(NULL){}
}; node *BST_insert(node *T, int val)
{
if(T == NULL)
{
T = new node();
T->val = val;
}
else if(val <= T->val)//题目此时对左子树的定义是<=
{
T->left = BST_insert(T->left, val);
}
else
{
T->right = BST_insert(T->right, val);
}
return T;
} int level[];
int maxLevel = -;
void dfs_level(node *root, int lv)
{
if(root == NULL) return;
maxLevel = max(maxLevel, lv);
level[lv]++;
dfs_level(root->left, lv + );
dfs_level(root->right, lv + );
} int main()
{
int n;
scanf("%d", &n);
node *root = NULL;
for (int i = ; i < n; i++)
{
int x;
scanf("%d", &x);
root = BST_insert(root, x);
} dfs_level(root,);
int n2 = level[maxLevel], n1 = level[maxLevel - ];
//不知道为什么下面这个...最后一个测试点过不去
// int n2 = level[1], n1 = level[2];
// for(int i = 3; i <= maxLevel; i++)
// {
// n2 = n1;
// n1 = level[i];
// }
printf("%d + %d = %d\n", n1, n2, n1 + n2); return ;
}
1118. Birds in Forest (25)
题意：有一些鸟在一棵树上，然后问你有几棵树，几只鸟，那几只鸟在一棵树上。
思路：基础并查集。。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + ; int vis[maxn], pa[maxn];
void init(int n){for(int i = ; i <= n; i++) vis[i] = , pa[i] = i;}
int uf_find(int x){return x == pa[x] ? x : uf_find(pa[x]);}
bool same(int x, int y){return uf_find(x) == uf_find(y);}
void uf_join(int x, int y)
{
int fx = uf_find(x), fy = uf_find(y);
if(fx != fy)
pa[fx] = fy;
} int main()
{
init(maxn);
int n;
scanf("%d", &n);
for(int i = ; i < n; i++)
{
int k, x, y;
scanf("%d", &k); if(k >= )
{
scanf("%d", &x);
vis[x] = ;
for(int j = ; j < k - ; j++)
{
scanf("%d", &y);
vis[y] = ;
uf_join(x, y);
}
}
else if(k == )
{
scanf("%d", &x);
vis[x] = ;
}
}
int cntTree = , cntBird = ;
for(int i = ; i <= ; i++)
{
if(vis[i])
{
cntBird++;
cntTree += (i == pa[i]);
}
} printf("%d %d\n", cntTree, cntBird);
int query;
scanf("%d", &query);
while(query --)
{
int x, y;
scanf("%d%d", &x, &y);
if(same(x, y)) puts("Yes");
else puts("No");
} return ;
}
1119. Pre- and Post-order Traversals (30)
题意：给出前序，后序序列，问你这棵树是否唯一。
思路：这题真的挺好的啊，考你对递归的理解。我们知道如果已知，中序序列加前/后序序列，那么树唯一。现在已知前后序序列，那么我们想，递归到某个结点，它如果只有一个child的时候，是不是这颗树就不唯一了，因为这个child可能是左边或者右边。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ; struct node
{
int val;
node *left, *right;
node():left(NULL), right(NULL){}
};
int n;
bool isOnlyOne;
int pre[maxn], post[maxn]; node *build(int L1, int R1, int L2, int R2)//pre [L1,R1] post [L2,R2]
{
if(L1 > R1) return NULL; node *root = new node();
root->val = pre[L1];
if(L1 == R1) return root;
int p = L1 + ;
while(pre[p] != post[R2 - ]) p++;//post[R2-1]是root右子树的根
int lsonSize = p - L1 - ;
//此时如果没有左子树，显然不唯一。需要中序序列来维护
if(p == L1 + )
{
isOnlyOne = false;
root->left = NULL;
root->right = build(L1 + , R1, L2, R2 - );
}
else
{
root->left = build(L1 + , L1 + lsonSize, L2, L2 + lsonSize - );
root->right = build(p, R1, L2 + lsonSize, R2 - );
} return root;
} int cntSize;//看看已经输出几个点了
void in_order(node *root)
{
if(root->left != NULL) in_order(root->left);
cntSize++;
printf("%d%c", root->val, cntSize == n ? '\n' : ' ');
if(root->right != NULL) in_order(root->right);
} int main()
{
scanf("%d", &n);
for(int i = ; i < n; i++) scanf("%d", &pre[i]);
for(int i = ; i < n; i++) scanf("%d", &post[i]); isOnlyOne = true;
node *root = build(, n - , , n - ); if(isOnlyOne) puts("Yes");
else puts("No"); cntSize = ;
in_order(root);
return ;
}
1122. Hamiltonian Cycle (25)
题意：让你判断一下这一条路径是不是哈密顿回路。
思路：判一下路上的不同的结点数，然后检测相邻两点是否图上相连就好了。模拟题。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ; set<int>G[maxn];
int n, m;
int path[]; int main()
{
scanf("%d%d", &n, &m);
for (int i = ; i < m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
G[u].insert(v);
G[v].insert(u);
} int query;
scanf("%d", &query);
while (query --)
{
int k ;
scanf("%d", &k); set<int>s;
for (int i = ; i <= k; i++)
{
scanf("%d", &path[i]);
s.insert(path[i]);
}
int isHamiltonPath = ;
if(s.size() == n && k == n + && path[] == path[k])
{
for(int i = ; i <= k; i++)
{
int u = path[i - ], v = path[i];
if(G[u].find(v) == G[u].end())
{
isHamiltonPath = ;
break;
}
}
if(isHamiltonPath) puts("YES");
else puts("NO");
}
else puts("NO");
}
return ;
}
1123. Is It a Complete AVL Tree (30)
题意：模拟avl树的插入。
思路：....课本知识
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + ; int n, isComplete; struct node
{
int val, height;
node *left, *right;
node():left(NULL), right(NULL){}
}; int Height(node *T)
{
if(T == NULL) return -;
return T->height;
} node *avl_RightRotate(node *k2);//左子树的左边插入，LL旋转 需要一次右单旋
node *avl_LeftRightRotate(node *k3);//左子树的右边插入，LR旋转 需要一次左单旋，再一次右单旋 node *avl_LeftRotate(node *k2);//右子树的右边插入RR旋转 需要一次左单旋
node *avl_RightLeftRotate(node *k3);//右子树的左边插入，RL旋转 需要一次右单旋，再一次左单旋 node *avl_RightRotate(node *k2)//左子树的左边插入，LL旋转 需要一次右单旋
{
node *k1 = k2->left;
k2->left = k1->right;
k1->right = k2; k1->height = max(Height(k1->left), Height(k1->right)) + ;
k2->height = max(Height(k2->left), Height(k2->right)) + ;
return k1;
} node *avl_LeftRightRotate(node *k3)//左子树的右边插入，LR旋转 需要一次左单旋，再一次右单旋
{
k3->left = avl_LeftRotate(k3->left);
k3 = avl_RightRotate(k3);
return k3;
} node *avl_LeftRotate(node *k2)//右子树的右边插入RR旋转 需要一次左单旋
{
node *k1 = k2->right;
k2->right = k1->left;
k1->left = k2; k1->height = max(Height(k1->left), Height(k1->right)) + ;
k2->height = max(Height(k2->left), Height(k2->right)) + ;
return k1;
} node *avl_RightLeftRotate(node *k3)//右子树的左边插入，RL旋转 需要一次右单旋，再一次左单旋
{
k3->right = avl_RightRotate(k3->right);
k3 = avl_LeftRotate(k3);
return k3;
} node *avl_insert(node *T, int x)
{
if(T == NULL)
{
T = new node();
T->val = x;
T->height = ;
}
else if(x < T->val)
{
T->left = avl_insert(T->left, x);
if(Height(T->left) - Height(T->right) == )
{
if(x < T->left->val)//LL
T = avl_RightRotate(T);
else
T = avl_LeftRightRotate(T);
}
}
else
{
T->right = avl_insert(T->right, x);
if(Height(T->right) - Height(T->left) == )
{
if(x > T->right->val)//RR
T = avl_LeftRotate(T);
else
T = avl_RightLeftRotate(T);
}
}
T->height = max(Height(T->left), Height(T->right)) + ;
return T;
} void level_order(node *root)
{
queue<node*>que;
que.push(root);
int cnt = ;
while(que.size())
{
node *cur = que.front();que.pop(); if(cur == NULL)
{
if(cnt != n) isComplete = ;
continue;
}
cnt++;//非空结点计数
que.push(cur->left);
que.push(cur->right);
if(cur != root) printf(" ");
printf("%d", cur->val);
}
puts("");
} int main()
{
scanf("%d", &n);
node *root = NULL;
for (int i = ; i < n; i++)
{
int x;
scanf("%d", &x);
root = avl_insert(root, x);
}
isComplete = ;
level_order(root); printf("%s\n", isComplete ? "YES" : "NO");
return ;
}
1127. ZigZagging on a Tree (30)
题意：序列转换
思路：....套路题。
#include <bits/stdc++.h>
using namespace std;
const int maxn = + ; int lch[maxn], rch[maxn], post[maxn], in[maxn], level[maxn]; int build(int L1, int R1, int L2, int R2)//前面的是中序遍历的， 后面的是后序遍历的
{
if (L1 > R1) return -;//你的子树已经不存在了 返回-1
int root = post[R2]; int p = L1;
while (in[p] != root) p++;
int cnt = p - L1;//他的左子树有几个点 lch[root] = build(L1, p - , L2, L2 + cnt - );
rch[root] = build(p + , R1, L2 + cnt, R2 - );
return root;
} void dfs(int cur, int depth)
{
level[cur] = depth;
int lson = lch[cur], rson = rch[cur];
if (lson != -) dfs(lson, depth + );
if (rson != -) dfs(rson, depth + );
} void show_post(int root)
{
int lson = lch[root], rson = rch[root];
if(lson != -) show_post(lson);
if(rson != -) show_post(rson);
printf("%d ", root);
} void show(int root, vector<int> &ans)
{
vector<int>vec;
queue<int>que;
que.push(root);
int d = ;
while(que.size())
{
int cur = que.front();que.pop();
if(level[cur] != d)
{
if(d & )
{
for (int i = ; i < vec.size(); i++) ans.push_back(vec[i]);
}
else
{
for (int i = vec.size() - ; i >= ; i--) ans.push_back(vec[i]);
}
d = level[cur];
vec.clear();
} vec.push_back(cur);
int lson = lch[cur], rson = rch[cur];
if (lson != -) que.push(lson);
if (rson != -) que.push(rson);
} if(d & )
{
for (int i = ; i < vec.size(); i++) ans.push_back(vec[i]);
}
else
{
for (int i = vec.size() - ; i >= ; i--) ans.push_back(vec[i]);
}
} int main()
{
int n;
scanf("%d", &n);
for (int i = ; i < n; i++) scanf("%d", &in[i]);//中序遍历 左根右
for (int i = ; i < n; i++) scanf("%d", &post[i]);//后序遍历 左右根
int root = build(, n - , , n - );
dfs(root, ); vector<int>ans;
show(root, ans);
for(int i = ; i < ans.size(); i++) printf("%d%c", ans[i], i == ans.size() - ? '\n' : ' ');
return ;
}