DIFFSTR – spoj

Đề bài:

Thuật toán:

Solution ăn 60%:

Xét xâu S và dãy x[1..n] thỏa mãn 1 <= x[i] <= length(S) và x[i] > x[i – 1]. Với mỗi dãy x, ta thu được 1 xâu con của S: S[x[1]] S[x[2]] S[x[3]]… S[x[n]]

Để tạo ra được các xâu con phân biệt của S mà 2 phần tử liền kề khác nhau, ta chỉ xét đến những dãy x thỏa mãn điều kiện sau:

  1. S[x[i]] != S[x[i – 1]]
  2. Không tồn tại số k thỏa mãn x[i] < k < x[i + 1] và S[k] == S[x[i + 1]] (nói nôm na là nếu chọn ký tự ch nào đó để cho vào xâu con thì luôn chọn ký tự có chỉ số nhỏ nhất)

(cái đoạn in nghiêng này hình như không cần thiết :)))

 Gọi g[i][j] là số cách chọn dãy x[] có i phần tử mà x[i] = j.

 g[i][j] sẽ cập nhật cho g[i + 1][k] mà k là những giá trị mà khi thêm x[i + 1] = k thì vẫn đảm bảo điều kiện của dãy x[] ở trên (nhận xét là sẽ có không quá 26 giá trị của k)

g[i + 1][k] += g[i][j]

Cuối cùng, để tính kết quả bài toán:

Gọi:

  • f[i][j][0] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con bằng với xâu b[1..i]
  • f[i][j][1] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con lớn hơn xâu b

Với mỗi f[i][j][t], tìm các giá trị k thỏa mãn thêm x[i + 1] = k vẫn đảm bảo thỏa mãn điều kiện của x[]:

– Nếu t = 1 thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] = b[i + 1] thì f[i + 1][k][0] += f[i][j]

– Nếu t = 0, S[x[k]] > b[i + 1] thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] < b[i + 1] thì không làm gì hết

Kết quả bài toán = tổng f[i][j][1] + tổng f[length(b)][j][0]

Đpt ít hơn O(n * n * log(n)) n * n là mảng f, log(n) để tìm k, thực chất là không cần tính hết mảng f nên đpt sẽ nhỏ hơn khá nhiều

Solution ăn 100%:

QHĐ tương tự như trên, ta có thể tính được số xâu con của S[i..n] bắt đầu bằng ký tự ch bất kỳ mà thỏa mãn 2 ký tự liền kề khác nhau trong O(1)

Duyệt i từ đầu đến cuối xâu b, đến bước thứ i, đếm số xâu con trong S có dạng b[1..i – 1] + x với x là 1 xâu < S[i..m]. Số lượng xâu x = (số xâu con trong S[k..n] (k là vị trí kết thúc đầu tiên của xâu con b[1..i – 1] trong xâu S) bắt đầu bằng các ký tự < b[i]) + 1 (xâu rỗng)

Kết quả bài toán là tổng của các xâu trên – 1 (xâu rỗng)

Lưu ý là trong khi duyệt, nếu xâu b[1..i] không thỏa mãn điều kiện  2 ký tự liền kề khác nhau thì phải dừng duyệt ngay lập tức.

Solution O(N): của anh Nguyễn Tấn Sỹ Nguyên ( flash_mt )

Gọi F[i] là số cách chọn 1 subsequence ko có 2 phần tử kề nhau bằng nhau với S[i] là phần tử đầu tiên. Có thể tính F[] trong O(26N).

Sau đó ta đếm số lượng subsequence A thỏa A[1..k] = B[1..k] và A[k + 1] > B[k + 1]. Với mỗi giá trị k, xét A[k + 1] = c với c > B[k + 1], tìm vị trí u đầu tiên trong đoạn còn lại thỏa S[u] = c và tăng kết quả lên f[u]. Độ phức tạp của bước này là O(26(M + N)).

Code:

  • (đang cập nhập)
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*