Editorial for VM 08 Bài 04 - Xóa số


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 happyboy99x

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

const int MAX = (int) 7e5;
bool p[MAX + 1];
int P[50000], n, k;
char s[300000], res[300000];

void eratos() {
    memset(p, -1, sizeof p); p[0] = p[1] = 0;
    for(int i = 2; i * i <= MAX; ++i) if(p[i])
        for(int j = i+i; j <= MAX; j += i) p[j] = 0;
    for(int cnt = 0, i = 0; i <= MAX && cnt < 50000; ++i)
        if(p[i]) P[cnt++] = i;
}

void create() {
    char * t = s;
    for(int i = 0, k; i < n; ++i) sprintf(t, "%d%n", P[i], &k), t += k; 
}

void solve() {
    deque<int> q; int b = 0, e = k, l = strlen(s);
    for(int i = 0, cnt = 0; i < l && cnt < l - k; ++i) {
        while(!q.empty() && s[q.back()] < s[i]) q.pop_back(); q.push_back(i);
        if(i == e) {
            while(!q.empty() && q.front() < b) q.pop_front();
            res[cnt++] = s[q.front()];
            b = q.front() + 1; e = min(k + cnt, l - 1);
        }
    }
    puts(res);
}

int main() {
    eratos();
    scanf("%d%d",&n,&k);
    create();
    solve();
    return 0;
}

Code mẫu của ladpro98

program kdel;
uses    math,sysutils;
type    element = record
        pos:longint;
        val:char;
        end;
const   maxV  = 1000000;
        fi='';
        fo='';
var     s,res:ansistring;
        sieve:array[1..maxV] of boolean;
        prime:array[1..maxV] of longint;
        stack:array[1..maxV] of element;
        k,n,d,head,tail,tpos:longint;
        oup,inp:text;

procedure initStack;
begin
        head:=1;
        tail:=0;
end;

function isEmpty:boolean;
begin
        exit((tail-head)<0);
end;

function popHead:char;
begin
        inc(head);
        exit(stack[head-1].val);
end;

function popTail:char;
begin
        dec(tail);
        exit(stack[tail+1].val);
end;

procedure pushTail(i:longint);
begin
        inc(tail);
        stack[tail].val:=s[i];
        stack[tail].pos:=i;
end;

function isPrime(n:int64):boolean;
var     i:longint;
begin
        for i:=2 to trunc(sqrt(n)) do
        if n mod i=0 then exit(false);
        exit(true);
end;

procedure initsieve;
var     i,j:longint;
begin
        fillchar(sieve,sizeof(sieve),true);
        d:=0;
        i:=2;
        while i<=1000000 do
        begin
                if sieve[i] then
                begin
                        j:=i+i;
                        while j<=1000000 do
                        begin
                                sieve[j]:=false;
                                inc(j,i);
                        end;
                        inc(d);
                        prime[d]:=i;
                        if d=50000 then exit;
                end;

                inc(i);

        end;


end;

procedure  initString;
var     i:longint;
begin
        for i:=1 to n do
        s:=s+IntToStr(prime[i]);
end;

function findmax(i,j:longint):longint;
var     c,k:longint;

begin

        while (not isEmpty) and (stack[head].pos<i) do popHead;
        for c:=tpos+1 to j do
        begin
                while (not isEmpty) and (stack[tail].val<s[c]) do popTail;
                pushTail(c);
        end;
        exit(stack[head].pos);
end;

procedure   processDel;
var     pos,i,last:longint;
begin
        pos:=1;
        last:=k+1;
        tpos:=0;
        for i:=1 to length(s)-k do
        begin
                pos:=findmax(pos,last);
                tpos:=last;
                write(oup,s[pos]);
                inc(pos);
                inc(last);
        end;
end;

procedure input;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,k);
        //readln(inp,s);
        close(inp);
        assign(oup,fo);
        rewrite(oup);

end;

begin
        input;

        initSieve;
        initString;
        initStack;
        processDel;
        close(oup);
end.

Code mẫu của skyvn97

program KDEL_VOJ;
const MAXN=1000000;
var
    notprime:array [1..MAXN] of boolean;
      s:ansistring;
      next: array[1..MAXN,0..9] of longint;
      n,k:longint;
procedure init;
    begin
        read(n,k);
      end;
procedure eratosthene;
    var
        i,j,np:longint;
            t:ansistring;
      begin
        notprime[0]:=true;
            notprime[1]:=true;
            np:=0;
            for i:=1 to MAXN do
                if not notprime[i] then
                    begin
                            for j:=2 to MAXN div i do notprime[j*i]:=true;
                              inc(np);
                              str(i,t);
                            s:=s+t;
                              if np=n then writeln(stderr,'Last prime is ',i);
                              if np=n then exit;
                        end;
    end;
procedure process;
    var
        i,j,prev,len,rem:longint;
      begin         
            rem:=k;
            prev:=0;
            len:=length(s);
            for j:=0 to 9 do next[len+1,j]:=len+1;
            for i:=len downto 1 do
                  begin
                    for j:=0 to 9 do next[i,j]:=next[i+1,j];
                        next[i,ord(s[i])-48]:=i;
                  end;  
            for i:=1 to len-k do
                  for j:=9 downto 0 do
                    if (next[prev+1,j]<=i+k) and (next[prev+1,j]<=prev+rem+1) then
                            begin
                                write(j);
                                    rem:=rem-(next[prev+1,j]-prev-1);
                                    prev:=next[prev+1,j];
                                    break;
                              end;
      end;
begin
    init;
      eratosthene;
      process;
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.