APIO 2014

Cho một xâu chỉ gồm chữ cái Latin thường. Với mỗi xâu con, định nghĩa giá trị xuất hiện là số lần xâu con đó xuất hiện trong xâu ban đầu nhân với độ dài của nó.

Hãy tìm giá trị xuất hiện lớn nhất trong số các xâu con đối xứng.

Một xâu con của \(s=s_1s_2\ldots s_{|s|}\) là xâu không rỗng \(s_is_{i+1}\ldots s_j\) với \(1\le i\le j\le|s|\). Các lần xuất hiện có thể chồng lấn. Xâu đối xứng là xâu đọc từ trái sang phải giống đọc từ phải sang trái.

Dữ liệu vào

Dòng duy nhất chứa một xâu không rỗng gồm các chữ cái từ a đến z.

Dữ liệu ra

In giá trị xuất hiện lớn nhất của một xâu con đối xứng.

Ví dụ

abacaba

7

www

4

Giải thích

Trong ví dụ thứ nhất, các xâu con đối xứng khác nhau là a, b, c, aba, aca, bacab, abacaba. Giá trị xuất hiện tương ứng là \(4,2,1,6,3,5,7\), nên đáp án là \(7\).

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2014, bài Palindromes.

Bạn có một dãy \(n\) số nguyên không âm và cần chia dãy thành \(k+1\) đoạn liên tiếp không rỗng. Ban đầu toàn bộ dãy là một đoạn. Lặp lại đúng \(k\) lần:

1. Chọn một đoạn có nhiều hơn một phần tử.
2. Cắt đoạn đó giữa hai phần tử liên tiếp để tạo thành hai đoạn không rỗng.

Mỗi lần cắt, bạn nhận số điểm bằng tích tổng các phần tử của hai đoạn mới tạo ra. Hãy tối đa hóa tổng điểm qua \(k\) lần cắt.

Dữ liệu vào

• Dòng đầu chứa \(n,k\), với \(k+1\le n\).
• Dòng thứ hai chứa \(n\) số \(a_1,a_2,\ldots,a_n\).

Dữ liệu ra

• Dòng đầu in tổng điểm lớn nhất.
• Dòng thứ hai in \(k\) số nguyên trong đoạn \([1,n-1]\), là các vị trí phần tử mà sau đó cần cắt dãy để đạt tổng điểm lớn nhất.

Nếu có nhiều phương án tối ưu, in bất kỳ phương án nào. Thứ tự các vị trí trên dòng thứ hai không ảnh hưởng đến kết quả cuối cùng, nhưng mỗi vị trí phải khác nhau và phải tạo ra đúng \(k+1\) đoạn không rỗng.

Ràng buộc

• \(0\le a_i\le10^4\).
• \(1\le k<n\le100\,000\).
• Trong các nhóm lớn, \(k\le200\).

Ví dụ

7 3
4 1 3 4 0 2 3

108
1 3 5

Giải thích

• Cắt sau phần tử \(1\), nhận \(4\times(1+3+4+0+2+3)=52\) điểm.
• Cắt đoạn thứ hai sau phần tử \(3\), nhận \((1+3)\times(4+0+2+3)=36\) điểm.
• Cắt đoạn cuối sau phần tử \(5\), nhận \((4+0)\times(2+3)=20\) điểm.

Tổng điểm là \(52+36+20=108\).

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2014, bài Split the Sequence.

Một trò chơi phổ biến thời Leonardo sử dụng các hạt và dây. Dây có màu đỏ hoặc xanh, các hạt được đánh số từ \(1\) đến \(n\). Trò chơi bắt đầu với một hạt duy nhất. Sau đó có thể thêm hạt mới bằng một trong hai thao tác:

• Append(w, v): gắn hạt mới \(w\) vào hạt đã có \(v\) bằng một đoạn dây đỏ.
• Insert(w, u, v): chọn một đoạn dây đỏ đang nối hai hạt \(u,v\), bỏ dây đó và chèn hạt mới \(w\) vào giữa bằng hai đoạn dây xanh \(u-w\) và \(w-v\).

Mỗi đoạn dây có một độ dài. Điểm cuối cùng là tổng độ dài của các dây xanh; dây đỏ không đóng góp điểm.

Bạn được cho cấu hình cuối cùng: các cặp hạt nối nhau và độ dài từng dây, nhưng không biết màu dây. Trong số mọi quá trình chơi hợp lệ có thể tạo ra cấu hình này, hãy tìm điểm cuối cùng lớn nhất.

Dữ liệu vào

• Dòng đầu chứa \(n\).
• \(n-1\) dòng tiếp theo, dòng thứ \(i\) chứa \(a_i,b_i,c_i\), cho biết hạt \(a_i\) và \(b_i\) được nối bởi dây dài \(c_i\).

Cấu hình đã cho là một cây.

Dữ liệu ra

In tổng độ dài dây xanh lớn nhất có thể đạt được.

Ràng buộc

• \(1\le a_i<b_i\le n\).
• \(1\le c_i\le10\,000\).
• \(1\le n\le200\,000\).

Ví dụ

5
1 2 10
1 3 40
1 4 15
1 5 20

60

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

140

Giải thích

Ở ví dụ thứ nhất, bắt đầu với hạt \(3\), nối thêm hạt \(5\) bằng dây đỏ tùy ý, chèn hạt \(1\) vào dây \(3-5\) bằng hai dây xanh dài \(40\) và \(20\), rồi nối thêm hạt \(2\) và \(4\) bằng dây đỏ. Tổng độ dài dây xanh là \(60\) và không thể đạt giá trị lớn hơn.

{{asset:apio14-beads-sample1}}

Cấu hình của ví dụ thứ hai có thể đạt điểm \(140\) như hình sau.

{{asset:apio14-beads-sample2}}

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2014, bài Beads and Wires.