QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431267#4187. Decrypting Zodiackevinyang#TL 2ms3980kbC++142.6kb2024-06-05 08:36:372024-06-05 08:36:37

Judging History

你现在查看的是最新测评结果

  • [2024-06-05 08:36:37]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3980kb
  • [2024-06-05 08:36:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using cd = complex<double>;
const double PI = acos(-1);
void fft(vector<cd> & a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
}

template<typename T>
vector<T> multiply(vector<T> const& a, vector<T> const& b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) 
        n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++)
        fa[i] *= fb[i];
    fft(fa, true);

    vector<T> result(n);
    for (int i = 0; i < n; i++)
        result[i] = round(fa[i].real());
    return result;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    string s,t;
    cin >> s >> t;
    vector<int>a(n);
    vector<int>b(n);
    for(int i = 0; i<n; i++){
        a[i] = s[i]-'a';
        b[i] = t[i]-'a';
    }
    vector<vector<int>>idx(26);
    vector<vector<int>>idx2(26);
    for(int i = 0; i<n; i++){
        idx[a[i]].push_back(i);
        idx2[b[i]].push_back(i);
    }
    int ans = 0;
    for(int dx = 0; dx<26; dx++){
        vector<int>dp(n);
        vector<int>ar(n+1);
        vector<int>br(n+1);
        for(int x = 0; x<26; x++){
            
            for(int i: idx[x]){
                ar[i] = 1;
            }
            for(int i: idx2[(x+dx)%26]){
                br[n-i] = 1;
            }
            vector<int>c = multiply(ar,br);
            for(int i = 0; i<c.size(); i++){
                dp[i%n]+=c[i];
            }
            for(int i: idx[x]){
                ar[i] = 0;
            }
            for(int i: idx2[(x+dx)%26]){
                br[n-i] = 0;
            }
        }
        for(int i = 0; i<n; i++){
            ans = max(ans,dp[i]);
        }
    }
    cout << n-ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3700kb

input:

6
drhmex
zodiac

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3720kb

input:

8
dicepara
paradise

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3980kb

input:

13
lvlvdvdqsonwk
thisisasample

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Time Limit Exceeded

input:

150000
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:


result: