NYOJ 119 士兵杀敌（三）【ST算法】 分类： Brush Mode 2014-11-13 20:56 101人阅读 评论(0) 收藏
2024-09-06 07:49:44
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=119
解题思路：
RMQ算法。
不会的可以去看看我总结的RMQ算法。
http://blog.csdn.net/niushuai666/article/details/6624672
代码如下：
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std; const int N = 100010;
int maxsum[N][20], minsum[N][20]; void RMQ(int num) //预处理->O(nlogn)
{
for(int j = 1; j < 20; ++j)
for(int i = 1; i <= num; ++i)
if(i + (1 << j) - 1 <= num)
{
maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);
minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);
}
} int main()
{
int num, query;
int src, des;
scanf("%d %d", &num, &query);
for(int i = 1; i <= num; ++i) //输入信息处理
{
scanf("%d", &maxsum[i][0]);
minsum[i][0] = maxsum[i][0];
}
RMQ(num);
while(query--) //O(1)查询
{
scanf("%d %d", &src, &des);
int k = (int)(log(des - src + 1.0) / log(2.0));
int maxres = max(maxsum[src][k], maxsum[des - (1 << k) + 1][k]);
int minres = min(minsum[src][k], minsum[des - (1 << k) + 1][k]);
printf("%d\n", maxres - minres);
}
return 0;
}
代码优化后：
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std; const int N = 100010;
int maxsum[20][N], minsum[20][N]; //优化1 void RMQ(int num) //预处理->O(nlogn)
{
for(int i = 1; i != 20; ++i)
for(int j = 1; j <= num; ++j)
if(j + (1 << i) - 1 <= num)
{
maxsum[i][j] = max(maxsum[i - 1][j], maxsum[i - 1][j + (1 << i >> 1)]); //优化2
minsum[i][j] = min(minsum[i - 1][j], minsum[i - 1][j + (1 << i >> 1)]);
}
} int main()
{
int num, query;
int src, des;
scanf("%d %d", &num, &query);
for(int i = 1; i <= num; ++i) //输入信息处理
{
scanf("%d", &maxsum[0][i]);
minsum[0][i] = maxsum[0][i];
}
RMQ(num);
while(query--) //O(1)查询
{
scanf("%d %d", &src, &des);
int k = (int)(log(des - src + 1.0) / log(2.0));
int maxres = max(maxsum[k][src], maxsum[k][des - (1 << k) + 1]);
int minres = min(minsum[k][src], minsum[k][des - (1 << k) + 1]);
printf("%d\n", maxres - minres);
}
return 0;
}
优化1：数组由F[N][20]变为F[20][N];
因为数组的地址为a + i + j，对应上面数组，我们需要先循环N的部分，所以
如果是第一种，我们计算时因为i不断变化，我们就需要计算a + i + j
如果是第二种，我们计算时a + i不变,只需要改变j
优化2：
位运算
转载至：http://blog.csdn.net/niushuai666/article/details/7400587
自己也放心不下ST算法
最新文章
- python 线程之 threading(二）
- [Fraud] China UnionPay defrauded in Macau money laundering scandal
- 《极客学院 －－NSAttributedString 使用详解－4－UITextKit 简介》学习笔记（待处理）
- 71 Query Rank Min Max Successor of BST
- 敏捷开发之道（四）Scrum概述
- [Hadoop源码解读]（五）MapReduce篇之Writable相关类
- 有哪些适合学生参与的 C++，网络编程方面的开源项目？
- JavaScript中return的用法详解
- abstract关键字 super 关键字 类与继承
- Neural Network Programming - Deep Learning with PyTorch - YouTube
- linux crontab 命令，最小的执行时间是一分钟,如需要在小于一分钟内重复执行
- IDEA的Database管理台如何显示
- 列式数据库~clickhouse 场景以及安装
- 异步编程之使用yield from
- vue生命周期图示中英文版Vue实例生命周期钩子
- //生成四位数的验证码--->
- SRM482
- lstm(一) 演化之路
- memcached Java Client
- Excel 导入遍历