QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426893#4187. Decrypting Zodiacrania__#TL 1ms3880kbC++202.1kb2024-06-01 00:01:392024-06-01 00:01:39

Judging History

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

  • [2024-06-01 00:01:39]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3880kb
  • [2024-06-01 00:01:39]
  • 提交

answer

#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5+7, P1 = 31, P2 = 37, mod= 1e9 + 7;

int mul(int a, int b) {
    return (1LL * a * b) % mod;
}

int add(int a, int b) {
    a = (a + mod) % mod;
    b = (b + mod) % mod;
    return (a + b) % mod;
}

int fp(int b, int p) {
    if (b == 1 or p == 0)
        return 1;

    int ret = fp(b, p >> 1);
    ret = mul(ret, ret);

    if (p & 1)
        ret = mul(ret, b);

    return ret;
}

ll modInv(ll n) {
    return fp(n, mod - 2);
}

ll fact[N], inv[N];

void pre() {
    fact[0] = inv[0] = 1;
    for (ll i = 1; i < N; i++)
        fact[i] = (fact[i - 1] * i) % mod, inv[i] = fp(fact[i], mod - 2);
}

ll nCr(ll n, ll r) {
    return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}

ll nPr(ll n, ll r) {
    return ((fact[n] * inv[n - r])) % mod;
}

void doWork() {
   int n;
   cin >> n;
   string a,b;
   cin >> a >> b;
   a+=a;
   int ans = n*2;
    for (int i = 0; i < n; ++i) {
        map<int,int> mp;
        for (int j = 0; j < n; ++j) {
            int k;
            if ( a[i+j] > b[j])
                k = a[i+j] - b[j];
            else
            {
                k = 26 - (b[j] - 'a') + (a[i+j] - 'a');
            }
            mp[k]++;
        }
        int sum =0,mx = 0;
        for( auto &it : mp)
        {
            sum +=it.second;
            mx = max( mx , it.second);
        }
        sum -= mx;
        ans = min(ans , sum);
    }
    cout << ans << endl;
}


int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
//    freopen("bisector.in","r",stdin);
//    freopen("bisector.out","w",stdout);
    int t = 1;
    // cout << primes.size() << endl;
   // cin >> t;
    while (t--) {
        doWork();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3572kb

input:

6
drhmex
zodiac

output:

2

result:

ok single line: '2'

Test #2:

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

input:

8
dicepara
paradise

output:

1

result:

ok single line: '1'

Test #3:

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

input:

13
lvlvdvdqsonwk
thisisasample

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Time Limit Exceeded

input:

150000
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:


result: