Title 00 dt25-26 tu 31-3.docx ✅

BÀI TẬP CHO ĐỘI TUYỂN 2025 – 2026 TỪ 31.3 ĐẾN 31.4 Link chấm: https://codeforces.com/contestInvitation/f9f2734146787a99a9d7f2ea4b60c5b2f36d9dc0 1. DP ĐỐI XỨNG Câu 1. NKPALIN Xâu con đối xứng Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu. Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu. Input: Gồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường. Output: Gồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu s. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ. Giới hạn: Chuỗi s có độ dài không vượt quá 2000. Ví dụ: Input Output lmevxeyzl level Giải DOIXUNG https://youtu.be/ZAfcLMTFKWo Gọi f[i][j] là độ dài xâu con đối xứng dài nhất của xâu s[i...j]. Output = f[1][ n]  f[i][j] = f[i+1][j-1] + 2 nếu s[i] = s[j] lmevxeyzl f[3][6]=f[4][5]+2  f[i][ j] = max( f[i+1][j], lmevxeyzl f[i][j-1]) nếu s[i] <> s[j] lmevxeyzl Cơ sở: f[i][i] = 1 Chú ý thứ tự tính bảng f. Ta tính từ hàng (n-1) về hàng 1, cột từ trái qua phải (i+1) đến n. 1 1 x 1 x x 1 1 1 1 1

else k=res.size()-2; for(int i=k;i>=0;i--) cout<<res[i]; } void giai() { for(int i=1;i<=n;i++) f[i][i]=1; for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { if(s[i]==s[j]) f[i][j]=f[i+1][j-1]+2; else f[i][j]=max(f[i+1][j],f[i][j-1]); } } // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++) cout<<f[i][j]<<" "; // cout<<endl; // } truyvet(); } int main () { freopen("nkpalin.inp","r",stdin); freopen("nkpalin.out","w",stdout); cin>>s;n=s.size();s=' '+s; giai(); } Câu 2. PALIN Tạo xâu đối xứng Một xâu được gọi là đối xứng (palindrome) nếu như khi đọc xâu này từ phải sang trái cũng thu được xâu ban đầu. Yêu cầu: cho một xâu S, tìm cách thêm vào xâu S một số ít nhất kí tự để S trở thành xâu đối xứng. Input:  Dòng đầu là số kí tự của xâu.  Dòng sau chứa xâu s, chỉ gồm những chữ cái in thường. Output:  Dòng đầu là số kí tự thêm vào.  Dòng sau là xâu đối xứng tạo thành Giới hạn: Chuỗi s có độ dài không vượt quá 5000. Ví dụ: Input Output 5 abcad 2 dacbcad Giải DOIXUNG ioi2000 https://youtu.be/2P7Uw-vAd-I