Hôm nay bài không phải là khó.

Tóm tắt đề bài

ballmachine

Cho một cây \(N\) đỉnh có gốc, mỗi đỉnh chứa tối đa 1 quả bóng. Quả bóng từ cha sẽ rơi xuống nút con nếu có thể. Nếu có nhiều nút con thỏa mãn, chọn nút con có cây con chứa nút có số thứ tự nhỏ nhất. Thực hiện \(Q\) truy vấn 1 trong 2 loại:

  • Lần lượt cho \(k\) quả bóng vào đỉnh gốc. In ra nút chứa quả cuối cùng khi bóng rơi xong.
  • Lấy quả bóng từ đỉnh \(u\) ra. Đếm số quả bóng bị rơi xuống.

Giới hạn

\(1 \le N, Q \le 10^5\)

numbers

Cho 2 số \(A\) và \(B\). Đếm số các số \(x\) thỏa mãn:

  • \(A \le x \le B\)
  • Nếu coi \(x\) là một xâu, không tồn tại một xâu con nào của \(x\) có độ dài lớn hơn 1 và đối xứng.

Giới hạn

\(0 \le A \le B \le 10^{18}\)

pipes

Cho đồ thị \(N\) đỉnh \(M\) cạnh. Mỗi cạnh có một chỉ số \(A_i\) chưa biết. Cho biết với mỗi đỉnh giá trị \(B_i\) là tổng các \(A_i\) của các cạnh kề với đỉnh đó. Kiểm tra xem có tồn tại duy nhất 1 nghiệm thỏa mãn, và in ra nếu có.

Giới hạn

\(1 \le N \le 10^5\), \(1 \le M \le 5 \times 10^5\)

Trong 25% số test input là cây.

brunhilda

Cho một tập \(N\) số nguyên tố \(A_i\). Với số \(x\), ta có thể biến đổi như sau trong một bước để ra số \(y\):

  • Chọn \(k = A_i\) với \(i\) bất kì
  • \(y = x - x \mod k\)

Có \(Q\) truy vấn, mỗi truy vấn cho một số \(X\). Tìm số bước nhỏ nhất để biến đổi \(X\) thành 0. (Số bước có thể là vô tận)

Giới hạn

\(1 \le N \le 10^5\), \(1 \le Q \le 10^4\), \(1 \le A_i, X \le 10^7\)

Lời giải

ballmachine

Tính min cây con

Theo đúng yêu cầu của bài toán, trước tiên ta tính \(V[u]\) - min chỉ số tất cả các nút của cây con gốc \(u\). Việc này có thể làm đơn giản bằng 1 lần dfs, độ phức tạp \(O(N)\).

Tìm thứ tự đặt

Ta có thể tóm tắt thuật toán đặt bóng như sau, từ một cây đã dồn bóng xuống. Giả sử ta đang ở nút \(v\):

  • Sort các cạnh \((v, u)\) theo \(V[u]\) tăng dần
  • Với mỗi cạnh \((v, u)\) theo thứ tự:
    • Tìm chỗ đặt ở \(u\)
    • Nếu tìm thấy: thoát. Nếu không, tiếp tục
  • Không có cây con nào còn chỗ. Nếu \(v\) có chỗ, đặt ở \(v\). Nếu không, trả về không đặt.

Ta có thể chỉnh sửa một chút để tạo ra mảng từng nút theo “priority” như sau, giả sử ta đang ở \(v\):

  • Sort các cạnh \((v, u)\) theo \(V[u]\) tăng dần
  • Với mỗi cạnh \((v, u)\) theo thứ tự:
    • dfs xây mảng xuống \(u\)
  • Đẩy \(v\) vào mảng

Ta sẽ được một dãy \(P\) theo kiểu postfix, dễ dàng nhận thấy nếu \(i < j\) thì quả bóng luôn được rơi xuống \(P_i\) trước \(P_j\).

Xây test mẫu ta được 5 8 6 3 7 4 2 1

Như vậy, việc đặt thêm bóng chỉ đơn giản là tìm \(i\) bé nhất mà \(P_i\) chưa có bóng, và đặt vào đó. Việc này có thể làm trong \(O(1)\), với 1 mảng đánh dấu.

Xóa như thế nào?

Ta nhận thấy một nút \(v\) không thể rỗng nếu như tồn tại một tổ tiên \(p_v\) có bóng. Do vậy, từ \(v\) lên gốc sẽ là một đoạn liên tiếp có bóng, kế theo là các nút không có bóng lên đến gốc. Vì thế, bản chất việc “dồn bóng” chỉ là tìm tổ tiên \(p_v\) cao nhất vẫn chứa bóng, và đưa quả bóng vào \(v\) - hay nói cách khác, thay vì xóa \(v\) ta xóa \(p_v\).

