有时候觉得自己就是个思路搬运机,只会搬运思路
这个题首先说了求的是好区间的个数, 好区间满足条件: 1、二进制位1的数量和为偶数 2、w[i]表示a[i]的二进制上1的个数 ,sum[i] = w[1] + ... + w[i],对于l-r区间上任意一个位置j,w[j] < sum[r] - sum[l] - w[j]
设置一个dp[n][2] 数组,dp[i][0]代表 以i为结尾的,区间内二进制1的个数和为偶数的 区间个数
dp[i][1]代表 以i为结尾的,区间内二进制1的个数和为奇数的 区间个数
然后再用dp[i][0] - 所有不满足条件2的区间,把所有满足的区间求和即可
这个1<=a[i] <= 1e8 1e8比这个long long要小,60二进制位就可以保存, 所以这个 l - r 这个区间 最大的w[j] 其实也就是60不到,最小的w[i] 也是1 ,所以当你这个区间长度大于60,必定满足条件2
附上我丑陋无比的ac代码
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<map>
#include<string>
using namespace std;
#define ll long long
#define se second
#define fi first
int n;
const int maxn = ;
long long arr[maxn];
int w[maxn];
int sum[maxn];
int dp[maxn][];
int main()
{
memset(w,,sizeof(w));
scanf("%d",&n);
for(int i = ; i <= n; ++i)
{
scanf("%lld",arr+i);
long long k = ;
for(int j = ; j < ; ++j, k <<= )
{
if( k & arr[i] )
w[i] ++;
}
//cout << w[i] << endl;
}
dp[][] = dp[][] = dp[][] = dp[][] = ;
for(int i = ; i <= n; ++i)
{
//cout << w[i] << endl;
if(w[i] % == )
{
dp[i][] = dp[i-][]+(w[i-]%);
dp[i][] = dp[i-][]+!(w[i-]%);
}
else
{
dp[i][] = dp[i-][]+!(w[i-]%);
dp[i][] = dp[i-][]+(w[i-]%);
}
}
ll ans = ;
for(int i = ; i <= n; ++i)
{
ll add = ;
ll mx = w[i];
ll sum = w[i];
for(int j = i-; j >= && i-j<=; --j)
{
if(mx < w[j]) mx = w[j];
sum += w[j];
if(mx > sum - mx && sum % == )
add --;
}
//cout << dp[i][0] << endl;
//cout << add << endl;
add += dp[i][];
ans += add;
}
printf("%lld\n",ans);
}
Codeforces Round #512 E - Vasya and Good Sequences的更多相关文章
-
Codeforces Round #512 D - Vasya and Triangle
D - Vasya and Triangle #include<bits/stdc++.h> using namespace std; #define LL long long LL gc ...
-
【前行】◇第3站◇ Codeforces Round #512 Div2
[第3站]Codeforces Round #512 Div2 第三题莫名卡半天……一堆细节没处理,改一个发现还有一个……然后就炸了,罚了一啪啦时间 Rating又掉了……但是没什么,比上一次好多了: ...
-
数学 Codeforces Round #219 (Div. 2) B. Making Sequences is Fun
题目传送门 /* 数学:这题一直WA在13组上,看了数据才知道是计算cost时超long long了 另外不足一个区间的直接计算个数就可以了 */ #include <cstdio> #i ...
-
Codeforces Round #512 (Div. 2, based on Technocup 2019 Elimination Round 1) E. Vasya and Good Sequences(DP)
题目链接:http://codeforces.com/contest/1058/problem/E 题意:给出 n 个数,对于一个选定的区间,区间内的数可以通过重新排列二进制数的位置得到一个新的数,问 ...
-
Codeforces Round #512 (Div. 2, based on Technocup 2019 Elimination Round 1) E. Vasya and Good Sequences
题目链接 官网题解写的好清楚,和昨晚Aguin说的一模一样…… 这题只和每个数1的个数有关,设每个数1的个数的数组为$b$,就是首先一段如果是好的,要满足两个条件: 1.这一段$b$数组和为偶数,因为 ...
-
Codeforces Round #512 (Div. 2, based on Technocup 2019 Elimination Round 1) C. Vasya and Golden Ticket 【。。。】
任意门:http://codeforces.com/contest/1058/problem/C C. Vasya and Golden Ticket time limit per test 1 se ...
-
Codeforces Round #512 (Div. 2) D. Vasya and Triangle
参考了别人的思路:https://blog.csdn.net/qq_41608020/article/details/82827632 http://www.cnblogs.com/qywhy/p/9 ...
-
Codeforces Round #512 (Div. 2) D.Vasya and Triangle 数学
题面 题意:给你n,m,k,在你在(0,0)到(n,m)的矩形内,选3个格点(x,y都是整数),使得三角形面积为n*m/k,不能找到则输出-1 题解:由毕克定理知道,格点多边形的面积必为1/2的整数倍 ...
-
Codeforces Round #512 (Div. 2) D. Vasya and Triangle(几何+思维)
题目 题意: 给出 n,m,k ,让你在长为 n,宽为 m 的坐标系里构建一个三角形,使得面积= n*m/k.如果存在,输出“YES”,输出三角形三个顶点的坐标: 如果不存在,输出“NO”. 思路: ...
随机推荐
-
nginx+php 在windows下的简单配置安装
开始前的准备 PHP安装包下载:http://windows.php.net/downloads/releases/php-5.5.14-Win32-VC11-x86.zip Nginx 下载地址:h ...
-
使用 Jquery-UI 实现一次拖拽多个选中的元素操作
项目需要,实现一个拖放操作,要求每次可以拖拽选中的多个元素,释放到目标容器后可排序.考虑了一下,觉得jquery-ui比较合适,毕竟它提供了项目需要的交互性事件机制.拖拽.释放.排序.选择等效果.而在 ...
-
framwork NHibernate
NHibernate 一.NHibernate 1.HQL curd语句总结 . 查询整个映射对象所有字段 ? //直接from查询出来的是一个映射对象,即:查询整个映射对象所有字段 String ...
-
Node.js权威指南 (5) - 使用Buffer类处理二进制数据
5.1 创建Buffer对象 / 705.2 字符串的长度与缓存区的长度 / 725.3 Buffer对象与字符串对象之间的相互转换 / 74 5.3.1 Buffer对象的toString方法 / ...
-
编译boost python模块遇到的错误:../../libraries/boost_1_44_0/boost/python/detail/wrap_python.hpp:75:24: fatal error: patchlevel.h: No such file or directory
就是遇到类似标题上面的错误. 原因是没有安装对应python的python-dev依赖,不然编译到boost python模块的时候就会出错. 所以解决方案是sudo apt-get install ...
-
总结angular+ionic项目中的问题
1:tab的路由导向问题 运用ion-tabs时,第一个ion-tabs标签下的href功能会覆盖掉路由中定义的默认路由(进入应用后直接加载href指向的组件). 解决方法:多写一个ion-tabs标 ...
-
指定IP地址进行远程访问服务器设置方法(windows系统)
我们有很多服务器经常受到外界网络的干扰,入侵者们通过扫描3389端口爆破密码非法进入我们的服务器,这时,我们可以配置服务器IP 安全策略来限制一些IP访问,大大提高了服务器的安全. 实验环境: ...
-
vue上传图片到服务器
https://blog.csdn.net/qq_29712995/article/details/78839093(copy) HTML代码: <input accept="imag ...
-
由 POST 400 错误拔出来的萝卜
缘起 前段时间遇到扫描问题,好不容易拿到了扫描出来的数据,结果调用接口时弹了个 400(Bad request) 给我,匆匆找了点资料修补上线后,忐忑的心也可以安分点.然后,顺着这个 400 的萝卜, ...
-
一个神奇的BUG :Failed to finalize session : INSTALL_FAILED_INVALID_APK: /data/app/vmdl99393454.tmp/10_slice__ signatures are inconsistent
Android Studio 在Gradle编译完成后安装APK时总是失败,EventLog提示如下信息: Failed to finalize session : INSTALL_FAILED_IN ...