P8719 [蓝桥杯 2020 省 AB2] 字串排序题解

这篇具有很好参考价值的文章主要介绍了P8719 [蓝桥杯 2020 省 AB2] 字串排序题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

根据题目意思,我们构造的字符串需要满足冒泡排序交换次数为 V V V 次,越短越好的情况下输出字典序最小的那一个。于是我们先从字符串的长度开始考虑。

  1. 如何求字符串的最短长度是多少

设字符串长度为 l e n len len, 若该长度的字符串能构造出的最大交换数 ≥ V \geq V V,就代表该长度的字符串一定能恰好构造出交换数为 V V V 的。于是我们首先要求的是长度为 i i i 的字符串能构造出的的最大交换数 f i f_i fi 是多少。

在求最大交换数之前,我们需要知道冒泡排序的一个性质:最大交换数 = = = 逆序对的个数(下文中就用逆序对数代替最大交换数),长度 l e n ≤ 26 len \leq 26 len26 的字符串的最大构造方法显然是前 l e n len len 个字符按逆序排列,这样逆序对的个数就是 f l e n = l e n ∗ ( l e n − 1 ) / 2 f_{len} = len * (len - 1) / 2 flen=len(len1)/2,这样构造的最大交换数在 l e n = 26 len = 26 len=26 时取得 f 26 = 325 f_{26} = 325 f26=325
当要求的逆序对数 ≥ 325 \geq 325 325 时怎么办呢?我们考虑字符串的长度每增加一个字符相当于在任意位置插入一个字符,那么最多能得到的新增逆序对数为:原字符串中与新增字符不同的字符个数。

例如: c b b a a cbbaa cbbaa 新增一个字符,显然是插入一个 c c c 在原来的 c c c 周围最优。 我们可以得出结论:字符串中所有字符数量越接近越好,在字符数 ≥ 26 \geq 26 26 以后就又是以 a b c abc abc 的顺序开始新增(满足字典序小),每次插入新字符增加的逆序对即为原字符长度 - 与自己相等的字符数量。

我们可以递推求解长度为 i i i 的字符串能构造的最大逆序对数为 f i f_i fi。在确定最短长度后开始考虑其他条件。

  1. 如何使得字符串中的逆序对个数恰好为 V V V 的同时,使得字典序最小。

同样利用上述构造最大逆序对的贪心策略,我们从前向后暴力枚举该位的字符 (从 a a a 开始枚举,满足字典序最小),剩下的字符按照逆序对最大的方法进行构造能否使得逆序对数 f i ≥ V f_i \geq V fiV,如果能就选定该字符,否则就枚举紧接着的下一位字符(具体见代码及注释)。

#include <bits/stdc++.h>
using namespace std;
int n;
/*  
贪心的思想,增加字符串长度相当于插入一个字符,增加的逆序对 = 大于自己 + 小于自己的,
最大构造逆序对的情况即不等于自己的字符数,于是有字符串中所有字符数量越接近越好,
在字符数 > 26 以后就又是从abc的顺序开始新增(满足字典序小),每次插入新字符增加的逆序对即为原字符长度 - 与自己相等的字符数量
于是我们可以暴力枚举字符,判断在选择此字符的情况下能否构造出逆序对数 >= n的
*/
int f[1010];
int get_max(){ // 获取长度为m的字符串的最大逆序对数
    for(int i = 2; i <= 26; i ++) f[i] = f[i - 1] + i - 1; // 长度小于26的字符串最大逆序对数
    int sum = 26, vis[30];
    for(int i = 0; i < 26; i ++) vis[i] = 1; // 记录当前字符串已经各个字符串各一个了
    for(int i = 27; f[i - 1] < n; i ++, sum ++){ 
        int ch = (i % 26 - 1 + 26) % 26; // 新增的字符按abc……的顺序新增,插入到逆序的位置,例如zyx……a,下一个接着插入a zyx……aa
        f[i] = f[i - 1] + sum - vis[ch]; vis[ch] ++; //新增逆序对字符总数 - 和自己相同的字符数
    }
}

int cnt[30], vis[30]; // cnt 代表已经确定的构造字符,vis代表后续按最大方法构造的字符
int get_add(int ch){
    int add = 0;
    for(int i = 0; i < ch; i ++) add += vis[i]; // vis 是还未确定的可以按任意顺序排列所以都可以计算进来
    for(int i = ch + 1; i < 26; i ++) add += cnt[i] + vis[i]; // 因为cnt已经确定了,后续字符只能在其后,所以新增的只能是 > ch 的字符数
    return add; 
}
bool check(int id, int m, int ch, int sum){
    for(int i = id + 1; i <= m; i ++){
        int maxadd = 0, ch1 = 0;
        for(int j = 0; j < 26; j ++){ // 和上述fi的求解过程同理,只是枚举字符选择最优解的那一个
            int add = get_add(j);
            if(maxadd < add){
                maxadd = add;
                ch1 = j;
            }
        }
        vis[ch1] ++;
        sum += maxadd;
    }
    memset(vis, 0, sizeof vis);
    if(sum >= n) return true; // 当剩余字符能构造出 >= n 的即返回true
    return false;
}

