寒假思维训练day17 C. Equal Frequencies

本文介绍: 不知不觉已经过了差不多一个月了，坚持一件事情还是有点收获的，今天更新一道1600的构造。

不知不觉已经过了差不多一个月了，坚持一件事情还是有点收获的，今天更新一道1600的构造。

寒假训练计划day17

摘要：

Part1 题意

Part2 题解 (有数学推导，latex形式)

Part3 代码 (C++版本，有详细注释)

Part4 我对构造题的归纳总结(自己对构造题的浅薄理解还有例题)

题目链接(有需自取)：Problem – 1781C – Codeforces

Part1 题意

题意:

规定字符串是平衡字符串当且仅当字符串中每个字符的数量相等，给定一个长度为 $n$ 的字符串S，要求找到一个长度为 $n, n leq 1e5$ 的平衡字符串T，使得满足T和S的字符匹配数最多，也就是 $sum_{i = 0}^{n - 1} (S[i] == T[i] ? 1 : 0)$ 最大，输出不匹配的数量和构造出来的T。

Part2 题解

题解：

1、已知 $n,S$ , 设 $res$ 为字符串的匹配数量并赋初值 $0$ 。

2、我们来观察一下平衡字符串有什么性质，因为在平衡字符串中，每个字符的数量都是相等的，假设我们知道每个字符的数量都是 $cnt$ ，显然 $n % cnt = 0, 1 leq n / cnt leq 26$ ，这两个数本质就是 $n$ 的约数。所以我们对 $n$ 分解约数，找到所有满足 $cnt * hve = n, cnt <= 26$ 的数对。

3、假设我们当前考虑 $cnt, hve$ ，我们需要求出当前这样分配最多能匹配几个字符，因为每个字符在原字符串中的数量不同，所以我们预处理一个 $Pair<int, char>$ 序列，他们存的是S中的字符和字符的数量，并且排序，再处理出来一个该序列的前缀和序列，根据这两个序列我们可以开始求最多能匹配几个字符，我们先二分出大于等于 $hve$ 的位置，再进行分了讨论，具体如下：
// u1是cnt, u2是hve, v是匹配数量     
int u1 = c, u2 = n / c;
int l = 1, r = cnt, v; 
if(u1 <= 26) {
    // 先二分
    while(l < r) {
        int mid = l + r >> 1;
        if(q[mid].ff >= u2) 
            r = mid;
        else 
            l = mid + 1;
    }
    // 分类讨论
    v = -1e18;
    if(q[l].ff >= u2) {
        if(cnt - l + 1 >= u1) 
            v = u1 * u2;
        else 
            v = (cnt - l + 1) * u2 + qs[l - 1] - 
            qs[max(0ll,l - 1 - (u1 - (cnt - l + 1)))];
    }
    else {
        v = qs[cnt] - qs[max(0ll,cnt - u1)];
    }
    // 更新res 
    if(res < v) {
        res = v;
        usu1 = u1, usu2 = u2;
    }
}
最后得到了使得匹配数量 $res$ 最大的 $cnt, hve$ 。

4、现在我们需要利用 $cnt,hve$ 逆向构造出T，首先我们对于已经处理出来的 $Pair<int, char>$ 序列（已排序）的后面 $cnt$ 个，注意可以会有不足的情况，我们就得补充回去，具体操作如下：
cout << n - res << endl;  // 输出最后不匹配的最小数量
vector<char> us;   
// 先处理在原字符串中的字符 
for(int i = cnt; i >= max(1ll, cnt - usu1 + 1); i--) {    
    us.push_back(q[i].ss); 
    st[q[i].ss - 'a'] = usu2;      
}

// 先将原字符串的字符有st标记的填入
for(int i = 0; i < n; i++) 
    if(st[s[i] - 'a']) { 
        ans[i] = s[i];
        st[s[i] - 'a']--;
        is_use[i] = 1;
    }

// 将后面的补上
for(int i = max(1ll, cnt - usu1 + 1) - 1; i >= 1; i--)
    us.push_back(q[i].ss), st[q[i].ss - 'a'] = usu2;  

// 如果不够再补上一些没用过的字符
for(int i = 0; i <= 25; i++) 
    if(!ot[i]) us.push_back(i + 'a'), st[i] = usu2;  
    
