Editorial for Bedao Mini Contest 08 - CHECKARRAY
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Giả sử ~a[i] \ge a[j]~. Ta có ~a[i] - a[j] \le 1~.
Có ~a[i] - a[j] = 0~, dễ thấy điều kiện này chỉ thỏa mãn khi ~a[i] = a[j]~. Vì vậy ta có thể chọn mọi cặp ~(i, j)~ với ~a[i] = a[j]~ và loại bỏ ~a[j]~. Sau đó, ta thu được một dãy các số phân biệt đôi một.
Có ~a[i] - a[j] = 1~, dễ thấy nếu sắp xếp lại dãy thu được trên, để thu dược dãy này về ~1~ phần tử, dãy đó phải tăng dần với hiệu hai số liên tiếp bằng ~1~. Ta thu dãy về ~1~ phần tử bằng cách chọn liên tiếp hai số bé nhất và loại bỏ số bé hơn.
Code mẫu
#include <iostream> #include <stdio.h> #include <vector> #include <cmath> #include <math.h> #include <map> #include <algorithm> #include <set> #include <bitset> #include <queue> #include <cstring> #include <stack> #include <iomanip> #include <assert.h> #define BIT(x,pos) (((x)>>(pos)) & 1LL) #define _(x) (1LL<<(x)) #define bitCnt(x) __builtin_popcountll(x) #define turnOn(x,pos) ((x) = (_(pos))) #define turnOff(x,pos) ((x) &= ~(_(pos))) #define flipBit(x,pos) ((x) ^= (_(pos))) #define lowBit(x) ((x) & (-x)) #define turnAll(x) (_(x)-1LL) #define name "test" #define nameTask "" #define fastIO ios::sync_with_stdio(false); cin.tie(0); using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<int,ll> pil; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; const int N = 50; vector<int> a; int n; int main() { if (fopen(name".INP","r")) freopen(name".INP","r",stdin), freopen(name".OUT","w",stdout); fastIO cin>>n; for (int i = 1;i <= n; ++i) { int x; cin>>x; a.push_back(x); } sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); for (int i = 1;i < (int)a.size(); ++i) if (a[i] != a[i-1] + 1) return cout<<"NO" ,0; cout<<"YES"; }
Comments