Câu 1: Diện tích hình chữ nhật lớn nhất Cho môt hình chữ nhật có độ dài hai cạnh kề nhau là a và b. Hãy tìm hai cạnh hình chữ nhật có cùng chu vi với hình chữ
Câu 1: Diện tích hình chữ nhật lớn nhất Cho môt hình chữ nhật có độ dài hai cạnh kề nhau là a và b. Hãy tìm hai cạnh hình chữ nhật có cùng chu vi với hình chữ nhật đã cho có diện tích lớn nhất. Dữ liệu vào: tệp văn bản DTHCN.INP chỉ ghi hai số nguyên dương số a và b (a, b ≤10^9) . Kết quả: Ghi ra tệp văn bản DTHCN.OUT hai số nguyên là số đo hai cạnh của hình chữ nhật mới tìm được. Hai số ghi trên một dòng, số nhỏ trước số lớn sau Ví dụ DTHCN.INP DTHCN.OUT 1 4 2 3 Câu 2. Xâu hậu tố Trong giờ học thực hành Tin Nam đã đố Hùng bài toán sau: Cho xâu S mỗi xâu hậu tố của xâu S là các xâu sau khi xóa lần lượt từ 0 đến length(S)-1 kí tự từ trái sang phải. Ví dụ như xâu ‘abaaa’ các xâu hậu tố đó là ‘abaaa’, ‘baaa’, ‘aaa’, ‘aa’ và ‘a’. Nam muốn Hùng tính tổng sự giống nhau của xâu S với các xâu hậu tố của nó. Sự giống nhau của hai xâu A và B là chiều dài của tiền tố chung dài nhất của hai xâu đó. Xâu tiền tố của xâu A là các xâu sau khi xóa length(A)-1 kí tự về 0 kí tự tính từ phải sang trái ví dụ như A=’bbbcc’ thì các xâu tiền tố là ‘b’, ‘bb’, ‘bbb’, ‘bbbc’ và ‘bbbcc’. Ví dụ, sự giống nhau của hai xâu “abc” và “abd” là 2, còn sự giống nhau của hai xâu “aaa” và “aaab” là 3. Yêu cầu: Bạn hãy giúp Hùng viết chương trình tính tổng sự giống nhau của xâu S với mỗi hậu tố của nó. Dữ liệu vào file SIMI.INP Gồm một dòng chứa xâu S có độ dài không vượt quá 104 và chỉ bao gồm các chữ cái tiếng Anh thường. Kết quả ra: file SIMI.OUT Ghi ra một số nguyên là tổng sự giống nhau của xâu S với mỗi hậu tố của nó. Example: SIMI.INP SIMI.OUT ababaa 11 aa 3 Trong ví dụ đầu tiên, xâu S = “ababaa” và các hậu tố của xâu S là “ababaa”, “babaa”, “abaa”, "baa", “aa” và “a”. Sự giống nhau của mỗi xâu này với xâu S tương ứng là 6, 0, 3, 0, 1, 1. Do đó, câu trả lời là 6 + 0 + 3 + 0 + 1 + 1 = 11. Trong ví dụ thứ hai, câu trả lời là 2 + 1 = 3. Ràng buộc: • 70% test tương ứng với 70% số điểm có độ dài xâu S≤10^2. • 30% test tương ứng với 30% số điểm có độ dài xâu S≤10^4. pascalll helpppppppppppppp
Lời giải 1 :
Câu 1:
type int = longint;
type bool = boolean;
const prefix = 'DTHCN';
fi = prefix + '.INP';
fo = prefix + '.OUT';
var a, b, n: int;
begin
assign(input, fi); assign(output, fo);
reset(input); rewrite(output);
readln(a, b);
n:=a + b;
write(n div 2, ' ', n div 2 + n mod 2);
close(input); close(output);
end.
Câu 2:
- Cách 1: Lấy ra từng hậu tố của S để tìm độ dài tiền tố chung
type int = longint;
type bool = boolean;
const prefix = 'SIMI';
fi = prefix + '.INP';
fo = prefix + '.OUT';
var s, ss: ansistring;
i, r: int;
function f(x: ansistring): int;
var i: int;
begin
for i:=1 to length(x) do
if x[i] <> s[i] then exit(i - 1);
exit(length(x));
end;
begin
assign(input, fi); assign(output, fo);
reset(input); rewrite(output);
readln(s);
for i:=length(s) downto 1 do begin
ss:=s[i] + ss;
inc(r, f(ss));
end;
writeln(r);
close(input); close(output);
end.
// O(n*(n+1)/2)?
- Cách 2: Sử dụng mảng băm kết hợp chặt nhị phân
type int = longint;
type bool = boolean;
const prefix = 'SIMI';
fi = prefix + '.INP';
fo = prefix + '.OUT';
const base = 31;
const M = trunc(1e9) + 7;
var s: ansistring;
i, res, n: int;
H, po: array[0..10000] of int64;
function hash(i, j: int): int64;
begin
exit((H[j] - H[i - 1] * po[j - i + 1] + M * M) mod M);
end;
procedure init;
begin
po[0]:=1;
for i:=1 to n do begin
po[i]:=(po[i - 1] * base) mod M;
H[i]:=(H[i - 1] * base + ord(s[i]) - ord('a')) mod M;
end;
end;
function f(ss: int): int;
var l, r, mid: int;
begin
l:=0; r:=n - ss + 1;
while l <= r do begin
mid:=(l + r) shr 1;
if hash(1, mid) = hash(ss, ss + mid - 1) then l:=mid + 1 else r:=mid - 1;
end;
exit(l - 1);
end;
begin
assign(input, fi); assign(output, fo);
reset(input); rewrite(output);
readln(s); n:=length(s);
init;
for i:=1 to n do begin
inc(res, f(i));
end;
writeln(res);
close(input); close(output);
end.
// O(|S|log(|S|))?
Thảo luận
Có thể bạn quan tâm
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ự 8
Lớp 8 - Năm thứ ba ở cấp trung học cơ sở, học tập bắt đầu nặng dần, sang năm lại là năm cuối cấp áp lực lớn dần nhưng các em vẫn phải chú ý sức khỏe nhé!
Nguồn : ADMIN :))Copyright © 2021 HOCTAP247