0000

用户名：dafei0710

访问量：5712

签　名：

等　　级
排　　名	2484
经　　验	2285
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校	湖北汽车工业学院
专　　业

　　自我简介：

TA的其他文章

[编程入门]数字的处理与判断-题解(C语言代码)
浏览：65

[STL训练]sort练习-题解(C++代码)
浏览：1070

蓝桥杯2015年第六届真题-垒骰子-题解(C++代码)
浏览：784

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯2016年第七届真题-压缩变换-题解(C++代码)

　　作者: 0000　　　　发表时间：2020-03-11 15:22:36 浏览：741　|　评论：0　

原题链接：蓝桥杯2016年第七届真题-压缩变换

这道题直接按照问题描述的，对于每个数向前找到这个数，并统计之间遇到的数的种类数（使用排序），复杂度为O(n2 log n)，可以得到约30%的分数。
为了高效的解决这个问题，可以建立两棵平衡树。第一棵平衡树用于存储每个数和它最后出现的位置对应的映射。第二棵平衡树将所有数最后一次出现的位置通过树建立有序序列，并通过平衡树统计一个位置右边的结点数。
当枚举到序列中的一个数x时，首先在第一棵树中查找x，看是否出现过，如果出现过就找到最后一次出现的位置p，并在第二棵树中查找位置p右边的结点数。之后，在第一棵树中更新x对应的位置为当前位置，在第二棵树中删位置p，并把当前位置加入到第二棵树中。
使用两棵平衡树后的时间复杂度为O(n log n)，可以得到100%的分数。

```cpp
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

class Node {
public:
	Node *lch, *rch;
	int t;
	int h;
	int k, v;
};

Node *recs = 0;

void recyle(Node *rec)
{
	rec->lch = recs;
	recs = rec;
}

Node *createNode()
{
	if (recs)
	{
		Node *ret = recs;
		recs = ret->lch;
		return ret;
	}
	return new Node;
}

int getT(Node *node)
{
	return (node)?node->t:0;
}

void updateT(Node *node)
{
	node->t = getT(node->lch) + getT(node->rch) + 1;
}

int get(Node *root, int k)
{
	if (!root)
		return -1;
	if (root->k == k)
		return root->v;
	if (root->k > k)
		return get(root->lch, k);
	return get(root->rch, k);
}

void insert(Node *&root, int k, int v)
{
	if (!root)
	{
		root = createNode();
		root->lch = root->rch = 0;
		root->t = 1;
		root->h = rand();
		root->k = k;
		root->v = v;
		return ;
	}
	if (root->k == k)
	{
		root->v = v;
		return ;
	}
	if (root->k > k)
	{
		insert(root->lch, k, v);
		if (root->lch->h < root->h)
		{
			Node *ll = root->lch;
			root->lch = ll->rch;
			ll->rch = root;
			root = ll;
			updateT(root->rch);
		}
		updateT(root);
	}
	else
	{
		insert(root->rch, k, v);
		if (root->rch->h < root->h)
		{
			Node *rr = root->rch;
			root->rch = rr->lch;
			rr->lch = root;
			root = rr;
			updateT(root->lch);
		}
		updateT(root);
	}
}

Node *merge(Node *a, Node *b)
{
	if (!a) return b;
	if (!b) return a;
	if (a->h < b->h)
	{
		a->rch = merge(a->rch, b);
		updateT(a);
		return a;
	}
	else
	{
		b->lch = merge(a, b->lch);
		updateT(b);
		return b;
	}
}

int dodel(Node *&root, int k)
{
	if (!root)
		return 0;
	int ret = 0;
	if (root->k == k)
	{
		ret = getT(root->rch);
		Node *rec = root;
		root = merge(root->lch, root->rch);
		recyle(rec);
		return ret;
	}
	if (root->k > k)
		ret = getT(root->rch) + 1 + dodel(root->lch, k);
	else
		ret = dodel(root->rch, k);
	updateT(root);
	return ret;
}

Node *proot = 0;
Node *rroot = 0;

void printT(Node *r)
{
	if (!r) return ;
	printf("(");
	if (r->lch)
		printT(r->lch);
	printf("%d[%d] ", r->k, r->t);
	if (r->rch)
		printT(r->rch);
	printf(")");
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		int x;
		scanf("%d", &x);
		int p = get(proot, x);
		if (p < 0)
		{
			printf("-%d ", x);
		}
		else
		{
			int v = dodel(rroot, p);
			printf("%d ", v);
		}
		insert(proot, x, i);
		insert(rroot, i, x);
	}
	printf("\n");
	return 0;
}
```

0.0分

8 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

0000

TA的其他文章

你可能喜欢

化学品问题（C语言代码）

点我有惊喜！你懂得！

【回文数(二)】（C语言代码）

星期判断机（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯2016年第七届真题-压缩变换-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

孤独的骑士（C语言代码）

众数问题（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言训练-最大数问题（C语言代码）

小九九（C++代码）简单粗暴，直接输出

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

Manchester-台球碰撞-（附带图解）

A+B for Input-Output Practice (V) （C++代码）

WU-川哥的吩咐（C++代码）

0000

TA的其他文章

你可能喜欢

化学品问题 （C语言代码）

点我有惊喜！你懂得！

【回文数(二)】 （C语言代码）

星期判断机 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯2016年第七届真题-压缩变换-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

孤独的骑士 （C语言代码）

众数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言训练-最大数问题 （C语言代码）

小九九 （C++代码）简单粗暴，直接输出

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

Manchester-台球碰撞-（附带图解）

A+B for Input-Output Practice (V) （C++代码）

WU-川哥的吩咐 （C++代码）

化学品问题（C语言代码）

【回文数(二)】（C语言代码）

星期判断机（C语言代码）

　　评论区

孤独的骑士（C语言代码）

众数问题（C语言代码）

C语言训练-最大数问题（C语言代码）

小九九（C++代码）简单粗暴，直接输出

WU-川哥的吩咐（C++代码）