Codeforces Round #512 E - Vasya and Good Sequences

时间:2022-12-27 09:16:58

有时候觉得自己就是个思路搬运机,只会搬运思路

这个题首先说了求的是好区间的个数,  好区间满足条件: 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的更多相关文章

  1. Codeforces Round &num;512 D - Vasya and Triangle

    D - Vasya and Triangle #include<bits/stdc++.h> using namespace std; #define LL long long LL gc ...

  2. 【前行】◇第3站◇ Codeforces Round &num;512 Div2

    [第3站]Codeforces Round #512 Div2 第三题莫名卡半天……一堆细节没处理,改一个发现还有一个……然后就炸了,罚了一啪啦时间 Rating又掉了……但是没什么,比上一次好多了: ...

  3. 数学 Codeforces Round &num;219 &lpar;Div&period; 2&rpar; B&period; Making Sequences is Fun

    题目传送门 /* 数学:这题一直WA在13组上,看了数据才知道是计算cost时超long long了 另外不足一个区间的直接计算个数就可以了 */ #include <cstdio> #i ...

  4. Codeforces Round &num;512 &lpar;Div&period; 2&comma; based on Technocup 2019 Elimination Round 1&rpar; E&period; Vasya and Good Sequences(DP)

    题目链接:http://codeforces.com/contest/1058/problem/E 题意:给出 n 个数,对于一个选定的区间,区间内的数可以通过重新排列二进制数的位置得到一个新的数,问 ...

  5. Codeforces Round &num;512 &lpar;Div&period; 2&comma; based on Technocup 2019 Elimination Round 1&rpar; E&period; Vasya and Good Sequences

    题目链接 官网题解写的好清楚,和昨晚Aguin说的一模一样…… 这题只和每个数1的个数有关,设每个数1的个数的数组为$b$,就是首先一段如果是好的,要满足两个条件: 1.这一段$b$数组和为偶数,因为 ...

  6. Codeforces Round &num;512 &lpar;Div&period; 2&comma; based on Technocup 2019 Elimination Round 1&rpar; C&period; Vasya and Golden Ticket 【。。。】

    任意门:http://codeforces.com/contest/1058/problem/C C. Vasya and Golden Ticket time limit per test 1 se ...

  7. Codeforces Round &num;512 &lpar;Div&period; 2&rpar; D&period; Vasya and Triangle

    参考了别人的思路:https://blog.csdn.net/qq_41608020/article/details/82827632 http://www.cnblogs.com/qywhy/p/9 ...

  8. Codeforces Round &num;512 &lpar;Div&period; 2&rpar; D&period;Vasya and Triangle 数学

    题面 题意:给你n,m,k,在你在(0,0)到(n,m)的矩形内,选3个格点(x,y都是整数),使得三角形面积为n*m/k,不能找到则输出-1 题解:由毕克定理知道,格点多边形的面积必为1/2的整数倍 ...

  9. Codeforces Round &num;512 &lpar;Div&period; 2&rpar; D&period; Vasya and Triangle(几何&plus;思维)

    题目 题意: 给出 n,m,k ,让你在长为 n,宽为 m 的坐标系里构建一个三角形,使得面积= n*m/k.如果存在,输出“YES”,输出三角形三个顶点的坐标:  如果不存在,输出“NO”. 思路: ...

随机推荐

  1. nginx&plus;php 在windows下的简单配置安装

    开始前的准备 PHP安装包下载:http://windows.php.net/downloads/releases/php-5.5.14-Win32-VC11-x86.zip Nginx 下载地址:h ...

  2. 使用 Jquery-UI 实现一次拖拽多个选中的元素操作

    项目需要,实现一个拖放操作,要求每次可以拖拽选中的多个元素,释放到目标容器后可排序.考虑了一下,觉得jquery-ui比较合适,毕竟它提供了项目需要的交互性事件机制.拖拽.释放.排序.选择等效果.而在 ...

  3. framwork NHibernate

    NHibernate 一.NHibernate 1.HQL  curd语句总结 . 查询整个映射对象所有字段 ? //直接from查询出来的是一个映射对象,即:查询整个映射对象所有字段 String ...

  4. Node&period;js权威指南 &lpar;5&rpar; - 使用Buffer类处理二进制数据

    5.1 创建Buffer对象 / 705.2 字符串的长度与缓存区的长度 / 725.3 Buffer对象与字符串对象之间的相互转换 / 74 5.3.1 Buffer对象的toString方法 / ...

  5. 编译boost python模块遇到的错误:&period;&period;&sol;&period;&period;&sol;libraries&sol;boost&lowbar;1&lowbar;44&lowbar;0&sol;boost&sol;python&sol;detail&sol;wrap&lowbar;python&period;hpp&colon;75&colon;24&colon; fatal error&colon; patchlevel&period;h&colon; No such file or directory

    就是遇到类似标题上面的错误. 原因是没有安装对应python的python-dev依赖,不然编译到boost python模块的时候就会出错. 所以解决方案是sudo apt-get install ...

  6. 总结angular&plus;ionic项目中的问题

    1:tab的路由导向问题 运用ion-tabs时,第一个ion-tabs标签下的href功能会覆盖掉路由中定义的默认路由(进入应用后直接加载href指向的组件). 解决方法:多写一个ion-tabs标 ...

  7. 指定IP地址进行远程访问服务器设置方法&lpar;windows系统&rpar;

    我们有很多服务器经常受到外界网络的干扰,入侵者们通过扫描3389端口爆破密码非法进入我们的服务器,这时,我们可以配置服务器IP 安全策略来限制一些IP访问,大大提高了服务器的安全. 实验环境:     ...

  8. vue上传图片到服务器

    https://blog.csdn.net/qq_29712995/article/details/78839093(copy) HTML代码: <input accept="imag ...

  9. 由 POST 400 错误拔出来的萝卜

    缘起 前段时间遇到扫描问题,好不容易拿到了扫描出来的数据,结果调用接口时弹了个 400(Bad request) 给我,匆匆找了点资料修补上线后,忐忑的心也可以安分点.然后,顺着这个 400 的萝卜, ...

  10. 一个神奇的BUG :Failed to finalize session &colon; INSTALL&lowbar;FAILED&lowbar;INVALID&lowbar;APK&colon; &sol;data&sol;app&sol;vmdl99393454&period;tmp&sol;10&lowbar;slice&lowbar;&lowbar; signatures are inconsistent

    Android Studio 在Gradle编译完成后安装APK时总是失败,EventLog提示如下信息: Failed to finalize session : INSTALL_FAILED_IN ...