题解：P11279 Abstract String Basic

WsW_ · 2024-11-21 12:56:17 · 题解

前言

简单贡献统计题。

周六的时候还在上课，语文课上拿着同学老年机看题并口胡。另外，语文老师是年级主任。

思路

将题目翻译成中文：给一个字符串 S，请求一个字符串 T 使得两个字符串中位置和字母都不同的数量，即满足 i\neq j,S_i\neq T_j 的 (i,j)，最多。
容易发现每个 T_j 互不相关，所以对每个 T_j 分开考虑。

假设已知 T_j 是什么字母，我们考虑如何求出它的贡献 \sum\limits^{n}_{i=1}[i\neq j][S_i\neq T_j]。把式子理解之后转化一下，得 (\sum\limits^{n}_{i=1}[S_i\neq T_j])-[S_j\neq T_j]。
接着想怎样快速求出 \sum\limits^{n}_{i=1}[S_i\neq T_j]。把这个式子转化一下，得 n-\sum\limits^{n}_{i=1}[S_i= T_j]。
预处理一下，开一个桶 cnt 记录 S 中每个字母的数量，就可以 O(1) 求出 \sum\limits^{n}_{i=1}[S_i= T_j]=cnt_{T_j}。
最后我们就可以 O(1) 求出一个已知 T_j 的贡献 n-cnt_{T_j}-[S_j\neq T_j]。

然后对于每一个 T_j，枚举全部的 26 个字母，哪个字母产生的贡献大把 T_j 设成哪个字母。

时间复杂度为 O(|S|n)。其中 |S|=26。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int cnt[30];

int g(char c,int p){//求贡献
    return n-cnt[c-'a']-(s[p]!=c);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>s;
    for(int i=0;i<n;i++)cnt[s[i]-'a']++;//预处理
    for(int i=0;i<n;i++){
        char max_c='z';//随便初始化一个字母，初始化成啥都行
        for(char c='a';c<'z';c++)//枚举放哪个字母
            if(g(c,i)>g(max_c,i))max_c=c;
        cout<<max_c;
    }
    return 0;
}