首页 > 试题广场 >

有趣的区间

[编程题]有趣的区间

热度指数：1557 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个长度为 $n$ 的数组 $A$ ，下标从 $1$ 开始， $A_1,A_2,...,A_n$ 。定义一个区间 $[l,r]$ 是“有趣的区间”，当且仅当 $A_l \mid A_{l+1} \mid A_{l+2} \mid ... \mid A_{r-1} \mid A_{r}$ 结果为奇数。

$a \mid b$ 表示 $a$ 按位或 $b$ （按位或运算符“ $\mid$ ”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位有一个为 $1$ 时，结果位就为 $1$ ）。

求“有趣的区间”的个数，两个区间 $[L1,R1],[L2,R2]$ 相同，当且仅当 $L1=L2$ 且 $R1=R2$ 。

输入描述:

第一行包含一个整数 $n$ $(1\le n\le 5e5)$ ，表示数组 $A$ 的长度。

第二行包含 $n$ 个整数，分别表示数组 $A$ 的 $n$ 个元素，其中 $0\le A_i\le 1e9$ 。

输出描述:

一行包含一个整数，表示 ”有趣的区间“ 的个数。

示例1

输入

2
2 1

输出

说明

”有趣的区间“ 有

$[1,2]$ $($ $2 \mid 1 = 3$ 是奇数 $)$

$[2,2]$ $($ $1$ 是奇数 $)$

共 $2$ 个。

算法知识视频讲解

C++

kilomatutinal

喵～我来帮你解释这段代码喵！(≧ω≦)

这段代码是求“有趣的区间”个数喵～一个区间要有趣，就需要区间里所有数按位或的结果是奇数呢！(・ω<)

关键点喵：一个数是奇数的话，它的二进制最低位一定是1喵！所以区间按位或是奇数，就说明区间里至少有一个奇数哦～因为只要有一个奇数，按位或的最低位就是1，结果就是奇数了喵！(^・ω・^ )

所以问题变成：求数组中有多少个区间包含至少一个奇数喵！直接暴力枚举会超时呢，因为n最大5e5，区间有n*(n+1)/2个，太多啦喵！(>﹏<)

喵～我举一个栗子喵！(≧ω≦)

假如有5个数 5 4 3 2 1 因为这道题只和奇偶性有关。故而等价为 1 0 1 0 1 。

在数组[1,0,1,0,1]中：

左端点为位置0（奇数）有5个有趣区间
左端点为位置1（偶数）有3个有趣区间
左端点为位置2（奇数）有3个有趣区间
左端点为位置3（偶数）有1个有趣区间
左端点为位置4（奇数）有1个有趣区间

注意到了吗喵？位置1（偶数）和位置2（奇数）的有趣区间数都是3，位置3（偶数）和位置4（奇数）的都是1喵！(・ω<)

规律就是如果左端点是偶数，那么从这个位置开始的有趣区间数量，等于从它右边最近的奇数位置开始的有趣区间数量喵！(=^･ω･^)=

为什么呢？因为偶数本身不能使区间有趣，必须包含后面的奇数才行喵！所以从偶数位置开始，必须要走到第一个奇数位置，之后的选择就和直接从那个奇数位置开始一样了喵！(๑>ᴗ<๑)

先遍历数组，把所有的奇数位置记下来，放在weizhi数组里喵～（下标从0开始）

然后遍历这些奇数位置，对于每个奇数，计算以它作为“区间中第一个奇数”的区间个数喵！这样就不会重复计算了～(≧∇≦)ﾉ

具体计算喵：

设当前奇数的位置是i，上一个奇数的位置是f（初始是-1，表示前面没有奇数喵）
左端点可以取f+1到i，一共有(i-f)种选择喵！
右端点可以取i到n-1，一共有(n-i)种选择喵！
所以以这个奇数为第一个奇数的区间数就是(n-i)*(i-f)喵！

把每个奇数的贡献加起来就是答案啦～(๑>ᴗ<๑)
下面！请看代码喵！

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n;cin >> n;
    vector<int> weizhi;//存储所有奇数的索引
    int f=-1;//记录上一个奇数的索引

    for(int i=0;i<n;i++)
    {
        int num;cin >> num;
        if(num&1)//检查num是否为奇数
            weizhi.push_back(i);//记录奇数索引
    }

    ll ans=0;
    for(int i:weizhi)
    {
        //区间公式喵
        ans+=(n-i)*(i-f);
        f=i;//更新喵
    }
    cout << ans;
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

发表于 2026-01-17 00:52:25 回复(0)

牛客203596504号

二进制下奇数尾数是1、偶数尾数是0。

按照或运算规则，区间只要含任何一个奇数，就是有趣的区间。反过来说无趣的空间不能含奇数。

所以数列中的偶数会被奇数隔离成一段一段的，无趣的空间“跨”不过奇数的隔离。

长度为n的区间里的子区间数量公式：n(n+1)/2
所以我们可以：把整个数列的全部子区间数量，减去每一“段”连续偶数的子区间数量，即可。
速读提示：既然我们只关心奇偶，读数时前面所有字符直接跳，只读最后一个字符，且无需转数字('0'=48是偶数)

发表于 2026-01-17 01:26:21 回复(0)

C++

浅碎

基本思路就是，统计所有的连续偶数段，每一段的不合法数量为 len * (len + 1) / 2，总的可能数量为 n * (n + 1) / 2，所以最终答案即为总数量 - 不合法数量

记得开 long long，，，又死在数据范围上面了，我对 ans 的统计开了，但是没有对数组的长度开，导致 n * (n + 1) / 2 就爆数据范围了，，，

发表于 2026-01-17 19:21:49 回复(0)

大吉祥树王

不难发现区间内只要有至少一个奇数即可满足条件

使用贪心策略：

若输入的数为奇数，则添加所有含该奇数且不含上一个奇数的区间即可

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin>>n;
	long long r=0;
	for(int i=1,j=0,a;i<=n;i++)
	{
	    cin>>a;
		if(a&1)
		{
		    r+=(i-j)*(n-i+1);
			j=i;
		}
	}
	cout<<r;
}

发表于 2026-01-17 15:32:31 回复(0)

提交观点

问题信息

难度：

4条回答 4收藏 67浏览

有趣的区间

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题