前言

虽然开头带了点赛后总结的感觉，但主要还是在思考大模拟需要注意的细节问题，并且也是在围绕两道题的代码进行精注，所以这次就久违的把这篇文章放到了“程序精注”的分类，而不是“解题日志”或者“赛后复盘”。

在Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 – Elimination Round)比赛时惊险地以错误尝试1次的代价拿下了1782C – Equal Frequencies，这一个关键的topdeck助力，让我勉强挤进了校内新生的前七（上一个礼拜有点划水自己也是有数的），为校内选拔开了个不是那么好的好头。就是不知道为什么Rating卡在了1394，十分甚至九分尴尬（

讲道理C题并不难，就是简单的“削多填少”，然而如果直接以该思路完成题目的话，细节多到令人发指，以至于调了半天，还是因为静态查错的缺乏（耐心爆炸）WA了一发，好在还是及时找出问题后复审并通过了C题。

官方的题解还没出来，在重新回顾难得的小胜时，想起了一道之前悬而未决的一道双指针：1734D – Slime Escape。虽然之前把这道题放在了补题名单里，但其实一直没解决，正好由1782C题有感而发，于是去重·构·代·码！这不去不要紧，一去就又重构了3次代码，前后共计提交了25次至多！（虽然有不少其实是在套数据，）但这一天调试下来，解决问题的同时也深刻地认识到了大模拟中码力的重要性（以至于想给曾经的不知天高地厚自己扇两巴掌）。

1782C – Equal Frequencies

其实这道题在比赛的时候也是重构了两版代码才最终落实出来的（

当时做完前两题，刚看第三题情绪有点蒙，情绪稳定之后开始读题，发现比想像中的简 单，然后开始思考，并得出了不少初始结论（也写在了下方代码的注释中），虽然不准确，但还是给比赛增添了一点点信心。然而这些信息十分地脆弱，按下葫芦浮起瓢……所以一开始的注释其实只能记录一个思考过程。

总结一下写代码的时候出现的没有考虑清楚的细节问题：

1. 【致命】得出削多填少的时候没有考虑到多种情况！一开始只是简单的记录字符出现的次数，然后按照次数削多填少，把比出现次数大的变成其他字母。然而随着思考（码代码）的深入，发现了不少问题：多出来的字符可能会用于填充少掉的部分，也有可能填充一些从来没出现过的字符（情况1）！同时，也有可能不会有多出来的字符，单纯的把少的两两合并（情况2）！
   
   
   
   也就是说，一开始关注的目标就有问题！极大地干扰了求答案公式的计算。
2. 【致命】代码实现没想清楚，重构不可避免！一开始由于(1)，只是简单地认为只要关注多出来的部分并改成缺少的部分就可以了，没想清楚就开干，然后一脸懵逼，只得调转枪口优先关注需要填补的字符，直接导致了代码的一次重构（在代码中加入链表储存每个字符的位置以方便之后修改）。
3. 【警惕】静态查错！anss[val[head[q[l].second]]] = q[i].second + 'a';这个l-i错误是可以避免的，可能会比现在高50分！

namespace lovelive{
    /********************
     * 是否为平衡字符串无关字符串顺序
     * 假如确定一个字符串内所有的字符都出现x次
     * （很明显必须为字符串长度的约数）
     * 这是一个削堕天少的过程
     * 由于字符串最多26个，用堆应该……不会爆吧
     * 将字符出现的次数排序，从最大的往前处理：
     * 1. 大于上限的，加到可选自由文字，先不做处理
     * 2. 等于上限的，直接无视；
     * 3. 小于上限的，要么使用自由文字，要么与前面的配对
     * 如果无法与前面的文字完全匹配又没有自由字呢？
     * 多出来的一定会填到少的里面，所以只要二分
     * 找到等于的上界和下届，然后加起来就好
     * 同时注意份数不能多于26份。
    \********************/

