第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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个叶子节点,每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来,便得到一个序列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语言
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108#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++语言
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143#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语言
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181import 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 |
最后
以上就是舒适钻石最近收集整理的关于第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7 算法训练 逆序对 平衡二叉树的全部内容,更多相关第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7内容请搜索靠谱客的其他文章。
发表评论 取消回复