QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54871#4187. Decrypting ZodiacT3alaadl3k2olyehymn3kAC ✓7147ms507888kbC++2.7kb2022-10-11 01:13:462022-10-11 01:13:46

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-11 01:13:46]
  • 评测
  • 测评结果:AC
  • 用时:7147ms
  • 内存:507888kb
  • [2022-10-11 01:13:46]
  • 提交

answer

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 5;
using cd = complex<double>;
const double PI = acos(-1);
 
int reverse(int num, int lg_n) {
    int res = 0;
    for (int i = 0; i < lg_n; i++) {
        if (num & (1 << i))
            res |= 1 << (lg_n - 1 - i);
    }
    return res;
}
 
void fft(vector<cd> & a, bool invert) {
    int n = a.size();
    int lg_n = 0;
    while ((1 << lg_n) < n)
        lg_n++;
 
    for (int i = 0; i < n; i++) {
        if (i < reverse(i, lg_n))
            swap(a[i], a[reverse(i, lg_n)]);
    }
 
    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;
    }
}
vector<cd> mul(vector<cd> a, vector<cd> &b) {
	int n = a.size();
	for (int i = 0; i < n; i++)
        a[i] *= b[i];
    return a;
}
vector<cd> add(vector<cd> a, vector<cd> b) {
	int n = a.size();
	for(int i = 0;i < n;i++)
		a[i] += b[i];
    return a;
}
int n;
string s, t;
vector<int> a[26], b[26];
vector<cd> fa[26], fb[26];
vector<int> get(string s, char c) {
	int n = s.size();
	vector<int> ret(n, 0);
	for(int i = 0;i < n;i++)
		ret[i] = (s[i] == c);
	return ret;
}
int solve(int shift) {
	vector<cd> res;
	for(int i = 0, j = shift;i < 26;i++, j = (j + 1) % 26) {
		if(i == 0)
			res = mul(fa[i], fb[j]);
		else
			res = add(res, mul(fa[i], fb[j]));
	}
	fft(res, 1);
	vector<int> ret;
	for(int i = 0;i < res.size();i++)
		ret.push_back(round(res[i].real()));
	int mx = 0;	
	for(int i = 0;i < ret.size();i++)
		mx = max(mx, ret[i]);
	return mx;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> s >> t;
    s += s;
    reverse(t.begin(), t.end());
    for(int i = 0;i < 26;i++) {
		a[i] = get(s, i + 'a');
		b[i] = get(t, i + 'a');
	}
	int x = 1;
	while(x < a[0].size() + b[0].size())
		x <<= 1;
	for(int i = 0;i < 26;i++) {
		fa[i] = vector<cd>(a[i].begin(), a[i].end());
		fb[i] = vector<cd>(b[i].begin(), b[i].end());
		fa[i].resize(x);
		fb[i].resize(x);
		fft(fa[i], 0);
		fft(fb[i], 0);
	}
	int mx = 0;
	for(int i = 0;i < 26;i++)
		mx = max(mx, solve(i));
	cout << n - mx << '\n';
    return 0;
}

详细

Test #1:

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

input:

6
drhmex
zodiac

output:

2

result:

ok single line: '2'

Test #2:

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

input:

8
dicepara
paradise

output:

1

result:

ok single line: '1'

Test #3:

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

input:

13
lvlvdvdqsonwk
thisisasample

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 6783ms
memory: 507772kb

input:

150000
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

144230

result:

ok single line: '144230'

Test #5:

score: 0
Accepted
time: 6754ms
memory: 507888kb

input:

150000
cccccccccccccmtccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccmfcrcccccccucccccccccccucccccccccyccoccccccccccccacccccbccccccccccccccccccccnccccccccccccccccccccclcccccccccccccccccccccckcccccccccccccccpcccccccccccccccccccccccbcccccqcccccccqccccccnycccceksckccccccccocccccccccccccc...

output:

144104

result:

ok single line: '144104'

Test #6:

score: 0
Accepted
time: 6845ms
memory: 507748kb

input:

150000
cccccccccccccctccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccckcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

144188

result:

ok single line: '144188'

Test #7:

score: 0
Accepted
time: 6800ms
memory: 507772kb

input:

150000
mlskccoxctpexrrfygtjtckjutzjaictbppyuovjxmgqdsxliigkbtdwuujwvbxcmmrahkynldbzdrhoanxhutnowdtrxjnenxplkrvzmvepxxnqoocplxcsidexplfcxzceufqfmghnkheurcllsnemhezbfqwmybtwqzjcxbbkarxeksjpnybqsomqfvpthtmrxvvhudntwobvhaklxmrqztpgfookwjdiypuljrpaduxbcoetirlejsbrknpojgtpusveqhegiuldicojiouondcjuehkbimsr...