    int cnti[26];
    int n,tmp,ans,anst,l,r;
    string s;
    char anss[100005];
    pair<int,int> q[30];
    pair<int,int> freei[30];
    int sumi[27];
    int head[26],nxt[100005],val[100005],lcnt;
    void main(){
        cin>>n>>s;ans = n;lcnt = 0;
        memset(cnti,0,sizeof(cnti));
        memset(head,0,sizeof(head));
        for(int i=0;i<n;i++){
            anss[i] = s[i];
            cnti[s[i] - 'a'] ++;
            nxt[++lcnt] = head[s[i] - 'a'];
            val[lcnt] = i;
            head[s[i] - 'a'] = lcnt;
        }
        for(int i=0;i<26;i++){
            q[i] = {cnti[i],i};
        }
        sort(q,q+26);
        sumi[0] = 0;
        for(int i=0;i<26;i++){
            sumi[i+1] = sumi[i] + q[i].first;
        }
        for(int tr = max(1,n / 26);tr <= n;tr ++){
            if(n % tr || tr * 26 < n) continue;
            l = upper_bound(q,q+26,make_pair(tr,-1)) - q;
            r = upper_bound(q,q+26,make_pair(tr+1,-1)) - q;
            //tmp = (n - ((n/tr - (26-l)) * tr)) / 2;
            tmp = n - ((26 - l) * tr) - (sumi[l] - sumi[26 - n/tr]);
            if(tmp < ans){
                ans = tmp;
                anst = tr;
            }
        }
        l = 25 - n/anst;
        r = upper_bound(q,q+26,make_pair(anst+1,-1)) - q;
        for(int i = upper_bound(q,q+26,make_pair(anst,-1)) - q - 1;i>25 - n/anst;i--){
            while(cnti[q[i].second] < anst){
                cnti[q[i].second] ++;
                if(r>=26){
                    anss[val[head[q[l].second]]] = q[i].second + 'a';
                    head[q[l].second] = nxt[head[q[l].second]];
                    if(!(head[q[l].second])) l--;
                }else{
                    anss[val[head[q[r].second]]] = q[i].second + 'a';
                    head[q[r].second] = nxt[head[q[r].second]];
                    cnti[q[r].second] --;
                    if(cnti[q[r].second] == anst) r++;
                }
            }
        }
        anss[n] = '\0';
        cout<<ans<<endl<<anss<<endl;
    }
}

1734D – Slime Escape

