{口胡~数据结构} 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;
}