int l = 0;
// 最后从入序列的顺序补全字符串
for(int i = 0; i < n; i++) { 
    while(!st[us[l] - 'a']) 
        l++; 
    if(!is_use[i]) 
        ans[i] = us[l], st[us[l] - 'a']--;
}

for(int i = 0; i < n; i++) 
    cout << ans[i];
cout << endl;

Part3 代码(C++)：

#include <bits/stdc++.h>
#define int long long 
#define ff first 
#define ss second 
using namespace std;
using PII = pair<int, char>; 
constexpr int N = 1e6 + 10; 
int n, m, sum; 
int ot[50], qs[50], is_use[N], st[50], cnt; 
PII q[50];
void solve() {
    string s; 
    cin >> n >> s; 
    cnt = 0;
    for(int i = 0; i <= 30; i ++ ) ot[i] = 0, st[i] = 0; 
    for(int i = 0; i < n; i ++ ) ot[s[i] - 'a'] ++, is_use[i] = 0;
    for(int i = 0; i <= 30; i ++ ) if(ot[i]) q[++ cnt] = {ot[i], 'a' + i};
    sort(q + 1, q + 1 + cnt);
    
    for(int i = 1; i <= cnt; i ++ ) qs[i] = q[i].ff + qs[i - 1];
    int res = -1e18;
    vector<char> ans(n + 1, 0); 
    int usu1,usu2;
    for(int c = 1; c <= n / c; c ++ ) 
        if(n % c == 0) {
            int u1 = c, u2 = n / c;
            int l = 1, r = cnt, v; 
            if(u1 <= 26) {
                while(l < r) {
                    int mid = l + r >> 1;
                    if(q[mid].ff >= u2) r = mid;
                    else l = mid + 1;
                }
                v = -1e18;
                if(q[l].ff >= u2) {
                    if(cnt - l + 1 >= u1) v = u1 * u2;
                    else v = (cnt - l + 1) * u2 + qs[l - 1] - qs[max(0ll,l - 1 - (u1 - (cnt - l + 1)))];
                }
                else {
                    v = qs[cnt] - qs[max(0ll,cnt - u1)];
                }
                if(res < v) {
                    res = v;
                    usu1 = u1, usu2 = u2;
                }
            }
            u1 = n / c, u2 = c;
            if(u1 <= 26) {
                l = 1, r = cnt;
                while(l < r) {
                    int mid = l + r >> 1;
                    if(q[mid].ff >= u2) r = mid;
                    else l = mid + 1;
                }
                v = -1e18;
                if(q[l].ff >= u2) {
                    if(cnt - l + 1 >= u1) v = u1 * u2;
                    else v = (cnt - l + 1) * u2 + qs[l - 1] - qs[max(0ll,l - 1 - (u1 - (cnt - l + 1)))];
                }
                else {
                    v = qs[cnt] - qs[max(0ll,cnt - u1)];
                }
                if(res < v) {
                    res = v;
                    usu1 = u1, usu2 = u2;
                }
            }
            
        }
        cout << n - res << endl; 
        vector<char> us;
        for(int i = cnt; i >= max(1ll, cnt - usu1 + 1); i -- ) {
            us.push_back(q[i].ss), st[q[i].ss - 'a'] = usu2;  
            // cout << q[i].ss << endl;
        }

        for(int i = 0; i < n; i ++ ) 
            if(st[s[i] - 'a']) { 
                // cout << s[i] << endl;
                ans[i] = s[i], st[s[i] - 'a'] --, is_use[i] = 1;
                // cout << ans[i] <<  "#";
            }
            
        for(int i = max(1ll, cnt - usu1 + 1) - 1; i >= 1; i -- )
            us.push_back(q[i].ss), st[q[i].ss - 'a'] = usu2;  
        
        for(int i = 0; i <= 25; i ++ ) if(!ot[i]) us.push_back(i + 'a'), st[i] = usu2;  
        
        int l = 0;

        for(int i = 0; i < n; i ++ ) { 
            while(!st[us[l] - 'a']) l ++; 
            if(!is_use[i]) ans[i] = us[l], st[us[l] - 'a'] --;
        }
        
        
        for(int i = 0; i < n; i ++ ) cout << ans[i];
        cout << endl;
}   
signed main() {

    int ts; 
    cin >> ts; 
    while(ts --) 
        solve(); 
    
    return 0; 
}