竞赛讨论区 > C题数据出大锅
头像
xzx_123
发布于 02-08 14:50
+ 关注

C题数据出大锅

C题数据也太水了吧 直接匹配完前后缀 不用看是否为回文串也能过啊? 而且赛时就是这样过的

补题代码 20ms 就水过去了

#include<bits/stdc++.h>

#define endl '\n'
#define GG() void(cout<<"-1\n")
#define YES() void(cout << "YES\n")
#define NO() void(cout << "NO\n")
#define debug(x) void (cout<<x<<"\n")
#define dbug(x,y); cout<<x<<' '<<y<<endl;
#define  fi first
#define  se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, N = 2e5 + 10, mod1 = 1e9+7,mod2=954169327;
const LL inf = 1e9+10;
const int M = 2 * N;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int n,m;
int a[N];
LL P[N],ha[2][N];
LL qr(int id,int l,int r,int MOD) {
    return (ha[id][r]-ha[id][l-1]*P[r-l+1]%MOD+MOD)%MOD;
}
void solve() {
    srand(time(0));
    int MOD = 998244353 + rand() % 10007;
    int BASE = 33 + rand() % 233;
    P[0]=1;
    string s1,s2;
    cin>>n>>m;
    cin>>s1>>s2;
    for (int i = 1; i <= N-10; i++) P[i] = P[i - 1] * BASE % MOD;
    for (int i = 1; i <=n; i++) {
        ha[0][i] = (ha[0][i-1] * BASE + s1[i-1]-'a'+1) % MOD;
        //cout<<ha[0][i]<<endl;
    }
    for(int i = 1;i<=m;i++)
    {
        ha[1][i] = (ha[1][i-1]*BASE + s2[i-1]-'a'+1)%MOD;
    }
    vector<LL>mx(m+4);
    for(int i =1;i<=m;i++)
    {
        mx[i]=mx[i-1];
        if(n-i+1<1) continue;
        if(qr(1,1,i,MOD)==qr(0,n-i+1,n,MOD)) mx[i]=i;
        //cout<<qr(1,1,i,MOD)<<' '<<qr(0,n-i+1,n,MOD);
        //cout<<' '<<i<<' '<<mx[i]<<endl;

    }
    LL res=-1;
    for(int i =1;i<=n;i++)
    {
        if(m-i+1<1) break;
        if(qr(0,1,i,MOD)==qr(1,m-i+1,m,MOD))
        {
            if(mx[min(m-i,n-i)]!=0)
            {
                res=max(res,((LL)i+mx[min(m-i,n-i)])*2ll);
               // cout<<i<<' '<<m-i<<' '<<n-i<<' '<<mx[min(m-i,n-i)]<<endl;
            }
        }
    }
    cout<<res<<endl;


}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int xzx_123 = 1;
     //cin >> xzx_123;
    while (xzx_123--) solve();
    return 0;
}

hack数据 答案是-1 跑出来是8 这能过就离谱

5
5
abcde
cdeba

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