HTML:
Ví dụ 6. Cho xâu s (ñộ dài không vượt quá 10^6 chỉ gồm 2 kí tự 'A' và 'B'. đếm số cách chọn cặp chỉ số (i,j) mà xâu con liên tiếp từ kí tự thứ i ñến kí tự thứ j của xâu s có số lượng kí tự 'A' bằng số lượng kí tự 'B'.
Dữ liệu vào trong file “AB.INP” có dạng:
gồm một dòng duy nhất chứa xâu s
Kết quả ra file “AB.OUT”
có dạng:gồm một dòng duy nhất chứa một số là kết quả bài toán.
AB.INP AB.OUT
ABAB 4
const MAX =1000000;
fi ='AB.INP';
fo ='AB.OUT';
var s :ansistring;
c :array[-MAX..MAX]of longint;
f :text;
i, sum :longint;
count :int64;
BEGIN
assign(f,fi); reset(f);
read(f,s);
close(f);
fillchar(c,sizeof(c),0);
c[0]:=1;
sum:=0;
count:=0;
for i:=1 to length(s) do begin
if s[i]='A' then sum:=sum - 1
else sum:=sum + 1;
count:=count + c[sum];
inc(c[sum]);
end;
assign(f,fo); rewrite(f);
write(f,count);
close(f);
END.
Bài tập
Ví dụ 6. Cho xâu s (ñộ dài không vượt quá 10^6 chỉ gồm 2 kí tự 'A' và 'B'. đếm số cách chọn cặp chỉ số (i,j) mà xâu con liên tiếp từ kí tự thứ i ñến kí tự thứ j của xâu s có số lượng kí tự 'A' bằng số lượng kí tự 'B'.
Dữ liệu vào trong file “AB.INP” có dạng:
gồm một dòng duy nhất chứa xâu s
Kết quả ra file “AB.OUT”
có dạng:gồm một dòng duy nhất chứa một số là kết quả bài toán.
AB.INP AB.OUT
ABAB 4
const MAX =1000000;
fi ='AB.INP';
fo ='AB.OUT';
var s :ansistring;
c :array[-MAX..MAX]of longint;
f :text;
i, sum :longint;
count :int64;
BEGIN
assign(f,fi); reset(f);
read(f,s);
close(f);
fillchar(c,sizeof(c),0);
c[0]:=1;
sum:=0;
count:=0;
for i:=1 to length(s) do begin
if s[i]='A' then sum:=sum - 1
else sum:=sum + 1;
count:=count + c[sum];
inc(c[sum]);
end;
assign(f,fo); rewrite(f);
write(f,count);
close(f);
END.
Bài tập