题意:
n个数,分割成k个部分,使得每份和都为奇数
做法:
一个序列的和的奇偶性和偶数没关系,所以只需要考虑奇数的个数
现在考虑两个问题:
1.如果奇数的个数小于最终要求的k,那么就无法完成分类(即是如果一个数一块也不行)
2.如果奇数的个数,记为cnt,cnt的奇偶性和k的奇偶性不同,例如cnt为3,k为2,那么会出现一组两个奇数相加的情况,是非法状态
完成非法状态的判断过后,则可以进行输出答案,挑选前k-1个奇数,分为k-1块,最后一块以n结尾即可
code:
/*
/\_/\
(o o)
/ \
//^ ^\\
//
| |
\_____/
/\_ _/\
*/
#include<bits/stdc++.h>
#define LL long long
#define N 1000010
#define M 100
#define all(X) (X).begin(),(X).end()
#define pb(X) push_back(X)
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define in io::input()
#define out io::output()
using namespace std;
namespace io{
void input(){
freopen("in.txt","r",stdin);
}
void output(){
freopen("out.txt","w",stdout);
}
}
#define qpow(X,Y) power::quickpow(X,Y)
#define qpow_mod(X,Y) power::quickpow_mod(X,Y)
namespace power{
long long quickpow(long long a,long long b){
long long ret=1;
while(b){
if(b&1)ret*=a;
b>>=1;
a*=a;
}
return ret;
}
long long quickpow_mod(long long a,long long b){
long long ret=1;
long long mod=1e9+7;
while(b){
if(b&1)ret=ret*a%mod;
b>>=1;
a=a*a%mod;
}
return ret;
}
}
using namespace io;
using namespace power;
const long long mod=1e9+7;
int solve(){
int n,k;
cin>>n>>k;
vector<int>a(n);
int cnt=0;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]&1)cnt++;
}
if(cnt<k||cnt%2!=k%2){
return -1;
}
Yes;
for(int i=0;i<n;i++){
if(k==1)break;
if(a[i]&1){
cout<<i+1<<" ";
k--;
}
}
cout<<n<<endl;
return 0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t=1;
cin>>t;
while(t--){
int flag=solve();
if(flag==1) YES;
if(flag==-1) NO;
}
}
标签:cnt,int,ret,long,CF1196B,define,mod
From: https://www.cnblogs.com/NPC404/p/17810871.html