第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7 算法训练 逆序对 平衡二叉树
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
算法训练 逆序对
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：
有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a[1]…a[n]。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。
Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。
输入格式
第一行一个整数n。
下面每行，一个数x。
如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x≠0，表示这个节点是叶子节点，权值为x。
输出格式
输出一个整数，表示最少有多少逆序对。
样例输入
3
0
0
3
1
2
样例输出
1
数据规模与约定
对于20%的数据，n <= 5000。
对于100%的数据，1 <= n <= 200000，0 <= a[i]<2^31
题解：
C语言
#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("%I64d\n",ans); return 0; }
C++语言
#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语言
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, " \t\n\r\f"); } 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个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
