Dãy con đối xứng dài nhất - LCOJ: Luyen Code Online

MANGDX - Dãy con đối xứng dài nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 0.1s

Giới hạn bộ nhớ: 256M

Tác giả:

aprocoder

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Cho n số nguyên ~ a_i ~ . Hãy lập trình tìm ra số lượng dãy con đối xứng dài nhất

Input

Dòng 1 là số nguyên n (~ 1 \le n \le 10^3 ~),

Dòng 2 là n số nguyên ~ a_i ~ (~ | a_i | \le 10^4 ~).

Output

Là độ dài dãy con đối xứng dài nhất .

Sample

Input #1

8
1 2 3 3 2 1 5 7

Output #1

Bình luận

Hãy đọc nội quy trước khi bình luận.

c++ full AC

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n+1];
    a[0] = 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    bool L[n+1][n+1];
    int ans = 1;
    memset(L,false,sizeof(L));
    for (int i = 1; i <=n; i++) {
        L[i][i] = true;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            if (len == 2 && a[i] == a[j])
                L[i][j] = true;
            else
                L[i][j] = L[i + 1][j - 1] && (a[i] == a[j]);
            if (L[i][j]) ans = max(ans,len);
        }
    }
    cout << ans;
}

include <bits/stdc++.h>

using namespace std;

void inout();

int manacher(const vector <int>& a);

int main()

{

    inout();         

    int n; cin>>n;

    vector <int> a(n);

    for (auto &i:a) cin>>i;

    cout<< manacher(a);

    return 0;

}

void inout()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);      

}

int manacher(const vector <int>& a)

{

    vector <int> c;

    c.push_back(1e4+3);         

    for (auto i:a) 

        c.push_back(1e4+1),

        c.push_back(i);

    c.push_back(1e4+1);

    c.push_back(1e4+7);

    int

        n=c.size(),mir=0, 

        cen=0,lmax=0,r=0;

    vector <int> p(n);

    for (int i=1; i&lt;n-1; ++i)

        {

            mir=2*cen-i;

            if (i < r) p[i]=min(p[mir],r-i);

            while (c[i-(1+p[i])]==c[i+(1+p[i])])

                ++p[i];

            if (i+p[i]>r)

                cen=i,r=i+p[i];

            if (p[i]>lmax) lmax=p[i];      

        }

     return lmax;

}

0

danghuuthuan đã bình luận lúc 31, Tháng 3, 2024, 9:49

include<bits/stdc++.h>

using namespace std; int a[10007], dem=0,n; bool dx(int n, int m) { int d; d=(m-n+1)/2; for(int i=0;i<=d;i++) { if(a[n+i]!=a[m-i]) return false; } return true; } int main(){

int n; cin>>n; for(int i=1 ;i<=n;i++) cin>>a[i]; for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) { if(dx(i,j)&&((j-i+1)>dem)) dem=j-i+1; } cout<<dem; return 0; }

0

top1sever đã bình luận lúc 4, Tháng 3, 2024, 10:25

include<bits/stdc++.h>

define ll long long

using namespace std; ll n,a[100006]; ll f[100006],b[100006],vt,l,r,kq=0; int main() { //freopen("1.inp","r",stdin); //freopen("1.out","w",stdout); iosbase::syncwith_stdio(false); cin.tie();cout.tie(); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { l=i,r=i; while(l>0 && r<=n) { if(a[l]==a[r]){kq=max(kq,r-l+1);l--;r++;} else break; } l=i;r=i+1; while(l>0 && r<=n) { if(a[l]==a[r]){kq=max(kq,r-l+1);l--;r++;} else break; } } cout<<kq; return 0; }