QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#54839 | #4187. Decrypting Zodiac | Sa3tElSefr | TL | 8ms | 3596kb | C++ | 2.5kb | 2022-10-10 20:04:41 | 2022-10-10 20:04:57 |
Judging History
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...