namespace lovelive{
    typedef long long LL;
    /*
    被以下数据hack了，只能第三次重构代码（
    1
    43 22
    -206 -906 -827 83 -46 -211 -561 -720 -318 -224 231 -82 943 944 922 256 -665 83 -629 -629 83 1545 275 -332 337 -119 -707 -66 253 -184 742 -839 -379 -495 -750 728 -399 -999 572 -640 975 -967 98 
    发现了kotori版本代码的问题，就是处理极其后面的大赚分块的时候会出现“破绽稍纵即逝”的问题
    于是老老实实地研究了官方题解
    */
    #define niconi   (!cheflag || che1 != CHE1 || che2 == CHE2)
    #define lovenico (cheflag && che1 == CHE1 && che2 == CHE2)
    //上面这两行是用来在练习的时候套数据的……对解题本身没有实际影响
    LL n,m,ai[200005];
    LL cnt,nm,tmp,flag;
    LL bi[200005],ci[200005],l,r,ll,rr,worst;
    LL sumi[200005];
    const int CHE1 = 20000;
    const int CHE2 = 9331;
    const int CHEN = 9;
    const int CHEM = 1;
    bool cheflag = false;
    void main(int che1=0,int che2=0){
        //最终屈服于官方的做法
        //官方题解将所有区间和大于0的（以及直接抵达端点的）合并为一个“好的”区间
        //同时记录两个特征值：该段区间内的最少血量（门槛）和该段区间总和
        //在迭代的时候只要尽可能吃好的区间即可
        cin>>n>>m;
        if(che2==1 && n==CHEN && m==CHEM) cheflag = true;
        if(lovenico) cout<<n<<" "<<m<<endl;
        for(int i=1;i<=n;i++){
            cin>>ai[i];
            sumi[i] = sumi[i-1] + ai[i];
            //技巧1：前缀和，可快速判断一个区间内的数之和是否大于0.
            if(lovenico) cout<<ai[i]<<" ";
        }
        if(lovenico) cout<<endl;
        if(ai[m]<0){
            if(niconi) cout<<"NO"<<endl;
            return;
        }
        bi[m] = ai[m];
        l = m-1; r = m+1; ll = rr = m;
        while(l && ai[l]>=0)bi[m] += ai[l],l--; //将一号区间内所有的正数都吃掉
        while(r<=n && ai[r]>=0)bi[m] += ai[r],r++;
        l++; r--;                               //想好！区间范围对于左侧是左闭右开区间
                                                //在确定需要区间求和的时候就要注意到的
        for(int i=l-1; i; i--){                 //首先向左合并
            if(i==1 || sumi[i-1]<=sumi[l-1]){   //技巧1：前缀和，可快速判断一个区间内的数之和是否大于0.
                //找到了一个好的区间
                ll--;bi[ll] = ci[ll] = 0;       //【注意】永远不要忘记重置，因为有多重数据
                for(int j=l-1;j>=i;j--){        //记录特征值
                    bi[ll] += ai[j];            //其实一遍记录不好是可以第二次遍历的
                    ci[ll] = min(ci[ll],bi[ll]);//因为只是常数乘级别的复杂度
                                                //对比赛来说省下了不少脑子
                }
                l = i;                          //记住区间需要变化
                ci[ll] = -ci[ll];               //【注意】需要负负得正！
            }
        }
        for(int i=r+1; i<=n; i++){              //右侧同理
            if(i==n || sumi[i]>=sumi[r]){       //【注意】右侧的前缀和利用与左侧有不同！
                rr++;bi[rr] = ci[rr] = 0;       //【注意】永远不要忘记重置，因为有多重数据
                for(int j=r+1;j<=i;j++){
                    bi[rr] += ai[j];
                    ci[rr] = min(ci[rr],bi[rr]);
                }
                r = i;
                ci[rr] = -ci[rr];
            }
        }

        //debug//for(int i=ll;i<=rr;i++)cout<<bi[i]<<" ";cout<<endl;
        //debug//for(int i=ll;i<=rr;i++)cout<<ci[i]<<" ";cout<<endl;

        bi[ll-1] = bi[rr+1] = 0;
        ci[rr+1] = ci[ll-1] = 0;                //边界值的处理

        l = r = m;                              //flag的指示[2]：当flag入场时，在其上放置两个指示物
        tmp = bi[m];                            //每当一次尝试失败时，移除一个指示物
        flag = 2;                               //当flag上没有指示物的时候，你输掉这盘游戏
        //debug//cout<<l<<"\t"<<r<<"\t"<<tmp<<endl;
        while(ll<l && r<rr){                    //尽可能尝试从左侧逸脱
            if(tmp >= ci[l-1]) tmp += bi[--l];  //左侧不行再去考虑右侧
            else if(tmp >= ci[r+1]) tmp += bi[++r];
            else {flag--;break;}

            //debug//cout<<l<<"\t"<<r<<"\t"<<tmp<<endl;
        }

        l = r = m;                              //右侧同理，注意维持阶段的重置
        tmp = bi[m];
        //debug//cout<<l<<"\t"<<r<<"\t"<<tmp<<endl;
        while(ll<l && r<rr){                    //【注意】边界值的选取：如果当前区间能够取到边界点，那么它一定能逸脱
            if(tmp >= ci[r+1]) tmp += bi[++r];
            else if(tmp >= ci[l-1]) tmp += bi[--l];
            else {flag--;break;}
            //debug//cout<<l<<"\t"<<r<<"\t"<<tmp<<endl;
        }
        if(niconi)if(flag)  cout<<"YES"<<endl;
                    else    cout<<"NO"<<endl;
    }
}

namespace kotori{
    //【由于被重构代码的错误的思考方式，这里仅保留注释】
    //试图保证出生点一定会分到一个非负块里
    //主要是出生点有可能是0，如果不处理可能会分到负块里
    //0的话就和其他的块合并在一期 
    /*
    应该向左向右各做一次的，由于双指针模拟
    没有反悔机会，贪心不能只是简单的挑最大（损失最小）的块捡走
    这样可能会导致生命值低于门槛被卡死
    正确的贪心应该是在努力朝着左方向突破的时候
    除非被门槛卡住以至于只能往右看，否则使劲往左走
    hack数据集：
    2
    16 6
    -920734269 -1 1 -1 -1 4 1 -1 -1 -1 -1 1 -1 1 -1 -1
    16 9
    -920734269 1 1 -1 -1 1 -1 -1 1 1 1 -1 -1 1 -1 -1
    答案都是YES，但用错误的处理会卡注
    */
    //如果不成功就减掉，为0时输掉这盘游戏
    //向左走
    //做不到就艾草
    //向右走，代码大差不差
}