1. 首页
  2. 题解列表
  3. 1819题题解

蓝桥杯2014年第五届真题-Log大侠 （C++代码）

277 阅读 5 评论
原题链接：蓝桥杯2014年第五届真题-Log大侠

解题思路:

        其实暴力就行了。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int SIZE = 100002;
LL table[SIZE], cnt;
struct tree {
	LL value; int  left, right;
} tree[SIZE << 4];

void buildtree(int root, int L, int R) {
	tree[root].left = L; tree[root].right = R;
	if (L == R) {
		scanf("%lld", &tree[root].value);
		if (tree[root].value == 1) {
			tree[root].value = 2; cnt++;
		}
		return;
	}
	int mid = (L + R) >> 1;
	buildtree(root << 1, L, mid);
	buildtree(root << 1 | 1, mid + 1, R);
	tree[root].value = tree[root << 1].value + tree[root << 1 | 1].value;
}

void updata(int root, int L, int R) {
	if (tree[root].value == (tree[root].right - tree[root].left + 1) * 2)
		return;
	if (tree[root].left == tree[root].right) {
		tree[root].value = table[tree[root].value];
		return;
	}
	int mid = (tree[root].right + tree[root].left) >> 1;
	if (L > mid)
		updata(root << 1 | 1, L, R);
	else if (R <= mid)
		updata(root << 1, L, R);
	else {
		updata(root << 1, L, mid);
		updata(root << 1 | 1, mid + 1, R);
	}
	tree[root].value = tree[root << 1].value + tree[root << 1 | 1].value;
}

int main() {
	for (int pos = 1; pos < SIZE; pos++)
		table[pos] = (int)(log2(pos) + 1);
	int poi, que; scanf("%d%d", &poi, &que);
	buildtree(1, 1, poi);
	int L, R;
	while (que--) {
		scanf("%d%d", &L, &R);
		updata(1, L, R);
		printf("%lld\n", tree[1].value - cnt);
	}
}


点赞(0)
　

0.0分

0 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
点进来你会后悔的
点进来你会后悔的
简简单单的循环
简简单单的循环
简单的回文数
简单的回文数

评论列表 共有 5 条评论

咖啡 5年前 回复TA 
@咖啡 我的一直 输出抄超限  我把输出的  %I64d  改成 %Ild  就过了， 不知道什么鬼     感谢兄弟回复
HzuWHF 5年前 回复TA 
@咖啡 ヾ(*´▽‘*)ﾉ 过了鸭
咖啡 5年前 回复TA 
int m = tree[ri].mid();
	if(R <= m) UpdateTree(ri << 1, L, R);
	else if(L > m) UpdateTree(ri << 1 | 1, L, R);
	else {
		UpdateTree(ri << 1, L, m);
		UpdateTree(ri << 1 | 1, m + 1, R);
	}
	PushUp(ri);
}

int main() {
	int n, m;
	for(int i = 1; i < (N << 2); ++i) table[i] = (int)floor(log2(i)) + 1;
	scanf("%d%d", &n, &m);
	BuildTree(1, 1, n);
	int l, r;
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &l, &r);
		UpdateTree(1, l, r);
		printf("%I64d\n", sum[1]);
	}
	return 0;
}

/*
对于 30% 的数据， n, m <= 10^3
对于 100% 的数据， n, m <= 10^5
*/
咖啡 5年前 回复TA 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

struct Node{
	int L, R;
	int mid() { return L + R >> 1; }
}tree[N << 2];

ll sum[N << 2], table[N << 2];

void PushUp(int ri) {
	sum[ri] = sum[ri << 1] + sum[ri << 1 | 1];
}

void BuildTree(int ri, int L, int R) {
	tree[ri] = { L, R };
	if(L == R) {
		scanf("%d", &sum[ri]);
		return ;
	}
	int m = tree[ri].mid();
	BuildTree(ri << 1, L, m);
	BuildTree(ri << 1 | 1, m + 1, R);
	PushUp(ri);
}

void UpdateTree(int ri, int L, int R) {
	if(tree[ri].L == tree[ri].R) {
		sum[ri] = table[sum[ri]];
		return ;
	}
咖啡 5年前 回复TA 
兄弟  可以帮我看看为什么输出超限了吗