2018.09.23 codeforces 1053B. Vasya and Good Sequences(前缀和)
2024-08-28 21:05:40
传送门
考试的时候卡了一会儿。
显然这个答案只跟二进制位为1的数量有关。
还有一个显然的结论。
对于一个区间[l,r][l,r][l,r],如果其中单个数二进制位为1的数量最大值不到区间所有数二进制位为1的数量之和的一半即maxn∗2≤summaxn*2\le summaxn∗2≤sum,并且sum是偶数那么这个区间是好的。
继续考虑,如果我们枚举左端点l和右端点r,那么当sum[r0]−sum[l−1]≥64sum[r_0]-sum[l-1]\ge 64sum[r0]−sum[l−1]≥64之后,如果保持lll不变,r0≤r≤nr_0\le r\le nr0≤r≤n时的答案可以直接通过前缀和预处理求出。
这样总时间复杂度是O(n∗64)O(n*64)O(n∗64)
代码:
#include<bits/stdc++.h>
#define N 300005
#define ll long long
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n;
ll a[N],sum[N],sum1[N],sum2[N],ans=0;
inline ll lowbit(ll x){return x&-x;}
inline int calc(ll x){
int ret=0;
while(x)x-=lowbit(x),++ret;
return ret;
}
int main(){
n=read(),sum2[0]=1;
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+(a[i]=calc(read()));
for(int i=1;i<=n;++i)sum1[i]=sum1[i-1]+(sum[i]&1);
for(int i=1;i<=n;++i)sum2[i]=sum2[i-1]+((sum[i]&1)^1);
for(int r=1;r<=n;++r){
ll maxn=a[r];
int low=max(1,r-64);
for(int l=r;l>=low;--l){
maxn=max(maxn,a[l]);
if((maxn<<1)<=(sum[r]-sum[l-1])&&(sum[r]&1)==(sum[l-1]&1))++ans;
}
if(low==1)continue;
ans+=sum[r]&1?sum1[low-2]:sum2[low-2];
}
cout<<ans;
return 0;
}
最新文章
- HTML自定义对象与属性(谷歌,火狐,IE9浏览器没问题)
- MATLAB的GUI
- js中文乱码怎么解决【转】
- hduoj 4706 Herding 2013 ACM/ICPC Asia Regional Online —— Warmup
- html5in24hours
- WebService简单介绍
- POJ 1961 Period KMP算法next数组的应用
- hdu 1466 计算直线的交点数
- css3投影讲解、投影
- python成长之路——第四天
- NhibernateProfiler-写个自动破解工具(源码)
- inet_aton()
- 生产环境中学习Redis
- Spring框架浅析
- 前端 ------ 03 body标签中的相关标签
- seo:与优化相关的熊掌号
- js正则表达式只能是数字、字母或下划线
- $(...).modal is not a function
- how webpack Hot Module Replacement works
- ios开发UI篇--UIStepper