{口胡~数据结构} CCCC L2-004 L2-006 L2-011 L2-012 L3-002(线段树) HRBUST-2040 L2-013(联通度)
L2-004 这是二叉搜索树吗？ （25 分）
口胡 搜索树
中序遍历是有序的 树 左边小于右边 所以在前序遍历里一旦找到第一个比当前比较用的跟大的 便是右子树的开端
这题 输入可能是镜像树的前序 所以 改下一开始建立树函数大小于号就好
当 是镜像树时 显然 不能正常建立 所以后续遍历数组不会到达n个
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn= 1e3+5;
int a[maxn];
int b[maxn];
int cnt,n;
void getrt1(int l,int r){
if(l>r) return ;
int i = l + 1 , j = r ;
while(i<=r&&a[l]>a[i]) i++;
while(j>l&&a[l]<=a[j]) j--;
if(i-j!=1) return ;
getrt1(l+1,j);
getrt1(i,r);
b[++cnt]=a[l];
}
void getrt2(int l,int r){
if(l>r) return ;
int i = l + 1 , j = r ;
while(i<=r&&a[l]<=a[i]) i++;
while(j>l&&a[l]>a[j]) j--;
if(i-j!=1) return ;
getrt2(l+1,j);
getrt2(i,r);
b[++cnt]=a[l];
}
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
getrt1(1,n);
if(cnt!=n){
cnt=0;
getrt2(1,n);
}
if(cnt!=n){
cout<<"NO\n";
}else{
cout<<"YES\n"<<b[1];
for(int i=2;i<=n;i++){
cout<<" "<<b[i];
}puts("");
}
return 0;
}
L2-006 树的遍历 （25 分）
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列
层序遍历 只好先建树了
按找前序遍历的方法建树。。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 35;
int n, in_order[maxn], post_order[maxn];
vector<int> ans;
struct Node {
int v;
int left, right;
} tree[maxn];
int Root;
int bulid(int L1, int R1, int L2, int R2) {
if (L1 > R1) return -1;
int root = post_order[R2];
int p = L1;
while (in_order[p] != root) p++;
int cnt = p - L1;
tree[root].left = bulid(L1, p - 1, L2, L2 + cnt - 1);
tree[root].right = bulid(p + 1, R1, L2 + cnt, R2 - 1);
return root;
}
void bfs() {
queue<int> Q;
Q.push(Root);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
ans.push_back(u);
if (tree[u].left != -1) Q.push(tree[u].left);
if (tree[u].right != -1) Q.push(tree[u].right);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <=n; i++) scanf("%d", &post_order[i]);
for (int i = 1; i <=n; i++) scanf("%d", &in_order[i]);
Root = bulid(1, n , 1, n );
bfs();
for (int i = 0; i < ans.size(); i++) {
if (i != 0) printf(" ");
printf("%d", ans[i]);
}
printf("\n");
return 0;
}
https://vjudge.net/problem/HRBUST-2040
二叉树的遍历 HRBUST - 2040
给出一棵二叉树的中序和前序遍历，输出它的后序遍历。
每组数据的第一行包括一个整数n，表示这棵二叉树一共有n个节点。
接下来的一行每行包括n个整数，表示这棵树的中序遍历。
接下来的一行每行包括n个整数，表示这棵树的前序遍历。
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn= 1e3+5;
int n;
int a[maxn],b[maxn],c[maxn];
int f=0;
void fun(int p1, int p2, int q1, int q2){
// cout<<p1<<" "<<p2<<" | "<<q1<<" "<<q2<<endl;
if(p1>p2 || q1>q2) return;
int i = 0;
while(a[p1] != b[i+q1]) i++;
// cout<<i<<endl;
fun(p1+1,p1+i,q1,q1+i-1);
fun(p1+i+1,p2,q1+i+1,q2);
// if(f) cout<<" ";
// f=1;
cout<<a[p1]<<" ";
}
int main() {
while(cin>>n){
f=0;
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++) cin>>a[i];
fun(1,n,1,n);
cout<<endl;
}
return 0;
}
L2-011 玩转二叉树 （25 分）
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
几乎同上
#include<bits/stdc++.h>
using namespace std;
const int maxn = 35;
int n, pre_order[maxn], in_order[maxn];
vector<int> ans;
struct Node {
int left, right;
} tree[maxn];
int Root;
int bulid(int L1, int R1, int L2, int R2) {
if (L2 > R2) return -1;
int root = pre_order[L1];
int p = L2;
while (in_order[p] != root) p++;
int cnt = p - L2;
tree[root].left = bulid(L1+1, L1+cnt, L2,p-1);
tree[root].right = bulid(L1+cnt+1, R1,p+1, R2 );
return root;
}
void bfs() {
queue<int> Q;
Q.push(Root);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
ans.push_back(u);
if (tree[u].right != -1) Q.push(tree[u].right);
if (tree[u].left != -1) Q.push(tree[u].left);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <=n; i++) scanf("%d", &in_order[i]);
for (int i = 1; i <=n; i++) scanf("%d", &pre_order[i]);
Root = bulid(1, n , 1, n );
bfs();
// cout<<Root<<endl;
for (int i = 0; i < ans.size(); i++) {
if (i != 0) printf(" ");
printf("%d", ans[i]);
}
printf("\n");
return 0;
}
L2-012 关于堆的判断
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005<<1;
int n,m,x,y;
vector<int> ans;
int a[maxn];
int rt=0;
map<int,int> b;
string tmp;
void insert(int x){
a[++rt]=x;
int t=rt;
while(t>1&&a[t/2]>a[t]){ // > 1
swap(a[t/2],a[t]);
t/=2;
}
a[t]=x;
}
int main() {
cin>>n>>m;
for(int i=0;i<n;i++) {
cin>>x;
insert(x);
}
for(int i=1;i<=n;i++){
b[a[i]]=i;
}
for(int i=0;i<m;i++){
cin>>x;
cin>>tmp;
if(tmp[0]=='i'){
cin>>tmp;
if(tmp[0]=='t'){
cin>>tmp;
if(tmp[0]=='r'){
if(b[x]==1){
cout<<'T'<<endl;
}else cout<<"F"<<endl;
}else{
cin>>tmp;
cin>>y;
if(b[x]==b[y]/2){
cout<<"T\n";
}else cout<<"F\n";
}
}else{
cin>>tmp>>tmp>>y;
if(b[x]/2==b[y]){
cout<<"T"<<endl;
}else cout<<"F"<<endl;
}
}else{
cin>>y>>tmp>>tmp;
if(b[x]/2==b[y]/2){
cout<<"T"<<endl;
}else cout<<"F\n";
}
}
return 0;
}
L3-002 特殊堆栈 （30 分）
想不到吧 神tmd线段树 orz
被人提示了一下 很快A了
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int MN = 1e5;
int n,m,cmd,st,ed,k,rt;
stack<int> s;
int tr[maxn<<2];
void my_push(int l,int r, int p,int rt,int t){
//cout<<l<<" "<<r<<" "<<p<<" "<<rt<<" "<<t<<endl;
if(l==r){
tr[rt]+=t;
return;
}else{
int mid=(l+r)>>1;
if(p<=mid) my_push(l,mid,p,rt<<1,t);
else my_push(mid+1,r,p,rt<<1|1,t);
}
tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
int dfs(int x,int rt,int l,int r){
// cout<<x<<" "<<rt<<" "<<l<<" "<<r<<endl;
if(l==r) return l;
if(tr[rt<<1]>=x) {
return dfs(x,rt<<1,l,(l+r)>>1);
}
else{
x-=tr[rt<<1];
return dfs(x,rt<<1|1,((l+r)>>1)+1,r);
}
}
void my_peek(){
if(s.empty()){
cout<<"Invalid\n";
return ;
}
int cnt=(tr[1]+1)>>1;
cout<<dfs(cnt,1,1,MN)<<endl;
}
void my_pop(){
if(s.empty()) cout<<"Invalid\n";
else{
cout<<s.top()<<endl;
my_push(1,MN,s.top(),1,-1);
s.pop();
}
}
void slove(){
cin>>n;
string str;
for(int i=0;i<n;i++){
cin>>str;
if(str.size()==3){
my_pop();
}else if(str.size()==4){
cin>>m;
s.push(m);
my_push(1,MN,m,1,1);
}else{
my_peek();
}
}
}
int main() {
slove();
return 0;
}
L2-013 红色警报 （25 分）
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。
并查集跑联通度
为什么 上一次的联通度 CNT ==这次tmp+1 || tmp 是不改变连通性的
破坏了联通度 会割裂一个 联通子图 肯定+2了
有些联通度不变 是因为 本来我割裂的就是一个孤立点
tmp加一是：
仅攻占一个城市 却没有割裂其他城市对 除该城市联系外 的 关系
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 5005;
bool v[maxn];
pair<int,int> a[maxn];
int pre[maxn];
void init(int n) {
for(int i=0; i<=n; i++) pre[i]=i;
}
int finds(int x) {
return pre[x]!=x?pre[x]=finds(pre[x]):x;
}
void unions(int x,int y) {
x=finds(x);
y=finds(y);
x!=y?pre[x]=y:1;
}
int main() {
int n,m,k,x;
cin>>n>>m;
init(n);
for(int i=1; i<=m; i++) {
cin>>a[i].first>>a[i].second;
unions(a[i].first,a[i].second);
}
int cnt=0,tmp=0;
for(int i=0; i<n; i++) {
if(pre[i]==i) cnt++;
}
cin>>k;
int ks=0;
while(ks++!=k) {
cin>>x;
v[x]=1;
init(n);
tmp=0;
for(int i=1; i<=m; i++) {
if(v[a[i].first]||v[a[i].second]) continue;
else unions(a[i].second,a[i].first);
}
for(int i=0; i<n; i++) {
if(pre[i]==i) tmp++;
}
if(tmp<=cnt+1) {/////////////////
printf("City %d is lost.\n",x);
} else {
printf("Red Alert: City %d is lost!\n",x);
}
cnt=tmp;
}
if(n==k) cout<<"Game Over.\n";
return 0;
}
网易公司福利 162人发布