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.
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