output:

144230

result:

ok single line: '144230'

Test #8:

score: 0
Accepted
time: 6822ms
memory: 507884kb

input:

150000
kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...

output:

144090

result:

ok single line: '144090'

Test #9:

score: 0
Accepted
time: 6880ms
memory: 507716kb

input:

150000
kstbnrifsftqcvylmcfdxdmhtcjwauffntzfngdkztotkdasmxxrbicyfwdedwvkitqafpgemzuwvdypuoxtjnxdtzbmrrxpwtfxofrlxznfwhvwbwmgnqjmskuouimivuptfllnagthwbpjyrqbyrlagkhfqtseudnsojuxbauugljbaejyqqebggfwzjmkbmjogjmaoyrwvlbfccbhqksebvcfiuflnuuyxpoblmqbqdymcnqjjcitsynoqsuziolbutginragxhepqzkheqvfueumttctqoxkp...

output:

144187

result:

ok single line: '144187'

Test #10:

score: 0
Accepted
time: 6829ms
memory: 507752kb

input:

150000
nznanssdgutbwweyrmqhsotgvpcmajgeadjfexuzplxsivkozqowgigmoqdcwxmghhxyvszawdfclouotbxgfbzlpkaqoaibnynprylvcmsiuednvvktkejdxumuzgbgjlbtihkngtfeylpaqjvpefwthivnyzcvdhbgpachfwedzoftelhqhxuoekikmwuvvsfddirosgexgavdvgmroyrymssksjlefclhukwydtlkxtocgmkaajstnrisujibvzryeveimcqjniivemqnsmrdpwgvecmyazttd...

output:

143804

result:

ok single line: '143804'

Test #11:

score: 0
Accepted
time: 6873ms
memory: 507696kb

input:

150000
bhftmhqtqmltcxnygxqkozrwaqxuxczsiwrlcvsrbhzepxeggxlypsrabjessnegslpshvoaisjhranqqbhbeyebgfyozkchylzblleblohrjtfwrzbolmrkznqvkjnvclxdbeekzcbkewywjcdaubuuclsmxcslyzjiqagvrhqcktoadebtvyutdcawpfryybymlhcyxvbueumjaaclysshpttutcdfltsbzrbdcskomliuboedgdhnknrewztlbscoxnvzpdshqiaawnmenhkbbjmdgpupoqhgo...

output:

143849

result:

ok single line: '143849'

Test #12:

score: 0
Accepted
time: 6845ms
memory: 507836kb

input:

150000
fpagchsakklabymmpmyrsluqaqlupcshghcsnxkczhzhfzoztumdxgfubgpejktldbosntfuvraojcrvhwaasesmytilkwxecqewxzpitjowvrbdbdcahyigvonvqzasixpazorauoohlekwedequqhtuixyepiqnjotjhxdryyhwafsfcpidwzzplbfjdlutbmxlojjfaoeuqxgtitwcpzinbxacumzezlpjotuzvaymdjocnsfkzohmgosbnbhrbcxkzogplntxwweoshuuroeonqhhxbkpdqkh...

output:

143837

result:

ok single line: '143837'

Test #13:

score: 0
Accepted
time: 7147ms
memory: 507752kb

input:

150000
gjodcowfpbskvjhwilokpquumtimojricrslxqibrlesfbvlzyzidfscqtunhcmcbilztxsktwkcwfashgqbfesfbjwbtkykbfjyfbcxtvbftmyideiigieuhwhfoywkexdjlttpdskgarwujsasnbpgbegewrzqenohsxxicuxexnvxitfejocqscxyaqaczzarplydezbolwnunueyeygbfltdatzusyieotlexeqmlqexqmkrzxkbuiexstdemftnjqykqmdmxnozakbuvwhrjlnhgyjhixodd...

output:

143811

result:

ok single line: '143811'

Test #14:

score: 0
Accepted
time: 6945ms
memory: 507748kb

input:

150000
koyqowexlfpmfayhxjgnjysiwjlmhxtvymxwuglrckdwjwbnrnhsfqhgsrodzmzrvpgboqaimsssofirxfzrcnqcwbjmzcrqredlkfdbfwqtmkjqkamtjkdtlhhvsdldpapeqyyaueosatvoptdsxxojxenjlfivtjpofziaxajrarlptfwxekujrlqzvblimmzvndhctolswmygpcdkizuggfeuqblufxptosakasoseecrfspxxmxhlvfscslhruafsgpirpikhfhoxbclgnbuxeqpfhekqupov...

