Hướng dẫn giải của VM 08 Bài 04 - Xóa số
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.
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 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.
Bình luận