Hướng dẫn giải của Chơi bi-a 1 lỗ


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.

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

uses math;
var l,r:array[0..100000] of longint;
    n,i,x,m:longint;

begin
        read(n);
        for i:=1 to n do r[i]:=i+1;
        for i:=2 to n do l[i]:=i-1;
        m:=0;
        for i:=1 to n do
        begin
                read(x);
                if r[x]<m then
                begin
                        writeln('YES');
                        halt;
                end;
                r[l[x]]:=r[x];
                l[r[x]]:=l[x];
                m:=max(m,x);
        end;
        writeln('NO');
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 100000

int prev[N+2], next[N+2], n;

int main() {
    scanf("%d",&n);
    fo(i,1,n) { prev[i] = i+1; next[i] = i-1; }
    int last = 0;
    rep(i,n) {
        int v; scanf("%d",&v);
        if( v != next[last] && v < last ) { puts("YES"); return 0; }
        next[prev[v]] = next[v];
        prev[next[v]] = prev[v];
        last = v;
    }
    puts("NO");
    return 0;
}

Code mẫu của RR

var
  a,s:array[1..1000111] of longint;
  u,i,top,n:longint;
begin
  read(n);
  for i:=1 to n do read(a[i]);
  top:=0; u:=1;
  for i:=1 to n do
    begin
      inc(top); s[top]:=i;
      while (a[u]=s[top]) do
        begin
          inc(u);
          dec(top);
        end;
    end;

  while (top>0) and (a[u]=s[top]) do
    begin
      dec(top);
      inc(u);
    end;

  if top>0 then writeln('YES')
  else writeln('NO');
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{
long n;
int vaolo[100001],a[100001],t=0;
//FILE *p;
//p=fopen("D:\\Hoc tap\\test\\CHeat\\CHEAT.IN4","r");
scanf("%ld",&n);
for(long i=1;i<=n;i++)
  {
  scanf("%d",&a[i]);
  vaolo[i]=0;
  }
vaolo[a[1]]=1;
for(long i=2;i<=n;i++)
  {
  vaolo[a[i]]=1;
  if(a[i]<a[i-1])
    {
    for(long j=a[i]+1;j<=a[i-1]-1;j++)
      if(vaolo[j]==0)
        {
        printf("YES");
        t=1;
        break;
        }
    if(t==1)
      break;    
    }
  }  
if(t==0)
  printf("NO");
//getch();
}

Code mẫu của ll931110

program CHEAT; 
const 
        fi=''; 
        fo=''; 
var 
        f:text; 
        free:array[1..100000] of boolean; 
        i,j,n,h,k:longint; 
        angian:boolean; 
procedure xuly; 
begin 
        assign(f,fi); 
        reset(f); 
        readln(f,n); 
        fillchar(free,n,true); 
        angian:=false; 
        for i:= 1 to n do 
                begin 
                readln(f,k); 
                free[k]:=false; 
                if h>k then 
                for j:= k to h do 
                       if free[j] then 
                       begin 
                       angian:=true; 
                       exit; 
                       end; 
                h:=k; 
                end; 
        close(f); 
end; 
procedure xuat; 
begin 
        assign(f,fo); 
        rewrite(f); 
        if angian=true then write(f,'YES') 
        else 
        write(f,'NO'); 
        close(f); 
end; 
begin {main} 
xuly; 
xuat; 
end.

Code mẫu của khuc_tuan

const
    maxn = 100000;

var
    bit, vt, a : array[1..maxn] of longint;
    x, k, t, p, i, j, n : longint;
    f : array[0..16,1..maxn] of longint;

procedure add(i, v : longint);
begin
    while i<=n do begin
        inc(bit[i],v);
        inc(i,i and (-i));
    end;
end;

function tinh(i : longint) : longint;
var res : longint;
begin
    res := 0;
    while i>0 do begin
        inc(res,bit[i]);
        i := i and (i-1);
    end;
    tinh := res;
end;

function find(i : longint) : longint;
var
    l, r, m, a : longint;
begin
    a := tinh(i);
    l := 1;
    r := i;
    while l<r do begin
        m := (l+r) div 2;
        if tinh(m)=a then r := m
        else l := m+1;
    end;
    find := l;
end;

begin
    read(n);
    for i:=1 to n do begin
        read(a[i]);
        vt[a[i]] := i;
        f[0,i] := a[i];
    end;
    p := 1;
    for i:=1 to 16 do begin
        for j:=1 to n-p+1 do begin
            f[i,j] := f[i-1,j+p];
            if f[i,j]>f[i-1,j] then f[i,j] := f[i-1,j];
        end;
        p := 2*p;
    end;
    for i:=n downto 1 do begin
        if (i<=n-2) and (tinh(a[i])>0) then begin
            j := vt[find(a[i])];
            t := trunc(ln(j-i+1)/ln(2) + 1e-9);
            p := 1;
            for x:=1 to t do p:=2*p;
            k := f[t,j-p+1];
            if k>f[t,i] then k := f[t,i];
            if k<a[j] then begin
                writeln('YES');
                exit;
            end;
        end;
        add(a[i],1);
    end;
    writeln('NO');
end.

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.