kết quả từ 1 tới 6 trên 6

Ai biết ý tưởng giải thuật của bài này như thế nào giúp minh với

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Ai biết ý tưởng giải thuật của bài này như thế nào giúp minh với

    HTML Code:
    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 
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Ai biết ý tưởng giải thuật của bài này như thế nào giúp minh với

    Bạn thử nghĩ như thế này xem:
    Với i <= j, gọi:
    Mã:
    a[i..j] = số lượng 'A' trong đoạn [i..j],
    b[i..j] = số lượng 'B' trong đoạn [i..j].
    Như vậy,
    Mã:
    a[i..j] = a[1..j] - a[1..i-1],
    b[i..j] = b[1..j] - b[1..i-1].
    Nếu đoạn [i, j] thỏa mãn số lượng 'A' bằng số lượng 'B', thì ta phải có: a[i..j] = b[i..j]. Thay thế theo như trên, ta có:
    Mã:
    a[1..j] - b[1..j] = a[1..i-1] - b[1..i-1].
    Công thức trên có nghĩa rằng: đoạn [i, j] thỏa mãn tính chất như đề bài khi và chỉ khi
    Mã:
    sự khác nhau (hiệu) của số lượng 'A' và 'B' trong đoạn [1..j] = sự khác nhau (hiệu) của số lượng 'A' và 'B' trong đoạn [1..i-1] với i <= j (nếu có). (*)
    Như vậy ta chỉ cần ghi nhận sự khác nhau giữa số lượng 'A' và 'B' khi duyệt chuỗi lần lượt từ trái sang phải. Số lượng đoạn [i, j] cần tìm chính là số lần hiệu bị trùng lặp.

    Nhìn lại đoạn code, tại mỗi bước i,
    Mã:
    sum    = hiệu của số lượng chữ số 'B' và số lượng chữ số 'A' từ 1 tới i.
    
    c[sum] = số lần xuất hiện của hiệu 'sum' này. Ví dụ, nếu giá trị của c[sum] là 1, thì hiệu này đã xuất hiện 1 lần.
    Nếu như gặp 'sum' một lần nữa thì ta chắc chắn có được một đoạn [i, j] cần tìm theo (*).
    
    count  = số đoạn [i, j] thỏa mãn yêu cầu đề bài (số lần đẳng thức (*) được thỏa mãn).
    I hope it helps.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:

    thexx 

  4. #3
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Reply: Ai biết ý tưởng giải thuật của bài này như thế nào giúp minh với

    bạn có thể giải thích giải thuật trên cho mình thông qua ví dụ trên được không ak
    Vd ABAB -> 4

  5. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Ai biết ý tưởng giải thuật của bài này như thế nào giúp minh với

    Nếu s = "ABAB", thì:
    i = 0 (ban đầu)
    Mã:
    sum = 0     count = 0     c[0] = 1 // lần đầu tiên 'sum' bằng 0.
    i = 1, s[1..1] = 'A'
    Mã:
    sum = -1     count = 0     c[-1] = 1 // lần đầu tiên 'sum' bằng -1.
    i = 2, s[1..2] = 'AB'
    Mã:
    sum = 0    count = 1     c[0] = 2 // lần thứ hai 'sum' bằng 0.
    i = 3, s[1..3] = 'ABA'
    Mã:
    sum = -1     count = 2     c[-1] = 2 // lần thứ hai 'sum' bằng -1.
    i = 4, s[1..4] = 'ABAB'
    Mã:
    sum = 0     count = 4     c[0] = 3 // lần thứ ba 'sum' bằng 0.
    Bạn nên hiểu phần giải nghĩa của mình ở phía trên cho rõ thì sẽ dễ hơn. Cái (*) mình ghi chính là ý tưởng chính của cách làm.

  6. #5
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Reply: Ai biết ý tưởng giải thuật của bài này như thế nào giúp minh với

    mình thấy ở đây ta ghi nhận số lần xuất hiện của 'A' và 'B' . mình thắc mắc không biết vì sao ta chưa duyệt mà ghi nhận đã được 1 chữ 'B'

  7. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Ai biết ý tưởng giải thuật của bài này như thế nào giúp minh với

    Ý của bạn có phải là 'c[0] = 1' không? Cái đó ko phải là 1 chữ 'B', mà là chuỗi rỗng (chưa duyệt gì cả) nên số lượng 'A' bằng số lượng 'B' (tức là hiệu là 0). Bạn lưu ý ở đây tính hiệu của số lượng 'B' và 'A', biến 'sum' chính là tính cái này.