【oi模拟赛】长乐中学-不知道多少年

改造二叉树

【题目描述】

小Y在学树论时看到了有关二叉树的介绍：在计算机科学中，二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子” 。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。

什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数值。对于其中的每个结点p，若其存在左孩子lch，则key[p]>key[lch]；若其存在右孩子rch，则key[p]<key[rch]；注意，本题中的二叉搜索树应满足对于所有结点，其左子树中的key小于当前结点的key，其右子树中的key大于当前结点的key。

小Y与他人讨论的内容则是，现在给定一棵二叉树，可以任意修改结点的数值。修改一个结点的数值算作一次修改，且这个结点不能再被修改。若要将其变成一棵二叉搜索树，且任意时刻结点的数值必须是整数（可以是负整数或0），所要的最少修改次数。

相信这一定难不倒你！请帮助小Y解决这个问题吧。

【输入格式】

第一行一个正整数 n表示二叉树结点数。结点从 1~n 进行编号。

第二行 n 个正整数用空格分隔开，第 i 个数 ai 表示结点 i 的原始数值。

此后 n - 1 行每行两个非负整数 fa, ch，第 i + 2行描述结点 i + 1 的父亲编号 fa，以及父

子关系 ch，(ch = 0 表示 i + 1 为左儿子，ch = 1表示 i + 1为右儿子)。

结点 1一定是二叉树的根。

【输出格式】

仅一行包含一个整数，表示最少的修改次数。

【样例输入】

3

2 2 2

1 0

1 1

【样例输出】

2

【数据范围】

20 % ：n <= 10 , ai <= 100.

40 % ：n <= 100 , ai <= 200

60 % ：n <= 2000 .

100 % ：n <= 10 ^ 5 , ai < 2 ^ 31.

分析

中序遍历 + 最长不下降序列

错误代码如下

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 100000+9;

#define lowbit(x) (x&-x)

int n;

int a[N], b[N], tot, c[N];

int lch[N], rch[N];

int mn = 2147483647, mx = -1;

void dfs(int x) {

	if(!x) return ;

	dfs(lch[x]);

	b[++tot] = x;

	dfs(rch[x]);

}

int ft[N], ans;

void add(int x, int k) {while(x <= mx) {ft[x] = max(ft[x], k); x += lowbit(x);} }

int query(int x) {//最长不下降

	int mxx = -1;

	while(x) {

		mxx = max(ft[x], mxx);

		x -= lowbit(x);

	}

	return mxx;

}

int main() {

//	freopen("binary13.in", "r", stdin);

//	freopen("binary5.out", "w", stdout);

	scanf("%d", &n);

	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

	int fa, ch;

	for(int i = 2; i <= n; i++) {

		scanf("%d%d",&fa, &ch);

		if(ch == 0) lch[fa] = i;

		else rch[fa] = i;

	}

	dfs(1);

//	for(int i = 1; i <= tot; i++) printf("%d ", b[i]);

//	printf("\n");

	for(int i = 1; i <= tot; i++) c[i] = a[b[i]], c[i] -= i, mn = min(mn, c[i]);

	for(int i = 1; i <= tot; i++) {

		c[i] = c[i] - mn + 1;//都变成大于等于1的， 才能用树状数组做

		mx = max(c[i], mx);//找树状数组下标最大值

	}

//	for(int i = 1; i <= tot; i++) printf("%d ", c[i]);

	ans = -1;

	for(int i = 1; i <= tot; i++) {

		ft[c[i]] = query(c[i]) + 1;

		ans = max(ft[c[i]], ans);

		add(c[i], ft[c[i]]);

	}

	printf("%d", tot - ans);//“最长不下降”是要保留下来的

}

正确代码：二分

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn=100000+20;

int n,p[maxn],lch[maxn],rch[maxn];

int order[maxn],tot=0;

int f[maxn],ans;

inline void read(int& n){

    n=0;

    char ch=getchar();

    while(ch<'0' || ch>'9') ch=getchar();

    do{

        n=n*10+ch-'0';

        ch=getchar();

    }while(ch>='0' && ch<='9');

    return;

}

void init(){

    memset(lch,-1,sizeof(lch));

    memset(rch,-1,sizeof(rch));

    read(n);

    for(int i=1;i<=n;i++) read(p[i]);

    for(int i=2;i<=n;i++){

        int fa,ff;

        read(fa);

        read(ff);

        if(ff==0) lch[fa]=i;

        else rch[fa]=i;

    }

    return;

}

