Hướng dẫn giải của VM 11 Bài 01 - Pirate đãng trí
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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(); }
Bình luận