hdu 5358 First One 2015多校联合训练赛#6 枚举
2024-10-20 20:36:15
First One
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 142 Accepted Submission(s): 37
Problem Description
soda has an integer array a1,a2,…,an.
Let S(i,j) be
the sum of ai,ai+1,…,aj.
Now soda wants to know the value below:
Let S(i,j) be
the sum of ai,ai+1,…,aj.
Now soda wants to know the value below:
∑i=1n∑j=in(⌊log2S(i,j)⌋+1)×(i+j)
Note: In this problem, you can consider log20 as
0.
Input
There are multiple test cases. The first line of input contains an integer T,
indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤105),
the number of integers in the array.
The next line contains n integers a1,a2,…,an (0≤ai≤105).
indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤105),
the number of integers in the array.
The next line contains n integers a1,a2,…,an (0≤ai≤105).
Output
For each test case, output the value.
Sample Input
1
2
1 1
Sample Output
12
Source
因为下取整log(sum)的值是非常小的。
能够枚举每一个位置为開始位置,然后枚举每一个log(sum)仅仅需36*n的。
中间j的累加和
推公式就可以。
可是找log值同样的区间,须要用log(sum)*n的复杂度预处理出来,假设每次二分位置会超时。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define maxn 100007
ll num[maxn];
ll pos[maxn][36]; int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i = 0;i < n; i++){
scanf("%I64d",&num[i]);
} num[n] = 0;
for(ll i = 0;i < 36; i++){
ll di = 1LL<<(i+1);
ll su = num[0];
int p = 0;
for(int j = 0;j < n; j++){
if(j) su -= num[j-1];
while(su < di && p < n){
su += num[++p];
}
pos[j][i] = p;
}
} ll ans = 0,res;
for(int i = 0;i < n; i++){
ll p = i,q;
for(int j = 0;j < 36 ;j ++){
q = pos[i][j];
res = (j+1)*((i+1)*(q-p)+(p+q+1)*(q-p)/2);
ans += res;
p = q;
}
}
printf("%I64d\n",ans);
}
return 0;
}
最新文章
- ubuntu中LAMP环境搭建及ubuntu语言和输入法设置
- pushState与ajax实现无刷新加载
- 如何在本地电脑安装phpmyadmin及访问地址
- 使用ViwePager显示图片时如何防止内存泄露。
- 一个巧妙的实现悬浮的tableViewHeader的方法
- mysql创建用户
- C# 分层 三层架构
- try与finally返回结果执行先后详解
- 安装配置MongoDB
- Oracle11g R2学习系列 之十 解决EM不能用
- Java字节码—ASM
- Redis基础知识小结
- 使用TkbmMWThreadList实现线程安全列表
- systemd service 设置limit,不生效问题
- android:targetSdkVersion引起的问题
- 修改Jenkins的主目录步骤
- 【373】LabelEncoder 相关
- c# ProgressBar进度条方向和美观
- 慕课网 jQuery 笔记
- JavaScript之MV*模式
热门文章
- nw335 debian sid x86-64 -- 4 realtek 提供的官方驱动
- UVa 10534 DP LIS Wavio Sequence
- Knockout v3.4.0 中文版教程-10-绑定-控制文本内容和外观-visible绑定
- [工具使用] visualvm 通过jmx不能连接
- SQL server 事务实例
- [git 学习篇] git remote add origin错误
- 有关git的配置
- bzoj 5055: 膜法师 树状数组+离散
- Spoj-NETADMIN Smart Network Administrator
- 使用反射获取类中的属性(可用于动态返回PO类的列,当做表格的表头)