Editorial for VM 11 Bài 01 - Pirate đãng trí
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.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #define maxN 100100 using namespace std; int n,deg[maxN],rest[maxN*3],mx[maxN*3]; void init(int nd,int l,int r) { if (l==r) rest[nd]=mx[nd]=deg[l]; else { int m=(l+r)>>1; init(nd<<1,l,m); init((nd<<1)+1,m+1,r); mx[nd]=mx[(nd<<1)+1]; } } void decrease(int nd,int l,int r,int x,int y,int val) { if (l==x && r==y) rest[nd]-=val, mx[nd]-=val; else { int m=(l+r)>>1; if (x<=m) decrease(nd<<1,l,m,x,min(y,m),val); if (m<y) { decrease((nd<<1)+1,m+1,r,max(x,m+1),y,val); mx[nd]=mx[(nd<<1)+1]+rest[nd]; } } } int getValue(int nd,int l,int r,int x) { if (l==r) return rest[nd]; int m=(l+r)>>1; if (x<=m) return rest[nd]+getValue(nd<<1,l,m,x); return rest[nd]+getValue((nd<<1)+1,m+1,r,x); } int findLeftmost(int nd,int l,int r,int x) { if (mx[nd]<x) return n; if (l==r) return l; int m=(l+r)>>1; x-=rest[nd]; if (mx[nd<<1]>=x) return findLeftmost(nd<<1,l,m,x); return findLeftmost((nd<<1)+1,m+1,r,x); } int main() { int x,y,test,pos; cin >> test; while (test--) { memset(rest,0,sizeof(rest)); memset(mx,0,sizeof(mx)); cin >> n; int valid=1; for (int i=0;i<n;i++) scanf("%d",°[i]); sort(deg,deg+n); init(1,0,n-1); for (int i=0;i<n;i++) { x=getValue(1,0,n-1,i); if (x+i>=n) { valid=0; break; } if (!x) continue; decrease(1,0,n-1,i,i,x); y=getValue(1,0,n-1,n-x); if (!y) { valid=0; break; } pos=findLeftmost(1,0,n-1,y+1); if (pos<n) decrease(1,0,n-1,pos,n-1,1); x-=(n-pos); pos=findLeftmost(1,0,n-1,y); decrease(1,0,n-1,pos,pos+x-1,1); } cout << (valid?"YES":"NO") << endl; } return 0; }
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <fstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define REP(i, a, b) for(int i = (a); i <=(b); ++i) #define FORD(i, a, b) for(int i = (a); i > (b); --i) #define REPD(i, a, b) for(int i = (a); i >=(b); --i) #define TR(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define RESET(a, v) memset(a, (v), sizeof(a)) #define SZ(a) (int(a.size())) #define ALL(a) a.begin(), a.end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> #define VII vector<II> #define endl '\n' const int N = 100005; using namespace std; int n, nTest; int a[N]; struct fenwickTree { int bit[N], n; void reset(int _n) { n = _n; REP(i, 0, n) bit[i] = 0; } void inc(int i, int v) { for(++i; i <= n; i += i & -i) bit[i] += v; } void inc(int i, int j, int v) { inc(i, v); inc(j + 1, -v); } void dec(int i, int j) { inc(i, -1); inc(j + 1, 1); } int at(int i) { int ret = 0; for(++i; i; i -= i & -i) ret += bit[i]; return ret; } } BIT; int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> nTest; while (nTest--) { cin >> n; bool NO = 0; FOR(i, 0, n) { cin >> a[i]; NO |= a[i] >= n; } if (NO) { cout << "NO\n"; continue; } sort(a, a + n, greater<int>()); BIT.reset(n); FOR(i, 0, n) BIT.inc(i, i, a[i]); FOR(i, 0, n) { a[i] = BIT.at(i); if (a[i] >= n - i || a[i] < 0) { NO = 1; break; } if (a[i] == 0) continue; int pos = i + a[i], L = pos, R = pos; int last = BIT.at(pos); int l = i + 1, r = pos; while (l <= r) { int mid = l + r >> 1; if (BIT.at(mid) == last) { L = mid; r = mid - 1; } else l = mid + 1; } l = pos, r = n - 1; while (l <= r) { int mid = l + r >> 1; if (BIT.at(mid) == last) { R = mid; l = mid + 1; } else r = mid - 1; } int len = pos - L + 1; BIT.dec(i + 1, L - 1); BIT.dec(R - len + 1, R); } if (!NO) cout << "YES\n"; else cout << "NO\n"; } return 0; }
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); const int MN = 100111; int n, a[MN], s[MN]; int main() { int ntest; GN(ntest); while (ntest--) { int n; GN(n); FOR(i,1,n) { GN(a[i]); a[i] = -a[i]; } sort(a+1, a+n+1); FOR(i,1,n) { a[i] = -a[i]; s[i] = s[i-1] + a[i]; } if (s[n] % 2) { puts("NO"); continue; } bool ok = true; int j = n; FOR(i,1,n) { long long ln = i*(i-1LL); if (j < i) j = i; while (j > i && a[j] < i) --j; ln += i*(ll) (j-i); ln += s[n] - s[j]; if (ln < s[i]) { ok = false; break; } } if (ok) puts("YES"); else puts("NO"); } return 0; }
Code mẫu của hieult
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> //#include <conio.h> using namespace std; int test,n,a[111111]; long long tong[111111],A,B,u,k,f[111111]; bool kq; int main(){ // freopen("VMDEGREE.in","r",stdin); scanf("%d",&test); for(int itest = 1;itest<=test;itest++){ scanf("%d",&n); for(int i = 1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); a[0] = 0; tong[0] = 0; for(int i = 1;i<=n;i++) tong[i] = tong[i-1]+a[i]; u = a[n]; // for(int i = 1;i<=n;i++) // printf("%d %lld\n",a[i],tong[i]); for(int i = n-1;i>=0;i--){ for(int j = u;j>a[i];j--) f[j] = i+1; u = a[i]; } f[0] = 1; //for(int i = 1;i<=n;i++) printf("*******%d\n",f[i]); if(tong[n]%2==1){ printf("NO\n"); continue; } kq = true; for(int i = n;i>=1;i--){ k = n-i+1; A = tong[n]-tong[i-1]; B = k*(k-1); if(f[k]<i){ B+=k*(i-f[k])+tong[f[k]-1]; } else B+=k*(i-1); // printf("______%lld %lld %lld\n",k,A,B); if(A>B){ kq = false; break; } } if(kq) printf("YES\n"); else printf("NO\n"); } //getch(); }
Comments