QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234650#4187. Decrypting ZodiacFyind#TL 2ms5808kbC++172.9kb2023-11-01 20:21:182023-11-01 20:21:19

Judging History

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

  • [2023-11-01 20:21:19]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:5808kb
  • [2023-11-01 20:21:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 3e5 + 5;

typedef double ld;
const ld PI = acos((ld)-1);

struct cp {
    ld x, y;
    cp(ld x=0, ld y=0) : x(x),y(y) {}
    cp operator + (const cp &c) const {
        return cp(x+c.x, y+c.y);
    }  
    cp operator - (const cp &c) const {
        return cp(x-c.x, y-c.y);
    }
    cp operator * (const cp &c) const {
        return cp(x*c.x - y*c.y, x*c.y + y*c.x);
    }
    cp conj() const {
        return cp(x, -y);
    }
};


void fft(vector<cp> &a, int len, int op) {
    while (sz(a) < len) a.push_back(cp(0,0));
    vector<int> R(len);
    R[0] = 0;
    for (int i = 1;i < len; ++i) {
        R[i] = (R[i>>1]>>1) + (i&1)*(len>>1);
        if (i < R[i]) swap(a[i], a[R[i]]);
    }
    vector<cp> w(len/2); w[0] = cp(1,0);
    for (int n = 2; n <= len; n <<= 1) {
        cp wt = cp(cos(2*PI*op/n), sin(2*PI*op/n));
        for (int k = 1;k < n/2; ++k) {
            if (k % 2) w[k] = w[k>>1] * w[k>>1] * wt;
            else w[k] = w[k>>1] * w[k>>1];
        }
        for (int i = 0; i < len; i += n) {
            int po = i + (n>>1);
            for (int k = 0; k < n/2; ++k) {
                auto t = a[i+k];
                a[i + k] = t + w[k] * a[po + k];
                a[po + k] = t - w[k] * a[po + k]; 
            }
        }
    }
    if (!~op) 
        for (int i = 0;i < len; ++i) a[i].x /= len;
}

vector<cp> convolution(vector<cp>& a, vector<cp>& b) {
    int len = 1;
    int lans = sz(a) + sz(b) - 1;
    while (len < lans) len <<= 1;
    fft(a, len, 1);
    fft(b, len, 1);
    vector<cp> ret(lans);
    for (int i = 0;i < len; ++i) a[i] = a[i] * b[i];
    fft(a, len, -1);
    for (int i = 0;i < lans; ++i) ret[i] = a[i];
    return ret;
}

int n, m;
int A[maxn], B[maxn], C[maxn];

int solve() {
    vector<int> eq(n*2);
    for (int c = 0;c < 26; ++c) { 
        vector<cp> polya(n), polyc(n*2);
        for (int i = 0;i < n; ++i) polya[i] = {(double)(A[n-i] == c), 0};
        for (int i = 0;i < n*2; ++i) polyc[i] = {(double)(C[i+1] == c), 0};
        auto poly = convolution(polya, polyc);
        for (int i = n-1;i < n*2; ++i) {
            eq[i] += (int)(poly[i].x+0.5);
        }
    }
    return n - *max_element(eq.begin()+n-1, eq.end());
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        char c; cin >> c;
        A[i] = c - 'a';
    } 
    for (int i = 1;i <= n; ++i) {
        char c; cin >> c;
        B[i] = c - 'a';
    }
    int ans = 1e9;
    for (int k = 0;k <= 25; ++k) { 
        for (int i = 1;i <= n; ++i) {
            C[i] = (B[i] + k) % 26;
            C[i + n] = C[i];
        }
        ans = min(ans, solve());
    }
    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5744kb

input:

6
drhmex
zodiac

output:

2

result:

ok single line: '2'

Test #2:

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

input:

8
dicepara
paradise

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 5808kb

input:

13
lvlvdvdqsonwk
thisisasample

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Time Limit Exceeded

input:

150000
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:


result: