树状数组题目详解 HDU 1166 HDU 1541

2024-02-14 14:18

本文主要是介绍树状数组题目详解 HDU 1166 HDU 1541,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

再次复习树状数组

这里写图片描述

上规律

c1 = a1;
c2 = a1 + a2;
c3 = a3;
c4 = a1 + a2 + a3 + a4;
c5 = a5;
………………
c16 = a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 + a11 + a12 + a13 + a14 + a15 + a16;

树状数组各元素表示的位数

cn = (n - a ^ k + 1) + ………………………… + an

代码版

    for (k = 1; k <= n; k++)for (l = k - lowbit(k) + 1; l <= k; l++)c[k] += b[l];

移位公式

int lowbit (int a)
{return a & (-a);
}

求和公式

int sum (int c[], int n)
{sum = 0;while(n > 0){sum += c[n]n -= lowbit(n);}
}

改变某一个变量公式

int change (int i, int x) // i表示更改的位置, x表示改为的数。
{while(i <= n){c[i] += x;i += lowbit(i);}
}

下面上题 HDU 1166(模板题)

敌兵布阵

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K
(Java/Others) Total Submission(s): 63224 Accepted Submission(s):
26668

Problem Description
C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:”你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:”我知错了。。。”但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.

Input 第一行一个整数T,表示有T组数据。
每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
接下来每行有一条命令,命令有4种形式: (1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30) (2)Sub i
j ,i和j为正整数,表示第i个营地减少j个人(j不超过30); (3)Query i j
,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数; (4)End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令

Output 对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

Sample Input 1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub
10 2 Add 6 3 Query 3 10 End

Sample Output Case 1: 6 33 59

分析

首先简单来看这是一个很简单的累加求和的问题 但是过多的数据会使题目超时

当累加的时候有少量的数据改变的时候不需要重新累加 这时候就需要树状数组

当某个数据发生改变的时候树状数组只需要改变大于这个数最近的2的级数的数组 效率为logN

具体方法看复习

核心代码

计算初始的C数组:
for(i = 1; i <= n; i++)for(l = i - lowbit(i) + 1; l <= i;l++)c[i] += b[l];
前n项求和
int sum2 (int c[], int n)
{int sum = 0;while(n >0){sum += a[n];k -= lowbit(k);}
}
更新数组
void add(int i, int x, int c[])
{while(i < n){c[i] += x;i += lowbit(i);}
}

全部代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int lowbit(int a);
int sum2(int a[], int k);
void add(int i, int x, int c[]);
int n;
int b[100000];
int c[100000];
char d[10];
int main(void)
{int i, j, k, l, a, change1, change2, sum, v;while (scanf_s("%d", &a) != EOF){for (i = 1; i <= a; i++){memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c)); scanf_s("%d", &n);for (j = 1; j <= n; j++)scanf_s("%d", &b[j]);for (k = 1; k <= n; k++)for (l = k - lowbit(k) + 1; l <= k; l++)c[k] += b[l];printf("Case %d:\n", i);getchar();scanf_s("%s", d, 10);while (d[0] != 'E'){scanf_s("%d %d", &change1, &change2);if (d[0] == 'Q'){sum = 0; v = change1 - 1;sum = sum2(c, change2) - sum2(c, v);//printf("%d %d  ", sum2(c, v), sum2(c, change2));printf("%d\n", sum);}else if (d[0] == 'A'){add(change1, change2, c);}else{add(change1, -(change2), c);}getchar();scanf_s("%s", d, 10);}}}return 0;
}int lowbit(int a)
{return a & (-a);
}int sum2(int a[], int k)
{int sum = 0;while (k > 0){sum += a[k];k -= lowbit(k);}return sum;
}void add(int i, int x, int c[])
{while (i <= n){c[i] += x;i += lowbit(i);}
}

HDU 1541

上题目

Stars Time Limit: 2000/1000 MS (Java/Others) Memory Limit:
65536/32768 K (Java/Others) Total Submission(s): 6737 Accepted
Submission(s): 2691

Problem Description Astronomers often examine star maps where stars
are represented by points on a plane and each star has Cartesian
coordinates. Let the level of a star be an amount of the stars that
are not higher and not to the right of the given star. Astronomers
want to know the distribution of the levels of the stars.

For example, look at the map shown on the figure above. Level of the
star number 5 is equal to 3 (it’s formed by three stars with a numbers
1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At
this map there are only one star of the level 0, two stars of the
level 1, one star of the level 2, and one star of the level 3.

You are to write a program that will count the amounts of the stars of
each level on a given map.

Input The first line of the input file contains a number of stars N
(1<=N<=15000). The following N lines describe coordinates of stars
(two integers X and Y per line separated by a space, 0<=X,Y<=32000).
There can be only one star at one point of the plane. Stars are listed
in ascending order of Y coordinate. Stars with equal Y coordinates are
listed in ascending order of X coordinate.

Output The output should contain N lines, one number per line. The
first line contains amount of stars of the level 0, the second does
amount of stars of the level 1 and so on, the last line contains
amount of stars of the level N-1.

Sample Input 5 1 1 5 1 7 1 3 3 5 5

Sample Output 1 2 1 1 0

翻译

我这弱菜的英语 - -

在 笛卡尔坐标系上有一张星空图。有N颗星 图中的每一颗星都用X,Y坐标表示。

每一颗星的亮度等于它左下角的星的个数

输出1 至 N - 1亮度的星的个数 每个一行

解析

我这弱菜的水平刚开始真没看出来这是一个树状数组的题目

其实从题目给的条件中也可以看出题目说了是从小到大排出X坐标优先

可以看成给出的一个暗示 可以通过树状数组来表示变化

下面我们来想象一下树状数组:

在读入第n个数据时,实际上就是求之前读入的数的X坐标小于第N个数的个数

因为题目给出的数字是默认排好序 x优先的 所以在之前的数不会有Y坐标大于第N个数的

同样因为要频繁的更改数组的第X项并改变前N项的和 所以优先考虑树状数组

伪码解析

从1到N循环读入数据(X0, Y0)用树状数组来计算前X0项的和计入数组 lignt[]中第X0项更新加一继续循环……
从1 到 n - 1 输出light[]数组

完全代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;const int maxn = 32050;
int  bit[maxn];
int  level[maxn];
int  n;int lowbit(int x)    //sum lowbit add 为树状数组模板代码 直接调用
{return x & (-x); //等价于x&(-x)
}void add(int x, int val)   //用树状数组对后面节点更新
{while (x<maxn){bit[x] += val;x += lowbit(x);}
}int sum(int x)
{int rank = 0;   //rank代表星星的等级,即它的左下角有的星星个数while (x>0){rank += bit[x];x -= lowbit(x);}return rank;
}int main()
{int   x, y;while (scanf_s("%d", &n) != EOF){memset(bit, 0, sizeof(bit));//清空数组memset(level, 0, sizeof(level));for (int i = 0; i < n; i++){scanf_s("%d%d", &x, &y);level[sum(++x)]++;  // sum函数计算出前x项和  也就是星的亮度add(x, 1);//更新数组}for (int i = 0; i<n; i++)printf("%d\n", level[i]);}return 0;
}

这篇关于树状数组题目详解 HDU 1166 HDU 1541的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/708720

相关文章

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

HTML5中的Microdata与历史记录管理详解

《HTML5中的Microdata与历史记录管理详解》Microdata作为HTML5新增的一个特性,它允许开发者在HTML文档中添加更多的语义信息,以便于搜索引擎和浏览器更好地理解页面内容,本文将探... 目录html5中的Mijscrodata与历史记录管理背景简介html5中的Microdata使用M