void solve(int m){
    int sum = 0;
    string ans;
    for(int i = 1; i <= m; i ++){
        for(int j = 0; j < 26; j ++){ // 每个位置都从'a' 开始枚举,看是否剩下的字符最大情况下仍然能构造出大于等于n的字符,若可以则使用当前的ch
            int initadd = get_add(j);
            cnt[j] ++;
            sum += initadd;
            if(check(i, m, j, sum)){
                ans += ('a' + j);
                break;
            }
            cnt[j] --; // 不满足,于是回溯枚举新的字符
            sum -= initadd;
        }
    }
    cout << ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    get_max();
    for(int i = 2; i <= n; i ++){
        if(f[i] >= n){
            solve(i);
            break;
        }
    }
    return 0;
}

一个贪心的构造题,使用暴力的方法实现,思维确实挺巧妙的。文章来源地址https://www.toymoban.com/news/detail-474834.html

到了这里,关于P8719 [蓝桥杯 2020 省 AB2] 字串排序题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2020 CSP - J初赛 题解

    快要CSP了,最近疯狂刷题中… 终于 抽出时间 乘爸妈不在 写了一篇题解 如需做题,请到以下网站自行练习。 本博客只提供讲解。 洛谷有题 初赛真题 - 信奥赛题库 题号 1~5: A A D C C 6~10: B A A A A 11~15: A D C A A 16~20: 对 错 对 错 A 21~25: D 错 错 对 D 26~30: B D 错 对 错 31~35:

    2024年02月11日
    浏览(41)
  • 2020ICPC南京【个人题解EFHKLM】

    首先如果炸弹在(0,0)或者机器人最终停在炸弹处,那么一定Impossible。 对于其他的情况,如果存在一条路径使得机器人可以不经过炸弹,那么一定存在一种方案,使得相同的方向在这个方案种是连在一起的。 于是可以直接枚举所有方向的排列,共4!个,判断每一种排列能否绕过

    2023年04月09日
    浏览(49)
  • 2020年 团体程序设计天梯赛——题解集

    Hello各位童学大家好!😊😊,茫茫题海你我相遇即是缘分呐,或许日复一日的刷题已经让你感到疲惫甚至厌倦了,但是我们真的真的已经达到了我们自身极限了吗?少一点自我感动,没有结果前别太松懈,请相信 ”一万小时定理“ 。当你迷茫时抬头看看远方回想当初那个稚

    2023年04月12日
    浏览(40)
  • 【C++题解】[CSP-J2020]优秀的拆分

    P a r t Part P a r t 1 1 1 读题 题目描述 一般来说,一个正整数可以拆分成若干个正整数的和。 例如: 1 = 1 1=1 1 = 1 , 10 = 1 + 2 + 3 + 4 10=1+2+3+4 10 = 1 + 2 + 3 + 4 等。对于正整数 n n n 的一种特定拆分,我们称它为“优秀的”,当且仅当在这种拆分下, n n n 被分解为了若干个不同的 2

    2024年02月06日
    浏览(43)
  • [洛谷]P8662 [蓝桥杯 2018 省 AB] 全球变暖(dfs)

    读题不规范,做题两年半!  注意:被海水淹没后的陆地应用另一个字符表示,而不是把它变为海洋,这个点可以便利,但不能被当作起点,不然就只有 36 分。 ACocde:  over~

    2024年02月16日
    浏览(37)
  • 2020第十一届蓝桥杯Python组国赛【真题+解析+代码】

    🚀 真题练习,冲刺国赛 🚀 2020年第十一届蓝桥python组国赛真题+解析+代码 博观而约取,厚积而薄发 🏆 国赛真题目录 🍰1.题目 美丽的2 👑2.思路分析 难度:⭐️ 标签:枚举字符串 🎇 思路:暴力法 🔱 思路分析: 本题为填空题,只需要遍历 1 → 2020 1→2020 1 → 2020 即可:

    2024年02月07日
    浏览(43)
  • 题解动态规划:蓝桥杯2022国赛B组 题解 A题目

    在这组题(蓝桥杯C/C++ B组 国赛)里面挑了几道喜欢的题目,做了一下,笔记思路如下。( 其实是我觉得能做出的题 ) 题目图片来源于:CSDN 罚时大师月色 请问2022,拆分成10个不同的正整数有多少种不同的分法。 这道题目,拿到手上的时候,第一个想法是暴力,但是,每次

    2023年04月08日
    浏览(92)
  • 第十四届蓝桥杯题解

    声明:以下都无法确定代码的正确性,是赛时代码,希望大家见谅!思路可以参考,等后续可以评测之后再去修改博客内错误,也希望大家能够指正错误! 分析:这道题直接暴力求解即可,八重for循环,注意剪枝,前四个for循环必须是2013,然后月数的第一位不能超过1,天数

    2023年04月10日
    浏览(42)
  • 蓝桥杯历年真题分类(包含超详细题解)

    ✍个人博客:https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343 📚专栏地址:蓝桥杯题解集合 📝官网题库地址:蓝桥杯练习系统 📣专栏定位:为想备考蓝桥杯的小伙伴整理常考算法题解,祝大家都能取得满意的成绩! ❤️如果有收获的话,欢迎点赞👍收藏📁,您的支持就是我创

    2023年04月08日
    浏览(50)
  • 【蓝桥杯】信号覆盖范围——BFS(java题解)

    小蓝负责一块区域的信号塔安装,整块区域是一个长方形区域,建立坐标轴后,西南角坐标为 (0, 0), 东南角坐标为 (W, 0), 西北角坐标为 (0, H), 东北角坐标为 (W, H)。其中 W, H 都是整数。 他在 n 个位置设置了信号塔,每个信号塔可以覆盖以自己为圆心,半径为 R 的圆形(包

    2023年04月09日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包