Codeforces Round #575 (Div. 3) B.Odd Sum Segments

题意：给q组数据，每组数据包含一个数组a有n个数和k。把数组分为k段，保证每段之和为奇数，

如是可以做到输出YES，加上每段最右边数的下标。不可以则输出NO。

思路：偶数对每段之和的奇偶没有影响。故遍历奇数个数，若奇数个数小于k，显然不能分成n段。因为偶数个奇数相加为偶数，奇数个奇数相加为奇数。所以当奇数个数与k同为奇数或偶数时。即可达成题意。此时只需遇到奇数就输出直至输出k-1个奇数时再输出n即可（因为若有偶数个奇数，k-1为奇数，则剩下的奇数个数为奇数。若是有奇数个奇数，k-1为偶数，则剩下的奇数个数为奇数,证明得每组分一个奇数最后剩下的那段为一定为奇数）。剩下的皆为NO。

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
int n, k; int a[1000000];
int t; cin >> t;
int cnt = 0;
while(t--) {
vector<int>b; int cnt = 0;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i]%2) {
cnt++;
b.push_back(i);
}
}
if(cnt % 2 == k % 2 && cnt >= k) {
cout << "YES" <<'n';
for(int i = 0; i < k - 1; i++) {
cout << b[i] <<' ';
}
cout << n <<'n';
}
else cout << "NO" <<'n';
}
return 0;
}

总结：把握好奇偶性的关系。

最后

以上就是舒适黄蜂为你收集整理的Codeforces Round #575 (Div. 3) B.Odd Sum Segments的全部内容，希望文章能够帮你解决Codeforces Round #575 (Div. 3) B.Odd Sum Segments所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。