首页 > 其他分享 >CF1493C

CF1493C

时间:2023-12-14 15:23:06浏览次数:47  
标签:qt int CF1493C back && ans push

以前写挂了 今天又拿出来写
手玩一下样例发现 我们从高位贪是肯定的
尽可能让该位置和原串一样
然后我们可以枚举该位改成什么字母 然后计算后面的放是否合法
写的很屎 其实就是复制粘贴了一坨
我们先找到 最远的位置可以修改 再修改为最小的即可

void solve(){
    int n,k;cin>>n>>k;
    string s;cin>>s;s='='+s;
    if(n%k){
        cout<<-1<<endl;
        return;
    }
    map<int,int>mp;
    int P;
    for(int i=1;i<=n;i++){
        for(int j=s[i]+1;j<='z';j++){
            mp[j]++;
            int sy=n-i;
            for(auto [pos,w]:mp)sy-=k-w;
            if(sy>=0&&sy%k==0){
//                cout<<i<<' '<<char(j)<<endl;
                P=i;
                mp[j]--;
                if(mp[j]%k==0)mp.erase(j);
                break;
            }
            mp[j]--;
            if(mp[j]%k==0)mp.erase(j);
        }
        mp[s[i]]++;
        if(mp[s[i]]%k==0)mp.erase(s[i]);
    }
    if(mp.size()==0){
        cout<<s.substr(1)<<endl;
        return;
    }
    mp.clear();
    for(int i=1;i<=P;i++){
        for(int j=s[i]+1;j<='z';j++){
            mp[j]++;
            int sy=n-i;
            for(auto [pos,w]:mp)sy-=k-w;
            if(sy>=0&&sy%k==0&&i==P){
                vector<int>qt;
                string ans=s.substr(0,i);
                ans+=j;
                for(auto [pos,w]:mp){
                    int syy=k-w;
                    while(syy--)qt.push_back(pos);
                }
                while(sy--)qt.push_back('a');
                sort(all(qt));
                for(auto now:qt)ans.push_back(now);
                cout<<ans.substr(1)<<endl;
                return;
            }
            mp[j]--;
            if(mp[j]%k==0)mp.erase(j);
        }
        mp[s[i]]++;
        if(mp[s[i]]%k==0)mp.erase(s[i]);
    }
    cout<<P<<endl;
}

标签:qt,int,CF1493C,back,&&,ans,push
From: https://www.cnblogs.com/ycllz/p/17901243.html

相关文章