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.

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",&deg[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

Please read the guidelines before commenting.


There are no comments at the moment.