D.有趣的区间
原题链接
感觉题解的办法好简单呜呜呜，但是我不会。
这里给出我的做法：
由题意知，只要区间中有一个数为奇数那么该区间就是有趣的区间。
不妨考虑[1,n]的所有区间个数设为s，不管它是否有趣。
那么显然s = (1+n)*n/2
考虑以下例子：
5
1 2 3 4 5
那么列出
展开全文
很显然的补集思想+组合数学。不难得出包含任意奇数的区间都为有趣的区间，单步容斥可得所有区间个数减去无趣区间个数即为有趣区间个数，而无趣区间为全为偶数的区间。优化计数可用组合数学，即连续的最大无趣区间包含的无趣区间个数只与区间长度有关，因此可实现时间复杂度为的计数。天冷了，请多喝热水，祝您拥有美好的一
展开全文
喵～我来帮你解释这段代码喵！(≧ω≦)这段代码是求“有趣的区间”个数喵～一个区间要有趣，就需要区间里所有数按位或的结果是奇数呢！(・ω<)关键点喵：一个数是奇数的话，它的二进制最低位一定是1喵！所以区间按位或是奇数，就说明区间里至少有一个奇数哦～因为只要有一个奇数，按位或的最低位就是1，结果就
展开全文
有趣的区间
x是奇数 ⇔ x的二进制最低位为1
A[l] | ...|A[r]为奇数 ⇔ A[l~r]至少有一个数是奇数
设以A[i]为右端点, 考虑它的左端点(<=i)能取哪些位置:
(1) 如果A[i]为奇数, 左端点可以随便取, 因为包含了A[i]这个奇数, 有i+1个
(2) 如
展开全文
Problem
Solution
翻译下题意：当一个区间内存在一个元素为奇数时，则被称为有趣的区间，并且只要两个区间的左右端点有一个不一样，这两个区间就不是同一个区间。
了解题意后，如何求出满足条件的区间个数呢？
我们可以假设数组内所有元素都为奇数，可以很容易地想到，此时的区间个数为1 +
展开全文
根据二进制按位或的性质，我们不难发现"有趣的区间"就是至少包括一个奇数的区间。我们考虑枚举数组A下标i从1~n，枚举的时候我们只统计以当前下标为区间右端点的答案。（可以证明，这样统计是不重不漏的）如果当前枚举的数A[i]是奇数，那么所有区间[j,i]，j取遍1~i，都是"
展开全文
一个比较经典的题目，思路详情可看：【1月17日 牛客每日一题】
#include <bits/stdc++.h>
#define il inline
#define double long double
using namespace std;
using ll = long long
展开全文
思路
显然，区间中只要包含一个奇数，其结果就会是奇数。
进一步思考，统计包含一个或以上奇数的区间的工作量大于统计只包含偶数的区间的工作量。
代码实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
展开全文
这道题看似跟按位或有关系，实际上并没有hhh，小误导依据题目定义，一个奇数与一个奇数或者偶数“|”运算后都会得到奇数，只有两个偶数“|”运算后会得到偶数；而按位或运算遵从交换律，那么我们翻译一下题目，也就是说，只要一个区间内有奇数，那么这个区间就满足题目条件我们在输入完数据以后可以分开进行思考，从头
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
