QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54839#4187. Decrypting ZodiacSa3tElSefrTL 8ms3596kbC++2.5kb2022-10-10 20:04:412022-10-10 20:04:57

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-10 20:04:57]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:3596kb
  • [2022-10-10 20:04:41]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;

const int N = 2e5 + 5, mod = 998244353;

using cd = complex<ld>;
const ld PI = acos(-1);

void fft(vector<complex<ld>> &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){
        ld ang = 2 * PI / len;
        if(invert) ang *= -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(auto &i: a) i /= n;
    }

}

vector<int> multiply(vector<int> &a, vector<int> &b){
    vector<complex<ld> > 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, 0);
    fft(fb, 0);

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

    fft(fa, 1);
    vector<int> res(n);
    for(int i = 0; i < n; i++){
        res[i] = (int) round(fa[i].real());
    }
    return res;
}

vector<vector<int> > a(26), b(26);

vector<int> get(string &s, char c) {
    int n = s.size();
    vector<int> ret(n, 0);
    for(int i = 0; i < n; i++) {
        if(s[i] == c) {
            ret[i] = 1;
        }
    }
    return ret;
}

vector<int> res[26];

int n;

int solve(int shift) {
    for(int i = 0, j = shift; i < 26; i++, j++) {
        if(j == 26) j = 0;
        res[i] = multiply(a[i], b[j]);
    }

    int ans = n;
    for(int i = n - 1; i < n - 1 + n; i++) {
        int kam = 0;
        for(int k = 0; k < 26; k++) {
            kam += res[k][i];
        }
        ans = min(ans, n - kam);
    }
    return ans;

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s, t;
    cin >> n >> s >> t;
    s += s;
    reverse(t.begin(), t.end());


    for(char c = 'a'; c <= 'z'; c++) {
        a[c - 'a'] = get(s, c);
        b[c - 'a'] = get(t, c);
    }

    int ans = n;
    for(int i = 0; i < 26; i++) {
        ans = min(ans, solve(i));
    }

    cout << ans;




    return 0;
}





詳細信息

Test #1:

score: 100
Accepted
time: 5ms
memory: 3584kb

input:

6
drhmex
zodiac

output:

2

result:

ok single line: '2'

Test #2:

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

input:

8
dicepara
paradise

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 8ms
memory: 3596kb

input:

13
lvlvdvdqsonwk
thisisasample

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Time Limit Exceeded

input:

150000
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:


result: