题目信息
- 平台：牛客
- 题目：有趣的区间
- 题目链接
题目描述
给定长度为 n 的整数数组，统计满足条件的子区间数量。根据代码语义推断：区间内至少包含一个奇数时，该区间被视为“有趣”。
初步思路
- 总子区间数为 n*(n+1)/2。
- 只要扣掉“全为偶数”的子区间数，剩下的就是至少包含一个奇数的区间数。
- 统计连续偶数段长度 len，每段贡献 len*(len+1)/2。
算法分析
- 核心：总区间数减去全偶区间数
- 技巧：用一个计数器累积连续偶数长度，遇到奇数就结算
- 正确性简述：任一区间要么含奇数要么全偶，两类互斥且覆盖全部，扣除全偶即可得到答案
- 时间复杂度：O(n)
- 空间复杂度：O(1)
代码实现（C++）
#include<iostream>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);longlongn;cin>>n;longlonglen=0;longlongtotal=n*(n+1)/2;// 总区间数longlongbad=0;// 全偶区间数for(inti=0;i<n;++i){longlonga;cin>>a;if((a&1)==0){// 偶数len++;}else{// 奇数，结算一段连续偶数bad+=len*(len+1)/2;len=0;}}bad+=len*(len+1)/2;// 处理末尾偶数段cout<<(total-bad)<<"\n";return0;}测试用例
| 输入 | 输出 | 说明 |
|---|---|---|
| n=3, a=[1,2,4] | 4 | 总区间 6，全偶区间 2 |
| n=4, a=[2,4,6,8] | 0 | 全偶，全部扣除 |
| n=5, a=[1,3,5,7,9] | 15 | 无全偶区间，等于总数 |
总结与反思
- 这类“至少包含某类元素”的计数题，常用补集思路更直接。
- 连续段计数公式要记牢：len*(len+1)/2。
