根据题意,反正就是随便安排每个数字1的位置了,那么一段区间是good,首先要是1的个数是偶数,因为1个1消掉另一个1,然后就是要一个数的1要用另外一个1去消掉,所以最多的1不能比所有1的一半大,那么这个区间是good的。
又考虑到b[i](每个数字1的个数)是1到63的,所以以每个i为左端点,只要for循环遍历j<=i+63,sum[j]-sum[i-1]%==0,2*mx<=sum[j]-sum[i]就行了,因为大于j的所有sum[j]-sum[i]都一定比2*mx要大,那么只要满足sum[j]-sum[i-1]%2==0就行了,这个预处理一蛤。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#include<bits/stdc++.h> #define maxl 300010 using namespace std; int n; long long ans; long long a[maxl],b[maxl],sum[maxl]; int f[maxl][2]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i]=__builtin_popcountll(a[i]); for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+b[i]; if(sum[i]&1) f[i][1]=f[i-1][1]+1,f[i][0]=f[i-1][0]; else f[i][0]=f[i-1][0]+1,f[i][1]=f[i-1][1]; } ans=0; long long mx,tmp; for(int i=1;i<=n;i++) { mx=0; for(int j=i;j<=i+63 && j<=n;j++) { mx=b[j]>mx?b[j]:mx; if((sum[j]-sum[i-1])%2==0 && sum[j]-sum[i-1]>=mx*2) ans++; } if(i+63<n) { if(sum[i-1]&1) ans+=f[n][1]-f[i+63][1]; else ans+=f[n][0]-f[i+63][0]; } } printf("%lldn",ans); }
最后
以上就是激情鲜花最近收集整理的关于codeforces 1030E的全部内容,更多相关codeforces内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复