### CF1879F *2800 ★
Giá trị của một điểm được tính bằng h_i * ceil(a_i / x).
Bước đầu tiên là sử dụng phương pháp phân đoạn trực tiếp, chia thành sqrt(n) khoảng và duyệt qua từng khoảng sẽ có độ phức tạp là O(Tn * sqrt(a_i)).
Tuy nhiên không có bảo đảm về tổng n, nên ta cần tìm cách sử dụng log.
Nhớ lại chuỗi điều hòa, khi liệt kê x, các phần tử có cùng giá trị làm tròn lên sẽ nằm trong một khoảng, từ đó chỉ cần tìm giá trị lớn nhất trong khoảng đó.
Sử dụng bảng ST, độ phức tạp sẽ là O(Tn * log n).
### CF1879E *2400 ★
Đặt c_i là màu sắc nối từ đỉnh i đến cha của nó, rõ ràng c_i != c_x, với x là con của i.
Vì vậy, ý tưởng đầu tiên là tô màu các đỉnh ở cùng mức độ bằng màu sắc giống nhau.
Tuy nhiên, vấn đề phát sinh ở các đỉnh bậc 2, không thể xác định được cha của nó.
Tận dụng ba màu sắc, tạo ra một chu trình, từ đó lựa chọn hai màu sắc để xác định được cha.
### CF1870F *2900 ★
Các chuỗi có độ dài bằng nhau và sắp xếp từ điển tăng dần.
Khi phân tích, thấy rằng các chuỗi thỏa mãn nằm trong một khoảng nào đó, có thể áp dụng thuật toán nhị phân.
Tính toán thứ tự từ điển cũng dựa trên việc phân loại theo độ dài.
### CF1866L *2400 ★
Lặp lại với mỗi k, sau đó chia thành từng đoạn có độ dài N, tổng cộng có M đoạn, mỗi đoạn có thể lấy được hộp từ hậu tố, giải quyết bằng cách brute-force sẽ có độ phức tạp là O(m^2).
### CF1284E *2500 ★
Lặp lại với mỗi p, tìm bốn điểm, đảm bảo không có hai góc liền kề vượt quá 180.
Sử dụng nguyên lý bù trừ, trừ đi trường hợp tất cả đều nằm ở nửa đường tròn.
Chú ý tới độ chính xác, cần phải kiểm soát kỹ lưỡng.
const lb Pi = acos(-1.0l);### CF1497D *2500 ★
Không biết làm.
Khoảng nhớ nhỏ, không thể dùng dp.
Một cách thông minh là sắp xếp tất cả các chuyển đổi (i,j) theo thứ tự 2^i - 2^j.
Sau đó thực hiện chuyển đổi từ nhỏ đến lớn.
Tương tự như tìm đường đi đơn điệu tăng trên đồ thị.
### CF1487G *2700 ★
Tối đa có ba trường hợp không hợp lệ, áp dụng nguyên lý bù trừ.
Bù trừ không cần quan tâm cụ thể là hai chữ cái nào, chỉ cần chú ý số lượng đã chọn, do đó có thể dùng dp brute-force, độ phức tạp là O(n^3).
### CF1019D *2700 ★
Lặp lại với mỗi cạnh, sau đó sắp xếp các đỉnh khác theo khoảng cách so với đỉnh này, có thể áp dụng thuật toán nhị phân.
Phát hiện ra rằng khi sắp xếp các cạnh theo góc cực, mỗi lần sẽ thay đổi thứ tự tương đối của hai đỉnh.
### CF917C *2900 ★
Sử dụng kỹ thuật nén bit, đặt f_i_S là trạng thái của i, trước k vị trí có người hay không là S, mỗi lần di chuyển người đứng đầu tiên trong S về phía trước.
Các vị trí đặc biệt thì xử lý bằng dp.
Mã nguồn khá khó viết.
### CF1500E *3300 ★
Dễ dàng nhận ra rằng khi liệt kê kích thước tập hợp x, tương đương với khoảng giữa x số nhỏ nhất và x số lớn nhất, sau đó tìm phép kết hợp.
Khi phân tích, thấy rằng x có một tiền tố là các khoảng không giao nhau, hậu tố là các khoảng không giao nhau, phần còn lại có thể hợp nhất thành một khoảng lớn, và điểm |S|/2 chắc chắn nằm trong khoảng lớn này.
Vì vậy, chia đôi bên trái và bên phải, độ phức tạp là O(n * log^2 n).
Mã nguồn khá khó viết, còn bị giới hạn thời gian chạy.
### CF1103C *2700 ★
Chạy cây DFS theo kiểu quy tắc.
Nếu độ sâu lớn hơn n/k thì dừng.
Ngoài ra, số lượng lá ít nhất sẽ là k.
Xét việc tìm một chu trình cho mỗi lá, ngoài các cạnh cây còn có hai cạnh không phải cây (x,y),(x,z).
Vì vậy, có ba cách chọn hai cạnh không phải cây để tạo chu trình, chứng minh thấy luôn tồn tại một cách thỏa mãn.
### CF1103D *3100 ★
Câu hỏi thú vị.
Lưu ý rằng các thừa số nguyên tố của gcd rất nhỏ, nhiều nhất chỉ có M=11 thừa số.
Sử dụng kỹ thuật nén bit, xét mỗi số, xem nó có loại bỏ các thừa số nguyên tố thuộc tập hợp S một cách hợp lệ hay không.
Cách tìm tập hợp này là loại bỏ các thừa số nguyên tố không liên quan, thấy rằng các số còn lại chắc chắn không nhiều, lưu kết quả trực tiếp.
Đến đây, tương đương với việc chọn một tập hợp các tập hợp sao cho phép kết hợp là tập hợp toàn phần tử.
Tuy nhiên mỗi số chỉ có thể chọn một khoảng, khá phức tạp, và độ phức tạp nổ ra.
Xét có chi phí, và nhiều nhất chọn M tập hợp, do đó đối với mỗi S, chỉ cần xử lý M khoảng có chi phí nhỏ nhất.
Sau đó brute-force, khi thực hiện dp chỉ cần liệt kê các tập hợp con. Độ phức tạp là O(3^M * M^2).
Xem một kỹ thuật thú vị: ngăn xếp cơ sở.
Nếu có n vật phẩm, tìm khoảng nhỏ nhất chứa đủ để 0/1 knapsack đạt được f_m >= v.
Lưu ý rằng việc thêm vào dễ dàng, nhưng không hỗ trợ việc xóa bỏ.
Rõ ràng rằng khoảng này thỏa mãn hai con trỏ, nhưng việc đẩy ra khỏi đầu trái khó duy trì.
Xét mở hai ngăn xếp, thêm trực tiếp vào ngăn xếp bên phải, sau đó duy trì giá trị tiền tố dp của ngăn xếp, nếu cần đẩy ra, liên tục đẩy ra đỉnh ngăn xếp bên trái cho đến khi nó rỗng, sau đó chuyển tất cả các phần tử của ngăn xếp bên phải sang ngăn xếp bên trái.
Vì vậy mỗi phần tử chỉ được đưa vào tối đa hai lần, và việc kết hợp hai ngăn xếp cũng đúng độ phức tạp, tổng độ phức tạp là O(nm).
### CF1416E *3200 ★
Câu hỏi chất lượng thấp, duy trì dp bằng cây cân bằng.
### CF1886F ★
Xem lời giải
### CF1120F *3100 ★
? ? ?
Nếu bắt đầu gửi thư, hộp thư sẽ luôn được sử dụng, tương đương mỗi đoạn liên tục đầu tiên sẽ mất đi đóng góp.
Lặp lại từ cuối đến đầu vị trí gửi thư đầu tiên, sau đó cộng tổng đóng góp của mỗi điểm.
### CF1120E *2600 ★
Câu hỏi tìm kiếm.
### CF1129E *3100 ★
D làm lâu quá, câu này có thể làm được.
Xét các thông tin cơ bản có thể hỏi ra, phát hiện đầu là 1, giữa đặt x, cuối cùng đặt phần còn lại, từ đó có thể hỏi ra kích thước cây con của x.
Xét việc bắt đầu từ gốc, xác định con, lưu ý rằng giữa đặt x, hai đầu là (1,y) có thể xác định được y có nằm trong cây con của x hay không.
Chia đôi, cây con có kích thước lớn nhất của y chắc chắn sẽ là con của x.
Loại bỏ y, đệ quy y tiếp theo.
Số lượng truy vấn là O(n * log n).
### CF1129D *2900 ★
Câu hỏi quy tắc.
Thực hiện dp, sau đó tương đương với việc duy trì một khoảng cộng trừ, truy vấn tổng các giá trị dp không vượt quá k.
Phân chia khối lớn.
### abc311_h *3605 ★
Câu hỏi tuyệt vời, công nghệ mới nhất.
Lời giải lg đầy lỗi về độ phức tạp, tốt nhất là đọc lời giải chính thức.
Đây là bài toán knapsack trên cây có ràng buộc, không thể hợp nhất vì độ phức tạp là O(m).
Sau đó nghĩ đến bài toán knapsack cổ điển, cách làm cổ điển là chạy dãy dfs, sau đó thực hiện dp trên dãy dfs, nếu một điểm không được chọn thì cây con của nó cũng không được chọn, nhảy đến vị trí tiếp theo, ngược lại thì nhảy vào cây con, như vậy chỉ cần hỗ trợ việc thêm một mặt hàng vào knapsack, độ phức tạp là O(nm).
Nếu chạy bất kỳ một thành phần liên thông nào, cần thêm phân chia cây, nhưng đáp án trong cây con sẽ khó xử lý (có thể không thể).
Sau đó có một công nghệ mới, cảm thấy hoàn toàn đánh bại dp trên dãy dfs.
Tính chất cơ bản của dp trên dãy dfs là, tương tự xây dựng một máy trạng thái, mỗi điểm nối đến con đầu tiên hoặc điểm ngoài cây đầu tiên, sau đó một đường đi trên máy trạng thái đại diện cho một thành phần liên thông trên cây chứa gốc, sau đó thực hiện dp trên đó.
Tuy nhiên, điều này khá tách rời với thông tin trong cây con, và chỉ hỗ trợ việc duy trì thành phần liên thông trên cây, gặp điều kiện ràng buộc trên cây không liên thông thì yếu, tức là khi thực hiện dp đến một điểm, thông tin của cha là không rõ ràng.
Từ đó suy nghĩ rất hay là truyền thông tin dp khi dfs đến i vào con, sau đó truyền ra.
function dfs(c, dp) // Hàm của贺
Dp[0] <- dp
Dp[1] <- dp
for d in {con của c} làm
Dp[0] <- dfs(d, Dp[0])[0]
Dp[1] <- dfs(d, Dp[1])[1]
kết thúc cho
cho i = 0 đến X - W[c] làm
chmax(Dp[C[c]][i + W[c]], Dp[C[c] ^ 1][i] + B[c])
kết thúc cho
trả về DpVì thông tin bên ngoài cách chọn của tôi thực sự không ảnh hưởng, chỉ cần chuyển mảng dp bên ngoài trực tiếp xử lý, điều kiện ràng buộc có thể hạn chế khi truyền về cha.
Sau đó mỗi lần truyền về cha, thêm điểm này vào.
Lưu ý rằng độ phức tạp của dp này là O(m2^n), khá yếu.
Lưu ý rằng độ phức tạp kém chủ yếu là do mỗi cây con được chia thành hai trường hợp 0/1 riêng biệt để dp, nếu chỉ có một con, có thể kế thừa trực tiếp trạng thái dp của con, vì không có ràng buộc từ các con khác.
Từ đó dẫn đến ý tưởng tương tự như dsu trên cây, đệ quy xuống con nặng trước, kế thừa thông tin trực tiếp.
function dfs(c, dp)
nếu c không phải lá thì
h = (con nặng của c)
Dp <- dfs(h, dp)
cho d trong {con của c} / {h} làm
Dp[0] <- dfs(d, Dp[0])[0]
Dp[1] <- dfs(d, Dp[1])[1]
kết thúc cho
khác
Dp[0] <- dp
Dp[1] <- dp
kết thúc nếu
cho i = 0 đến X - W[c] làm
chmax(Dp[C[c]][i + W[c]], Dp[C[c] ^ 1][i] + B[c])
kết thúc cho
trả về DpKhi phân tích độ phức tạp.
Nếu có k con, thì giá trị lớn nhất chắc chắn là a_1 = a_2 = ... = a_k.
f(n) = f(n/k)(2k-1) + O(m)
Rõ ràng k=2 tối ưu, độ phức tạp là O(n^(log_2 3)m) = O(n^(1.59)m).
Tuy nhiên lưu ý rằng bây giờ dp thu được chỉ có thể tính ra đáp án cho cả cây, không thể tính ra đáp án cho mỗi cây con, bởi vì mỗi lần đệ quy đều truyền thông tin bên ngoài vào.
Để tính thông tin của một điểm, chỉ cần truyền một trạng thái trống vào, nhưng độ phức tạp nhân với n.
Cũng có thể dsu, truyền thông tin trống vào cây con nặng, sau đó truyền toàn bộ trở lại, sau đó đưa vào cây con nhẹ để dp.
Khi phân tích độ phức tạp tương tự, thấy giống như tính một lần.
### P6326 ★
Đây là bài toán tiêu chuẩn trên, có thể dùng phân chia cây, nhưng không như tính đáp án cho mỗi cây con rồi lấy giá trị lớn nhất, độ phức tạp là O(nm * log n), dễ viết hơn và hằng số nhỏ hơn.
### loj2523 ★
gcd thỏa mãn thì đơn giản nghịch biến.
### loj2719 ★
Mỗi lần đưa phần tử nhỏ nhất về đầu, có thể thấy tương đương với một số x nếu đạt được vị trí của x trước khi xử lý thì chắc chắn không đạt được cận dưới.
Khi phân tích điều kiện này, tương đương một số có số lớn hơn trước đó, số nhỏ hơn sau đó thì không đạt được, do đó chuỗi giảm dài nhất không vượt quá hai.
Đp không giới hạn, xem xét việc làm ngây thơ là ghi nhớ chiều dài chuỗi giảm là 1, lớn nhất là bao nhiêu, chiều dài chuỗi giảm là 2, lớn nhất là bao nhiêu.
Sau đó nhận ra chiều dài là 1 chỉ là giá trị lớn nhất trước đó, chiều dài là 2 chắc chắn phải là phần tử nhỏ nhất chưa được chọn, ngược lại không hợp lệ.
Vì vậy có thể đưa ra một dp O(n^2), đặt một giá trị lớn nhất.
f[i,j] = f[i+1,j] + f[i,j+1]Khi vẽ sơ đồ lưới, thì j<i đều là các trạng thái bị loại bỏ.
Có thể thấy là một thứ tự Catalan, do đó có thể tính các giá trị điểm bằng O(1).
Vấn đề thứ tự từ điển, chỉ cần tìm vị trí đầu tiên lớn hơn.
Độ phức tạp là O(n).