codeforce每日一题链接
题目链接
题目描述
给定一个长为n的数组a,请构造出一个数组b,使得数组中每一个数都是奇数或是偶数,且b[i]等于a[i]或者a[i]-a[j],j可以取1到n。
样例
输入样例1
7
5
2 6 8 4 3
5
1 4 7 6 9
4
2 6 4 10
7
5 29 13 9 10000001 11 3
5
2 1 2 4 2
5
2 4 5 4 3
4
2 5 5 4
输出样例1
NO
YES
YES
YES
YES
NO
NO
算法
(思维) $O(n)$
我们可以直接找出a中的最小值,如果最小值为奇数,那么a中大于它的偶数都可以减去它成为奇数,所以一定可以;如果最小数为偶数,那么如果a中有奇数,则无解,否则有解。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int w[N];
inline void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
sort(w+1,w+n+1);
if(w[1]%2) cout<<"YES"<<endl;
else{
for(int i=1;i<=n;i++)
if(w[i]%2){
cout<<"NO"<<endl;
return ;
}
cout<<"YES"<<endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}