Trang chủ Tin Học Lớp 7 Nhập vào một mảng và một số nguyên dương k,in...

Nhập vào một mảng và một số nguyên dương k,in ra ước chung lớn nhất trong k dãy liên tiếp ví dụ: n = 5 k = 2 5 3 1 4 2 in ra 2 giải thích vì 5 3 ucln là 1 3 1

Câu hỏi :

Nhập vào một mảng và một số nguyên dương k,in ra ước chung lớn nhất trong k dãy liên tiếp ví dụ: n = 5 k = 2 5 3 1 4 2 in ra 2 giải thích vì 5 3 ucln là 1 3 1 ucln là 1 1 4 ucln là 1 4 2 ucln là 2 giới hạn thgian là 1s,code cho em pascal nha :>

Lời giải 1 :

{$Mode objFPC}

type int = longint;
type bool = boolean;
type long = int64;

const MaxN = trunc(1e5);

function max(a, b: int): int; begin if a > b then exit(a); exit(b); end;
function min(a, b: int): int; begin if a < b then exit(a); exit(b); end;
function __gcd(a, b: int): int;
var r: int;
begin
    while b <> 0 do begin
        r:=a mod b;
        a:=b; b:=r;
    end;
    exit(abs(a));
end;

// Do có 1 loại cây thôi nên mình đặt luôn là Tree v: đỡ dài là chính v:
// Segment Tree
type iarray = array[0..MaxN * 4] of int;
type Tree = class
  private
    arr, f: iarray;
    size: int;
  public
    constructor Create();
    constructor Create(a: iarray; n: int);
    function merge(a, b: int): int;
    procedure build(l, r, id: int);
    function __get(u, v, l, r, id: int): int;
    function get(l, r: int): int;
end;

constructor Tree.Create();
begin
    size:=0;
    fillchar(f, sizeof(f), 0);
end;

constructor Tree.Create(a: iarray; n: int);
begin
    fillchar(f, sizeof(f), 0);
    size:=n;
    arr:=a;
    build(1, n, 1);
end;

function Tree.merge(a, b: int): int; begin exit(__gcd(a, b)); end;
procedure Tree.build(l, r, id: int); 
var mid, k: int;
begin
    if l = r then begin
        f[id]:=arr[l];
        exit;
    end;
    
    mid:=(l + r) shr 1; k:=id shl 1;
    build(l, mid, k);
    build(mid + 1, r, k or 1);
    f[id]:=merge(f[k], f[k or 1]);
end;

function Tree.__get(u, v, l, r, id: int): int;
var mid, k: int;
begin
    if (r < u) or (v < l) then exit(0);
    if (u <= l) and (r <= v) then exit(f[id]);
    mid:=(l + r) shr 1; k:=id shl 1;
    exit(merge(__get(u, v, l, mid, k), __get(u, v, mid + 1, r, k or 1)));
end;

function Tree.get(l, r: int): int;
begin
    exit(__get(l, r, 1, size, 1));
end;

var St: Tree;
var a: iarray;
var i, n, k: int;
var res: int;

begin
    readln(n, k);
    for i:=1 to n do read(a[i]);
    
    St:=Tree.Create(a, n);
    res:=0;
    for i:=1 to n - k + 1 do res:=max(res, St.get(i, i + k - 1));
    writeln(res);    
end.

Thảo luận

Bạn có biết?

Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.

Nguồn : Wikipedia - Bách khoa toàn thư

Tâm sự 7

Lớp 7 - Năm thứ hai ở cấp trung học cơ sở, một cuồng quay mới lại đến vẫn bước tiếp trên đường đời học sinh. Học tập vẫn là nhiệm vụ chính!

Nguồn : ADMIN :))

Copyright © 2021 HOCTAP247