第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7 算法训练 逆序对 平衡二叉树
目录
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7 算法训练 逆序对 平衡二叉树
前言
算法训练 逆序对
C语言
C 语言
Java语言
总结
第六届——第十三届省赛题解
第六届——第十二届省赛题解
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
算法训练 逆序对
资源限制
内存限制：256.0MB C/C 时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目： 有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a1…an。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。 Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。
输入格式
第一行一个整数n。 下面每行，一个数x。 如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x≠0，表示这个节点是叶子节点，权值为x。
输出格式
输出一个整数，表示最少有多少逆序对。
样例输入
3 0 0 3 1 2
样例输出
1
数据规模与约定
对于20%的数据，n <= 5000。 对于100%的数据，1 <= n <= 200000，0 <= ai<2^31
题解：
C语言
代码语言：javascript复制#include<stdio.h>
#define N 200010
long long ans = 0;
int n,val,index=1;
int S[N],left[N],right[N],key[N];
int rRotate(int t){
int tem = left[t];
left[t] = right[tem];
right[tem] = t;
S[t] = S[left[t]] S[right[t]] 1;
S[tem] = S[left[tem]] S[right[tem]] 1;
return tem;
}
int lRotate(int t){
int tem = right[t];
right[t] = left[tem];
left[tem] = t;
S[t] = S[right[t]] S[left[t]] 1;
S[tem] = S[right[tem]] S[left[tem]] 1;
return tem;
}
int adjust(int t,int flag){
if(flag){
if(S[left[left[t]]]>S[right[t]] || S[right[left[t]]]>S[right[t]]){
if(S[right[left[t]]]>S[right[t]]){
left[t] = lRotate(left[t]);
}
return rRotate(t);
}
}else{
if(S[right[right[t]]]>S[left[t]] || S[left[right[t]]]>S[left[t]]){
if(S[left[right[t]]]>S[left[t]]){
right[t] = rRotate(right[t]);
}
return lRotate(t);
}
}
return t;
}
int insert(int t,int node){
S[t] ;
if(key[node]<key[t]){
if(left[t]==0){
left[t]=node;
}else{
left[t] = insert(left[t],node);
}
}else{
if(right[t]==0){
right[t]=node;
}else{
right[t] = insert(right[t],node);
}
}
return adjust(t,key[node]<key[t]);
}
int rank(int t,int val){
if(t==0)return 0;
if(val>=key[t]){
return rank(right[t],val);
}else{
return rank(left[t],val) 1 S[right[t]];
}
}
int merge(int node,int begin,int end){
long long lens=0,rans=0;
int i;
for(i=begin;i<end;i ){
int tem = rank(node,key[i]);
lens = tem;
rans = S[node] - tem;
}
ans = lens < rans ? lens : rans;
for(i=begin;i<end;i ){
left[i]=right[i]=0;
S[i]=1;
node = insert(node,i);
}
return node;
}
int buildTree(){
scanf("%d",&val);
if(val!=0){
left[index]=right[index]=0;
S[index]=1;
key[index]=val;
return index ;
}
int a = index;
int lt = buildTree();
int b = index;
int rt = buildTree();
int c = index;
if(b - a > c - b){
return merge(lt,b,c);
}else{
return merge(rt,a,b);
}
}
int main(){
scanf("%d",&n);
buildTree();
printf("%I64dn",ans);
return 0;
}C 语言
代码语言：javascript复制#include<stdio.h>
#include<iostream>
using namespace std;
#define ForD(i,n) for(int i=n;i;i--)
#define F (100000007)
#define MAXN (2*200000 10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a b)%F;}
long long sub(long long a,long long b){return (a-b (a-b)/F*F F)%F;}
int n,root=0;/*n->叶子结点数,root->根序号？*/
struct node
{
int fa; /*父结点的下标*/
int ch[2]; /*0->左树下标 1->右树下标*/
int size; /*size->当前结点含有的有效结点数*/
int c; /*当前结点的数值*/
node():size(0),c(0){ch[0]=ch[1]=fa=0;} /*初始化为0*/
}a[MAXN]; /*树形数组->纪录各叶结点的数值*/
void update(int x)/*更新叶结点个数*/
{
a[x].size=a[a[x].ch[0]].size a[a[x].ch[1]].size (a[x].c>0);
}
int tail=0;
void pushdown(int x)/*将叶结点的父结点指向当前结点*/
{
a[a[x].ch[0]].fa=a[a[x].ch[1]].fa=x;
}
/*创建树*/
void build(int &x)
{
if (!x) x= tail;
scanf("%d",&a[x].c);
if (a[x].c==0)
{
build(a[x].ch[0]);/*创建左子树*/
build(a[x].ch[1]);/*创建右子树*/
update(x);pushdown(x);/*更新当前结点的有效叶结点个数，以及父结点指向*/
}else a[x].size=1;
}
void rotate(int x)/*旋转*/
{
int y=a[x].fa,z=a[y].fa;
bool p=a[y].ch[0]==x;
if (z) /*有爷爷*/
{
if (a[z].ch[0]==y) /*未旋转*/
a[z].ch[0]=x;/*将子树提拔为父树(升序)*/
else
a[z].ch[1]=x; /*还原状态*/
}
a[x].fa=z,a[y].fa=x;/*当前结点与父结点交换(父结点指向)*/
if (a[x].ch[p]) /*原子树是否有右树(隔代转移)*/
a[a[x].ch[p]].fa=y;
a[y].ch[p^1]=a[x].ch[p];
a[x].ch[p]=y; /*父树移至子树的右端(右树)*/
update(y); /*更新旋转后，子树的结点的有效结点数*/
}
void splay(int x)
{
while (a[x].fa)/*不为根结点*/
{
int y=a[x].fa,z=a[y].fa;
if (z) /*有爷爷*/
if ((a[y].ch[0]==x)^(a[z].ch[0]==y)) rotate(x);/*旋转*/
else rotate(y);
rotate(x);
}
update(x);
}
void ins(long long &tot,int x,int y)
{
a[x].size ; /*插入 1*/
if (a[y].c<=a[x].c) /*是逆序对*/
{
if (a[x].ch[0]) /*左树有子*/
ins(tot,a[x].ch[0],y);
else /*左树无子*/
a[y].fa=x,splay(a[x].ch[0]=y);/*右数插入到左树子*/
}
else
{
tot =a[a[x].ch[0]].size (a[x].c>0);
if (a[x].ch[1]) ins(tot,a[x].ch[1],y);
else a[y].fa=x,splay(a[x].ch[1]=y);
}
}
int q[MAXN],size;
void clac(int x,int y)
{
if (a[y].ch[0]) clac(x,a[y].ch[0]);
if (a[y].c) q[ size]=y;
if (a[y].ch[1]) clac(x,a[y].ch[1]);
}
long long merge(bool &lor,int z)/*分治*/
{
int x=a[z].ch[0],y=a[z].ch[1];
if (a[x].size<a[y].size) /*判断叶结点多的往前调(平衡树?)*/
swap(x,y);
a[x].fa=0;a[y].fa=0;q[1]=y;
size=0;clac(x,y);
long long tot=0; /*最少逆序对*/
ForD(i,size) /*循环（子结点数）次*/
{
int now=q[i];
a[now].ch[0]=a[now].ch[1]=a[now].fa=0;
a[now].size=1;
ins(tot,x,now);
x=now;
}
a[x].fa=z;
a[z].ch[0]=0,a[z].ch[1]=x;
return tot;
}
long long qur(int &x)
{
if (a[x].c) return 0;/*若根结点没有叶结点，则逆序对为0*/
else
{
long long lson=a[a[x].ch[0]].size,rson=a[a[x].ch[1]].size,ls=qur(a[x].ch[0]),rs=qur(a[x].ch[1]);
bool lor=0;
long long ms=merge(lor,x);
return ls rs min(lson*rson-ms,ms);
}
}
int main()
{
scanf("%d",&n);
build(root);
cout<<qur(root)<<endl;
return 0;
}Java语言
代码语言：javascript复制import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.*;
public class Main {
static Node[] tree;
static int inReturn;
static int[] noLeaf;
static Queue<PQItem> inQ;
public static void main(String[] args) throws IOException {
InputReader in = new InputReader(System.in);
int n = in.nextInt(); long cnt = 0;
noLeaf = new int[n];
tree = new Node[n*2];
tree[0] = new Node(0);
tree[1] = new Node(1);
build(tree[1], 1, in);
inQ = new PriorityQueue();
for (int i = n - 2; i >= 0; i--) cnt = merge(noLeaf[i]);
System.out.print(cnt);
}
static void build(Node node, int offset, InputReader in) throws IOException {
LinkedList<Node> queue = new LinkedList();
int index = 0;
queue.addFirst(node);
while (queue.size() > 0) {
Node now = queue.poll();
noLeaf[index] = now.weight;
now.weight = in.nextInt();
if (now.weight == 0) {
now.left = offset;
queue.addFirst(tree[ offset] = new Node(offset));
now.right = offset;
queue.addFirst(tree[offset - 1] = new Node(offset - 1));
index ;
} else now.size = 1;
}
}
static long merge(int node) {
long LS = tree[tree[node].left].size, RS = tree[tree[node].right].size, cnt = 0;
if (LS > RS) {
Queue(tree[node].right);
tree[node] = tree[tree[node].left];
} else {
Queue(tree[node].left);
tree[node] = tree[tree[node].right];
}
while (inQ.size() > 0) {
inReturn = 0;
insert(node, reSet(inQ.poll().node));
cnt = inReturn;
}
return Math.min(cnt, LS * RS - cnt);
}
static void Queue(int node) {
if (tree[node].left != 0) Queue(tree[node].left);
if (tree[node].right != 0) Queue(tree[node].right);
if (tree[node].weight != 0) inQ.offer(new PQItem(tree[node].weight, node));
}
static void insert(int node, int value) {
tree[node].size;
if (tree[node].weight >= tree[value].weight) {
if (tree[node].left != 0) insert(tree[node].left, value);
else tree[node].left = value;
maintain(node, true);
} else {
inReturn = tree[tree[node].left].size 1;
if (tree[node].right != 0) insert(tree[node].right, value);
else tree[node].right = value;
maintain(node, false);
}
}
static int reSet(int node) {
tree[node].size = 1;
tree[node].left = 0;
tree[node].right = 0;
return node;
}
static void LeftRotate(int node) {
Node temp = tree[node];
int r = temp.right;
tree[r].size = temp.size;
temp.right = tree[r].left;
temp.size = tree[temp.left].size tree[temp.right].size 1;
tree[r].left = r;
tree[node] = tree[r];
tree[r] = temp;
}
static void RightRotate(int node) {
Node temp = tree[node];
int l = temp.left;
tree[l].size = temp.size;
temp.left = tree[l].right;
temp.size = tree[temp.left].size tree[temp.right].size 1;
tree[l].right = l;
tree[node] = tree[l];
tree[l] = temp;
}
static void maintain(int node, boolean flag) {
if (flag) {
if (tree[tree[tree[node].left].left].size > tree[tree[node].right].size) RightRotate(node);
else if (tree[tree[tree[node].left].right].size > tree[tree[node].right].size) {
LeftRotate(tree[node].left);
RightRotate(node);
} else return;
} else {
if (tree[tree[tree[node].right].right].size > tree[tree[node].left].size) LeftRotate(node);
else if (tree[tree[tree[node].right].left].size > tree[tree[node].left].size) {
RightRotate(tree[node].right);
LeftRotate(node);
} else return;
}
maintain(tree[node].left, true);
maintain(tree[node].right, false);
}
static class Node {
int weight;
int size;
int left;
int right;
Node(int weight) { this.weight = weight; }
}
static class PQItem implements Comparable<PQItem> {
int index;
int node;
PQItem (int index, int node) {
this.node = node;
this.index = index;
}
@Override
public int compareTo(PQItem o) {
if (this.index > o.index) return -1;
return 1;
}
}
static class InputReader {
BufferedReader read;
StringTokenizer tokens;
String delimiters;
InputReader (InputStream in, String delimiters) {
this.read = new BufferedReader(new InputStreamReader(in));
this.delimiters = delimiters;
this.tokens = new StringTokenizer("", delimiters);
}
InputReader (InputStream in) { this(in, " tnrf"); }
String next() throws IOException {
while (!tokens.hasMoreTokens()) tokens = new StringTokenizer(read.readLine(), delimiters);
return tokens.nextToken();
}
int nextInt() throws IOException { return Integer.parseInt(next()); }
void close() throws IOException { read.close(); }
}
}总结
这个题目能看到是对【平衡二叉树】的理解与使用，直接套用即可，这里面没有给定Python的解法。可以自己去填充一下。
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
第六届——第十三届省赛题解
所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。
第六届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123284163 |
|---|---|
第七届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123285783 |
第八届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123302677 |
第九届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123303285 |
第十届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123319090 |
第十一届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123320205 |
第十二届Java省赛C组第一套 | https://laoshifu.blog.csdn.net/article/details/123413141 |
第十二届Java省赛C组第二套 | https://laoshifu.blog.csdn.net/article/details/123413271 |
第十三届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/128891276 |
第六届——第十二届省赛题解
所有题目均有题解，部分第10题非最优解，至少跑20%数据。
第六届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123440705 |
|---|---|
第七届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123442982 |
第八届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123443626 |
第九届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123443908 |
第十届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123444946 |
第十一届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123445601 |
第十二届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123446589 |
