Editorial for VOI 11 Bài 4 - Nối điểm đen trắng


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>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;
struct rec
{
 int x,y;
};
int n,re,i;
rec a[200002];

bool cmp(rec i,rec j)
{
 return (i.x<j.x);
}

int main()
{
 cin >> n;
 fr(i,1,n*2)
 {
  scanf("%d",&a[i].x);
  if (i>n) a[i].y=1;
 }
 sort(a+1,a+n*2+1,cmp);
 i=1;
 while (i<n*2)
 {
  if (a[i].y!=a[i+1].y) 
  {
   re++; i++;
  }
  i++;
 }
 cout << re << endl;
}

Code mẫu của happyboy99x

#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> ii;
ii p[200005];
int n;

int main() {
    scanf( "%d", &n );
    for( int i = 0; i < n; ++i ) {
        scanf( "%d", &p[i].first );
        p[i].second = 0;
    }
    for( int i = n; i < (n<<1); ++i ) {
        scanf( "%d", &p[i].first );
        p[i].second = 1;
    }
    sort(p, p+(n<<1));
    bool skip = false; int cnt = 0;
    for( int i = 0; i < (n<<1)-1; ++i ) 
        if ( skip ) skip = false;
        else if ( p[i].second != p[i+1].second ) {
            ++cnt;
            skip = true;
        }
    printf( "%d\n", cnt );
    return 0;
}

Code mẫu của ladpro98

program bwpoints;
uses    math;
type    e=record
        v,t:longint;
        end;
const   fi='';
        maxN=222222;
        b=0;w=1;
var     a:array[1..maxN] of e;
        f:array[-1..maxN] of longint;
        n,res:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                read(inp,a[i].v);
                a[i].t:=b;
        end;
        for i:=n+1 to 2*n do
        begin
                read(inp,a[i].v);
                a[i].t:=w
        end;
        close(inp);
end;

procedure swap(i,j:longint);
var     t:e;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     p,i,j:longint;
begin
        if l>=r then exit;
        p:=a[random(r-l+1)+l].v;
        i:=l;j:=r;
        repeat
                while a[i].v<p do inc(i);
                while a[j].v>p do dec(j);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);dec(j);
                end;
        until i>j;
        sort(l,j);sort(i,r);
end;

procedure greedy;
var     i,black,white:longint;
begin
        i:=1;
        while i<2*n do
        begin
                if a[i].t<>a[i+1].t then
                begin
                        inc(res);
                        inc(i,2);
                end
                else
                inc(i);
        end;
end;

begin
        input;
        sort(1,n*2);
        greedy;
        write(res);
end.

Code mẫu của RR

#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 ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

pair<int,int> a[200111];
int n, f[200111];

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d", &n);
    FOR(i,1,n) {
        scanf("%d", &a[i].F);
        a[i].S = -1;
    }
    FOR(i,n+1,n+n) {
        scanf("%d", &a[i].F);
        a[i].S = 1;
    }
    n += n;
    sort(a+1, a+n+1);

    f[0] = 0;
    f[1] = 0;
    int res = 0;
    FOR(i,2,n) {
        if (a[i].S == a[i-1].S) f[i] = f[i-1];
        else f[i] = max(f[i-1], 1 + f[i-2]);
        res = max(res, f[i]);
    }
    cout << res;
    return 0;
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

int n;
vector< pair<int,int> > v;

int main()
{
//  freopen("BWPOINTS.INP","r",stdin);
//  freopen("BWPOINTS.OUT","w",stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;  scanf("%d", &x);  v.push_back(make_pair(x,0));
    }
    for (int i = 0; i < n; i++)
    {
        int x;  scanf("%d", &x);  v.push_back(make_pair(x,1));
    }
    sort(v.begin(),v.end());
    int col = -1,ret = 0;
    for (int i = 0; i < v.size(); i++)
      if (col < 0 || col == v[i].second) col = v[i].second; else
      {
            ret++;  col = -1;
        }
    printf("%d\n", ret);
}

Code mẫu của skyvn97

#include<stdio.h>
#include<queue>
using namespace std;
int n;
int c,k;
typedef priority_queue<int,vector<int>,greater<int> > pq;
pq b,w;
void process(void) {
    int i,x;
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&x);
        b.push(x);
    }
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&x);
        w.push(x);
    }
    c=-1e9-1;
    k=0;
    while ((!b.empty()) && (!w.empty())) {
        k=k+1;
        c=max(b.top(),w.top());
        while ((!b.empty()) && (b.top()<=c)) b.pop();
        while ((!w.empty()) && (w.top()<=c)) w.pop();
    }
    printf("%d",k);
}
int main(void) {
    process();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.