void dfs(int node){

    if(node==-1) return;

    dfs(lch[node]);

    ++tot;

    order[tot]=p[node]-tot;

    dfs(rch[node]);

    return;

}

void solve(){

    dfs(1);

    for(int i=1;i<=tot;i++){

        f[i]=2100000000;

    }

    f[1]=order[1];ans=1;

    for(int i=2;i<=tot;i++){

        if(order[i]>=f[ans])

            f[++ans]=order[i];

        else{

            int l = 1,r = ans, xxx;//注意右边界为r

            while (l <= r) {

                int mid = (l + r) >> 1;

                if (f[mid] < order[i]) {

			l = mid + 1;

                } else {

			xxx = mid;

			r = mid - 1;

		}

            }

            f[xxx] = order[i];

        }

    }

    ans=n-ans;

    printf("%d",ans);

    return;

}

int main(){

    init();

    solve();

    return 0;

}

数字对

【题目描述】

小 H 是个善于思考的学生，现在她又在思考一个有关序列的问题。

她的面前浮现出一个长度为 n的序列{ai}，她想找出一段区间[L, R](1 <= L <= R <= n)。

这个特殊区间满足，存在一个 k(L <= k <= R)，并且对于任意的 i(L <= i <= R)，ai 都能

被 ak 整除。这样的一个特殊区间 [L, R]价值为 R - L。

小 H 想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些

区间又分别是哪些呢？你能帮助她吧。

【输入格式】

第一行，一个整数 n.

第二行，n个整数，代表 ai.

【输出格式】

第一行两个整数，num和 val,表示价值最大的特殊区间的个数以及最大价值。

第二行 num 个整数，按升序输出每个价值最大的特殊区间的 L.

【样例输入 1】

5

4 6 9 3 6

【样例输出 1】

1 3

2

【样例输入 2】

5

2 3 5 7 11

【样例输出 2】

5 0

1 2 3 4 5

【数据范围】

30%: 1 <= n <= 30 , 1 <= ai <= 32.

60%: 1 <= n <= 3000 , 1 <= ai <= 1024.

80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.

100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.

分析

等下再具体的打...

RMQ的思想，求区间gcd和最小值，二分找答案

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 500000+9;

inline int gcd(int x, int y) {return !y ? x : gcd(y, x%y);}

int n;

int f[N][20], g[N][20];

void init() {

	for(int k = 1; (1<<k) <= n; k++) {

		for(int i = 1; i+(1<<k)-1 <= n; i++) {

			f[i][k] = min(f[i][k-1], f[i+(1<<(k-1))][k-1]);

			g[i][k] = gcd(g[i][k-1], g[i+(1<<(k-1))][k-1]);

		}

	}

}

int RMQ_gcd(int l, int r) {

	int m = r - l + 1;

	int k = 0;

	while(1<<k <= m) k++;

	k--;

	return gcd(g[l][k], g[r-(1<<k)+1][k]);

}

int RMQ(int l, int r) {

	int m = r - l + 1;

	int k = 0;

	while(1<<(k+1) <= m) k++;

	return min(f[l][k], f[r-(1<<k)+1][k]);

}

int num;

int ans[N], tot;

int check(int Len) {

	int r, is = 0;

	for(int l = 1; l <= n && l + Len - 1 <= n; l++) {

		r = l+Len-1;

		if(RMQ(l, r) == RMQ_gcd(l, r)) {

			if(is == 0) tot = 0;

			is = 1;

			ans[++tot] = l;

		}

	}

	return is;

}

int main() {

//	freopen("pair.in", "r", stdin);

//	freopen("pair.out", "w", stdout);

	scanf("%d", &n);

	for(int i = 1; i <= n; i++) scanf("%d", &f[i][0]), g[i][0] = f[i][0];

	init();

	int l = 1, r = n, mid, Len;

	while(l <= r) {//左闭右闭

		mid = (l+r)>>1;

		if(check(mid)) {

			Len  = mid;

			l = mid+1;

			num = tot;

		} else {

			r = mid - 1;

		}

	}

	printf("%d %d\n", num, Len - 1);

	for(int i = 1; i <= tot; i++) printf("%d ",ans[i]);

}

/*

7

6 3 9 18 4 8 2

*/

巴特西

【oi模拟赛】长乐中学-不知道多少年

改造二叉树

数字对

最新文章

热门文章