output:

143871

result:

ok single line: '143871'

Test #15:

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

input:

6
dabccd
dddcaa

output:

4

result:

ok single line: '4'

Test #16:

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

input:

5
aaabb
aabbb

output:

1

result:

ok single line: '1'

Test #17:

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

input:

9
aaaaabbbb
aaaabbbba

output:

0

result:

ok single line: '0'

Test #18:

score: 0
Accepted
time: 3ms
memory: 4088kb

input:

26
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxy

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 3ms
memory: 4016kb

input:

27
abcdefghijklmnopqrstuvwxyzz
zabcdefghijklmnopqrstuvwxyy

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 3ms
memory: 4148kb

input:

27
abcdefghijklmnopqrstuvwxyzz
zabcdefghijklmnopqrstuvwxyz

output:

0

result:

ok single line: '0'

Test #21:

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

input:

6
dabcbc
dccbdb

output:

4

result:

ok single line: '4'

Test #22:

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

input:

4
ahfa
ddgc

output:

2

result:

ok single line: '2'

Test #23:

score: 0
Accepted
time: 19ms
memory: 5868kb

input:

630
wkwyxtwpzwrjyvejrfpkucfycvypdlbvmkdjmqtekyyjgpqbipesqsgwjylhzzmqnempgwnqdrulvwdzgqvazopkwokqatoympmqwryctalziacdrkuaouwpnyrogvslrvkwtyldxatuvavtwzghlcjdrmvkocbnlzmpctcjqzcgieeevankgwpltjizarhvusncppcnizrgknhqigjgvafkdlfbnifzgwsnpiuaroejqbtortuitqzkwdusgeetqdxoxdiojqcejqrocmlyirbggfotvujllgfjlhgs...

output:

572

result:

ok single line: '572'

Test #24:

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

input:

511
ifiiieiihihihiigfghhhifiigghhiiiihifiihhiiiiihehihiieiieiighhigigighihhiiedhihidgiiiiiighgigiiiighghgiicihhhhiiihiihfggihiiihhheigighhifihiighihhfiiihgiigiiiihifhiiigiihhgiigiificiihibifgghhhihgihhifiihfhidghiiihihihhhihiiiihihihfhiihiieiigihhhghahhiiigiihgiihhihfdhheigihhifhhghfiiiihifiihiiiiii...

output:

342

result:

ok single line: '342'

Test #25:

score: 0
Accepted
time: 14ms
memory: 5880kb

input:

630
lhgyfhveuevynekxrpdznfjptsajghiqzsonmxktelvxbmfzwkdxsuzaoavxivezsryqnbfhslsrsroplapvvoazujudfatzoijkelxdprhkktlfzwoohzqszjmmrfyofcqahavmluplqoocffxesjmduxgnmdevhhuksfkoompcaagujirfscajkbenarpidfzoproxbgkmvnvsqlixxtmhxtujoixjjonfiojriyrdqbeewcblvnahqxlolacawirgwzpryrbwpecwhxtwbsxnxzpedylwnzsthjsz...

output:

588

result:

ok single line: '588'

Test #26:

score: 0
Accepted
time: 18ms
memory: 5760kb

input:

511
hiighiigiiihfgiifighiiiigfiihfiihiiggihiiihihiiiighihghiiihciieihihgiiifiihgihihihiifihhiiiiihigiihiihhhgeiigfiigiihiiiiighihiehhifihihcihggiihhehhghididhiiiciifiihhieiihiiihhchhhhihhihhhbighiiiiighhiiihhdiggihiiieiiihgihigiegehiihiifhhiigigiiifiihiihiihfieghhiggigiighhhifidiigieiihiiifafgiiihig...

output:

364

result:

ok single line: '364'

Test #27:

score: 0
Accepted
time: 15ms
memory: 5632kb

input:

511
hhiiiiigiidiiihidihiihhehhigdihgiighiifiigiiifihiigfiighigiiiiihiiiheegihiiiggiiiiiiihghhiicigggigihihfhihgghgfiiigfhihihiifgiehfiihghehfhhhigihhhihfiggifihhiiihhgihihgighgihhhihhighiiiihfiigiifhhigiihigiihahieehhiihhifiihiifhfhhihhhiihhiiifhiihiiiiihhgigfihiheigfigiihiihifhihiiiiiihhhihhhiiihgi...

output:

476

result:

ok single line: '476'

Test #28:

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

input:

4
aabb
abba

output:

0

result:

ok single line: '0'