题解：P10810 【MX-S2-T1】变

Sirkey · 2024-07-27 19:14:24 · 题解

挺好一题。

一个解是否满足有俩个条件。

• 首先得和字符长度满足倍数关系。
• 其次，我们枚举每个循环节的第 j 个变换成什么，所有的字符都是小写字母，所以完全可以。

我们直接二分的话可能会因为第一个条件影响，这样单调性就没了。

所以把所有的满足倍数关系的数搞出来，这样的数量不会太多，时间复杂度根号就可以筛出来。

再对所有数进行二分，就可以了。

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define debug(x) cout<<#x<<":"<<x,puts("");
#define FOR(i,a,b) for(ll i=(a); i<=(b); ++i)
#define ROF(i,a,b) for(ll i=(a); i>=(b); --i)
//
//
//
using namespace std;
inline ll read() {
    ll f = 0, t = 0;
    char c = getchar();
    while (!isdigit(c)) t |= (c == '-'), c = getchar();
    while (isdigit(c)) f = (f << 3) + (f << 1) + c - 48, c = getchar();
    return t ? -f : f;
}
int k,len;
string s;
const int inf = 1e18 + 10; 
bool check(int x){
            if(len % x != 0) return 0;
            int S = 0;
            FOR(i,1,x){             
                    int mi = inf;
                    FOR(k,1,26){
                        int sum = 0;
                        FOR(j,0, len/x - 1)
                            if(((int)s[j * x + i] -'a' + 1) != k)
                                sum += 1;

                        mi=min(sum,mi);
                    }       
                    S+=mi;
            }
            if(S<=k) return 1;
            return 0;
}
int h[1000006];
int top;
void make(int x){
    int walk = 1;
    while(x){
        if(walk*walk>x) {
            h[++top] = x;
            return;
        }
        if(x % walk == 0) h[++top] = walk,h[++top]=x/walk;
        walk++; 
    }
}
signed main() {
//  ios::sync_with_stdio(0), cout.tie(0);
    k = read();
    cin>>s;
    len = s.size();
    s= ' ' +s;
    make(len);
    sort(h+1,h+top+1);
//  FOR(i,1,top) if(check(h[i])) return cout<<h[i],0; 
    int l = 1,r=top;
    int ans =0;
    while(l<=r){
        int mid = (l+r)/2;
        if(check(h[mid])) ans = h[mid],r=mid-1;
        else l = mid+1;
    }
    cout<<ans;
    return 0;
}

——end——