Để tìm \(p_v\), ta chỉ cần sử dụng chặt nhị phân, sau đó kiểm tra xem tổ tiên ta chặt có chứa bóng hay không. Ta có thể dễ dàng cài đặt thuật toán này bằng nhảy 2 mũ, với độ phức tạp \(O(\log N)\).

// par[v][i] là cha 2 mũ i của v
int len = 0, cur = v;
for (int i = 17; i >= 0; --i) {
	// 2^17 + 2^16 + ... + 1 = 2^18 - 1 > 1e5
	if (par[cur][i] != 0 && ball[par[cur][i]]) {
		// ^ cha này tồn tại  ^ có bóng
		len += (1 << i); cur = par[cur][i];
		// ^ khoảng cách tăng 2^i
	}
}
printf("%d\n", len); // khoảng cách chính là số bóng rơi
removeBall(cur); // xóa bóng ở cur

Như vậy ta có thuật toán \(O(N \log N + Q \log N)\). Phần \(N \log N\) bị tạo ra do việc tính cha 2 mũ.

numbers

Tính chất đối xứng

Một xâu đối xứng sẽ thuộc 1 trong 2 loại:

  • Xâu chẵn, nửa đầu bằng nửa sau lật lại.
  • Xâu lẻ, bỏ phần tử giữa ta có xâu đối xứng chẵn.

Ta nhận thấy, trong trường hợp thứ nhất, luôn tồn tại 2 kí tự liên tiếp giống nhau (2 kí tự ở giữa). Trong trường hợp 2, có thêm một kí tự khác nằm giữa 2 kí tự giống nhau.

Như vậy, điều kiện không tồn tại xâu con đối xứng rất đơn giản:

  • Không tồn tại \(d_i = d_{i + 1}\), và
  • Không tồn tại \(d_i = d_{i + 2}\)

Với \(d_i\) là chữ số thứ \(i\) của số cần tìm.

Quy hoạch động

Để đơn giản hóa việc đếm trong đoạn \([A..B]\) ta có thể tính số phần tử nhỏ hơn \(B + 1\) rồi trừ đi số phần tử nhỏ hơn \(A\). Việc chỉ viết 1 hàm qhđ sẽ đơn giản hóa bài toán. Ta tập trung vào bài tính số phần tử thỏa mãn nhỏ hơn \(X\).

Công thức

Gọi \(f[i][a][b][sm]\) là số các số đã xây \(i\) chữ số đầu tiên, 2 chữ số cuối cùng đã xây là \(a\) và \(b\), và \(sm\) là biến quản lí việc so sánh số đang xây với \(X\) (1 nếu đã nhỏ hơn, 0 nếu vẫn bằng nhau).

Từ đây ta sẽ chuyển trạng thái bằng cách chọn chữ số điền tiếp theo (\(n\)) thỏa mãn:

  • \(n \neq a\) và \(n \neq b\)
  • \(sm = 1\) hoặc \(n \le X_{i + 1}\)

Độ phức tạp sẽ là \(O(\log_{10}N \times 10^3)\). Tất nhiên do tính chất phải lưu 2 chữ số nên phần cài đặt sẽ lằng nhằng, đồng thời để dễ dàng xét số chữ số của số đang qhđ ta cũng cần một số ý tưởng kì dị để quản lí (ví dụ, bạn phải xây các số 0 phía trước và cho phép đối xứng).

Quản lí trạng thái

Mình hay làm theo kiểu coi \(X\) và số cần tìm như các số có 20 chữ số với số 0 đứng đầu khi qhđ chữ số. Tuy nhiên riêng với bài này việc xử lí trở nên khó khăn hơn khi các số 0 đứng đầu không tạo ra xâu con đối xứng. Vì vậy, mình làm như sau:

  • Thay vì gọi chữ số 0 ở đầu là 0 gây nhầm với số 0 ở giữa số, ta gọi số này là -1
  • Mình cho phép đặt thêm -1 thoải mái, nhưng chỉ khi số ngay trước cũng là -1.
  • Tất nhiên, chữ số đầu tiên không phải -1 phải là một chữ số khác 0.
  • Và cuối cùng, yêu cầu trên sẽ xóa bỏ số 0 khỏi tập thỏa mãn, vì vậy về sau bạn nên thêm riêng số này nếu cần.

Để đơn giản ta coi \(f[0][-1][-1][0] = 1\), do ta có thể coi có vô tận chữ số -1 phía trước. Đáp số sẽ là tổng các \(f[20][a][b][1]\).

pipes

Giải trên cây

Ta có cách giải sau trên cây:

  • Chọn một lá \(v\). Hiển nhiên nếu cây có trên 1 đỉnh thì sẽ tồn tại 1 lá.
  • Xét cạnh \((v, p_v)\). Hiển nhiên trọng số cạnh này chính là \(B[v]\). Ta giải được cạnh này, và xóa \(v\) khỏi cây, giảm \(B[p_v]\).
  • Đồ thị còn lại cũng là một cây, ta tiếp tục làm đến khi không còn cạnh nào.

Do ở mỗi bước, trọng số cạnh là xác định, nên trên cây luôn tồn tại 1 đáp án duy nhất. Ta có thể giải với độ phức tạp \(O(N)\).

Đồ thị… lừa đảo

Vì mỗi thành phần liên thông không liên quan đến nhau, ta có thể giải riêng. Do vậy từ đây ta coi đồ thị là liên thông.

Với bài toán đã cho, ta có thể coi đây là một hệ \(N\) phương trình \(M\) ẩn. Hiển nhiên nếu \(M > N\) thì hệ sẽ có vô số nghiệm. Vì vậy, ta chỉ cần xét bài toán khi \(M \le N\).

Nếu \(M < N\) và đồ thị liên thông thì đây là cây, ta giải được ở trên. Vậy ta chỉ cần quan tâm đến \(M = N\), tức đồ thị “mặt trời”: một chu trình đơn, với mỗi đỉnh trong chu trình có thể là gốc một cây.

Chu trình

Với phần cây “tua rua” trên mỗi đỉnh, cách giải giống hệt như giải từng cây ở trên. Bài toán chỉ còn lại một chu trình đơn duy nhất.

Trước tiên, ta cần biết nếu chu trình có độ dài chẵn thì sẽ có vô số nghiệm. Thật vậy, giả sử ta tìm được một nghiệm. Theo chiều kim đồng hồ, tăng các cạnh chẵn thêm 1 và giảm các cạnh lẻ đi 1. Ta thấy tổng của tất cả các đỉnh đều không đổi. Vì vậy, từ một nghiệm ta có thể tạo ra vô số nghiệm khác.

Như vậy, ta chỉ giải trường hợp độ dài lẻ. Ta tính tổng sau:

\[P = B_1 + B_2 + … + B_{2k + 1}\] \[ = (A_{2k + 1} + A_1) + (A_1 + A_2) + … + (A_{2k} + A_{2k + 1})\] \[ = 2(A_1 + A_2 + … + A_{2k + 1})\]

Và

\[ Q = B_2 + B_4 + … + B_{2k} \] \[ = (A_1 + A_2) + (A_3 + A_4) + … + (A_{2k - 1} + A_{2k}) \]

Dễ dàng nhận thấy \(A_{2k + 1} = P / 2 - Q\). Khi đã có \(A_{2k + 1}\), ta có thể tính được tất cả các số còn lại với độ phức tạp là \(O(N)\).

Như vậy tổng cộng thuật toán của ta là \(O(N)\).

brunhilda

Quy hoạch động

Gọi \(f[i]\) là số bước nhỏ nhất để đưa \(i\) về 0. Ta có:

  • \(f[0] = 0\)
  • \(f[i] = \min\limits_{i \mod A[j] > 0}^ {1 \le j \le N}f[i - i \mod A[j]] + 1\)

Ta sẽ cần tính \(f[i]\) với mọi \(1 \le i \le 10^7\). Sau khi tính thì mỗi truy vấn ta trả lời trong \(O(1)\). Độ phức tạp sẽ là \(O(10^7N)\), quá lớn, cần cải tiến.

Số lần thay đổi giá trị

Xét \(1 \le i \le N\). Giá trị tối ưu của \(f[k \times A[i]]\) sẽ được cập nhật cho các số từ \(k A[i] + 1\) đến \((k + 1)A[i] - 1\). Như vậy, có \(10^7 / A[i]\) lần hàm thay đổi giá trị.

Do \(A[i]\) là các số nguyên tố khác nhau, nên chỉ có \(10^7 / 2 + 10^7 / 3 + … \le 29 \times 10^6\) (10^5 số nguyên tố đầu) lần đổi giá trị.

Hơn nữa, ta cũng có thể thấy \(f[kA[i]] \le f[(k + 1)A[i]] \le f[kA[i]] + 1\). Ta sẽ tìm cách sử dụng tính chất này khi tối ưu.

Tính nhanh

Trước tiên, nếu một số là bội của tất cả các số \(A[i]\) thì chắc chắn số đó không thể biến đổi được, ta sẽ không tính trường hợp đó.

Không khó để nhận ra \(f[i]\) là hàm không giảm khi \(i\) tăng, vì thế ta có thể giữ lại một deque các \(f[j]\) còn thỏa mãn đứng trước, và xóa dần đuôi khi chúng không còn được tính nữa.

\(f[j]\) không được tính nữa khi với mọi \(A[k]\) là ước của \(j\) thì \(i \ge A[k](j / A[k] + 1)\).

Ta có thể lưu lại bộ đếm của từng \(j\), tiến deque khi phần tử đầu tiên có bộ đếm về 0.

Tổng độ phức tạp sẽ là \(O(29 \times 10^6 + N)\).