历届试题_log大侠
2024-09-03 15:31:39
标题:Log大侠
atm参加了速算训练班,经过刻苦修炼,对以2为底的对数算得飞快,人称Log大侠。
一天,Log大侠的好友 drd 有一些整数序列需要变换,Log大侠正好施展法力...
变换的规则是: 对其某个子序列的每个整数变为: [log_2 (x) + 1] 其中 [] 表示向下取整,就是对每个数字求以2为底的对数,然后取下整。
例如对序列 3 4 2 操作一次后,这个序列会变成 2 3 2。
drd需要知道,每次这样操作后,序列的和是多少。
例如对序列 3 4 2 操作一次后,这个序列会变成 2 3 2。
drd需要知道,每次这样操作后,序列的和是多少。
【输入格式】
第一行两个正整数 n m 。
第二行 n 个数,表示整数序列,都是正数。
接下来 m 行,每行两个数 L R 表示 atm 这次操作的是区间 [L, R],数列序号从1开始。
第一行两个正整数 n m 。
第二行 n 个数,表示整数序列,都是正数。
接下来 m 行,每行两个数 L R 表示 atm 这次操作的是区间 [L, R],数列序号从1开始。
【输出格式】
输出 m 行,依次表示 atm 每做完一个操作后,整个序列的和。
输出 m 行,依次表示 atm 每做完一个操作后,整个序列的和。
例如,输入:
3 3
5 6 4
1 2
2 3
1 3
3 3
5 6 4
1 2
2 3
1 3
程序应该输出:
10
8
6
10
8
6
【数据范围】
对于 30% 的数据, n, m <= 10^3
对于 100% 的数据, n, m <= 10^5
对于 30% 的数据, n, m <= 10^3
对于 100% 的数据, n, m <= 10^5
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 1000ms
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。
提交时,注意选择所期望的编译器类型。
思路:首先我的算法可以解决较小的用例,但是否可以通过所有的用例我不清楚,因为蓝桥杯练习系统没有这道题,应该超时,不可能那么简单。个人就是按照题中的要求来的,整个代码的
时间复杂度为O(n^2),只不过要注意log函数在c++下标是e,所以要转换为求下标为2的对数函数则可以表示为log(x)/log(2);
#include<bits/stdc++.h>
using namespace std;
int n,m;
int array[];
int f(int a1,int a2)
{
for(int i=a1;i<=a2;i++){
array[i]=(int)(log(array[i])/log()+);
}
int sum=;
for(int i=;i<sizeof(array)/sizeof(int);i++){
sum+=array[i];
}
return sum;
}
int main()
{
cin >> n >> m;
int ans[m];
memset(array,,sizeof(array));
memset(ans,,sizeof(ans));
for(int i=;i<n;i++){
cin >> array[i];
}
int a1,a2;
int t=;
while(m--){
cin >> a1 >> a2;
a1--;
a2--;
ans[t++]=f(a1,a2);
}
for(int i=;i<t;i++){
cout << ans[i] << endl;
}
}
里对区间里的值进行对数运算,可以看做是更新,区间更新,求和,很明显是线段树...
下面提供一个大佬的代码只供参考:
#include<bits/stdc++.h> using namespace std; const int maxn = ; int num[maxn]; int tree[maxn*]; int n,m; int l,r; int cnt; void build(int x,int l, int r) { if (l == r){ cin >> tree[x]; if (tree[x] == ){//统计数值1的个数 ,方便优化程序 cnt++; tree[x] = ;//将所有1均变为2,防止1干扰程序优化 } return; } int mid = (l+r)/; build(x*,l,mid); build(x*+,mid+,r); tree[x] = tree[x*]+tree[x*+]; } void update(int x,int l,int r,int L,int R) { if (tree[x] == (r-l+)*){ //如果全为2,直接返回 return ; } if (l == r){ tree[x] = num[tree[x]]; return; } int mid = (l+r)/; if (R <= mid) update(x*,l,mid,L,R); else if (L > mid) update(x*+,mid+,r,L,R); else{ update(x*,l,mid,L,mid); update(x*+,mid+,r,mid+,R); } tree[x] = tree[x*]+tree[x*+]; } int main() { for(int i = ; i <= maxn; i++) //打表 num[i] = (int)(log2(i) + ); cin >> n >> m; build(,,n); while(m--){ cin >> l >> r; update(,,n,l,r); cout << tree[]-cnt << endl; } return ; }
最新文章
- 安装centos后无法引导启动windows7的解决方法
- OC与Swift单例
- Linux服务器之间的目录共享
- js中return,this,arguments,currentStyle和getComputedStyle小析
- 解析XML文件的几种常见操作方法—DOM/SAX/DOM4j
- Helios与Katana的区别
- 转:Jmeter之Bean shell使用(二)
- Yale CAS + .net Client 实现 SSO 的完整版
- C#实现插入排序法
- 使用 Spring 2.5 基于注解驱动的 Spring MVC
- ASP.NET生成日历
- (转载)PHP substr(),mb_substr()及mb_strcut的区别和用法
- 法方总经理用的笔记本电脑&;一体机拆开图。
- setsockopt角色
- Robot Framework使用技巧
- highcharts分段显示不同颜色
- myEclipse hibernate连接数据库配置方法
- Combine Two Tables
- 在ConoHa上Centos7环境下源码安装部署LNMP
- JVM之虚拟机类加载机制
热门文章
- JAVA NIO之浅谈内存映射文件原理与DirectMemory
- JS获取内联样式
- CyclicBarrier与CountDownLatch的区别
- 动态规划 最长回文子串 leetcode5
- linux命令学习笔记(11):nl命令
- FFMPEG基于内存的转码实例——输入输出视频均在内存
- Web实现音频、视频通信
- 基于FTP服务、JAVA实现文件同步操作
- 使用NSURLProtocol和NSURLSession拦截UIWebView的HTTP请求(包括ajax请求)
- Log Structured Merge Trees(LSM) 原理