首页 > 其他分享 >CF1809D Binary String Sorting 题解

CF1809D Binary String Sorting 题解

时间:2023-12-06 18:56:41浏览次数:46  
标签:Binary Sorting 删除 分界线 题解 交换 操作 减少 逆序

题意:

思路:

贪心:

单调不降的 $ 01 $ 字符串,一定是一串连续的 $ 0 $ 再加上一串连续的 $ 1 $ 。由于每次操作的代价很大,所以需要在操作次数尽可能少的情况下,尽可能多地使用交换操作

由于 $ 1 $ 次交换操作,只能减少 $ 1 $ 个逆序对,当存在多个逆序对时,优先通过删除操作减少逆序对的数量,来减少逆序对的数量。当逆序对的数量减少到 $ 1 $ 时,此时再采取 $ 1 $ 次交换操作,即为最优策略;当逆序对的数量减少到 $ 0 $ 时,此时无需进行任何操作,即为最优策略。

因此,枚举 $ 01 $ 分界线。在分界线同一侧进行交换操作是无意义的,那么,分界线左侧的 $ 1 $ 全部删除,分界线右侧的 $ 0 $ 全部删除。注意到,分界线左侧第一个字符为 $ 1 $ 且分界线右侧第一个字符为 $ 0 $ 时, $ 1 $ 次交换操作优于 $ 2 $ 次删除操作,此时优先执行交换操作,即为最优策略。

标签:Binary,Sorting,删除,分界线,题解,交换,操作,减少,逆序
From: https://www.cnblogs.com/ShawyYum/p/17880283.html

相关文章

  • ucup hefei 题解
    比赛链接B很有意思的题首先题目的要求为可以拆分成\(2\)个不相交的不降子序列根据\(dilworth\)定理,最小链覆盖\(=\)最长反链,所以要求最长反链\(\le2\)即原序列的逆序列的最长不降子序列长度\(\le2\)不难得到一个\(dp\)做法为:令\(f_{i,j}\)为到数\(i\),最长上......
  • python HTML文件标题解析问题的挑战
    引言在网络爬虫中,HTML文件标题解析扮演着至关重要的角色。正确地解析HTML文件标题可以帮助爬虫准确地获取所需信息,但是在实际操作中,我们常常会面临一些挑战和问题。本文将探讨在Scrapy中解析HTML文件标题时可能遇到的问题,并提供解决方案。问题背景在解析HTML文件标题的过程中,......
  • Error: error:0308010C:digital envelope routines::unsupported 【问题解决】【转载
    原文链接:  https://www.cnblogs.com/jaxu/p/17171211.html今天早上打开电脑,更新了日常工作的github仓库,然后就是习惯性地执行了"npminstall",发现报了下面这个错误:Error:error:0308010C:digitalenveloperoutines::unsupported顺便看了一下错误堆栈,发现是一个Node......
  • 线性代数题解
    前言写完了这道题我好想刚明白一点最小割???UU好闪,拜谢UU。题解首先,我们可以发现若第\(i\)行的\(B\)没选,那么第\(i\)列的\(B\)也不选,所以此时对于行和列是等价的。若\(A_i\)是\(0\),则会减少贡献\(\sum_{j}B_{i,j}\)。否则会减少贡献\(C_i\)。当\(A_i\)是\(0\)......
  • CF603题解
    CF603CodeforcesRound334(Div.1)CF603AlinkCF603A题意现有一个长度为\(n\)的01串,可以进行一次区间翻转(起点终点随意,并且区间里的值1变0,0变1),得到一个新的01串,使得得到的新的01串中的一个子串最长(子串不一定连续),且这个子串是01间隔的,没......
  • CF1824B1 LuoTianyi and the Floating Islands (Easy Version) 题解
    题意:思路:由于$k∈[1,3]$,分类讨论:当$k=1$时,有人结点自身即为好结点,每种情况的期望为$\frac{1}{n}$,$n$种情况的期望和为$1$。最终答案即为$1$。当$k=2$时,$2$个有人结点之间的路径上的结点即为好结点,那么问题转化为:树上所有路径的结点......
  • ABC325G offence 题解
    给出一个长为\(n\)的字符串和非负整数\(k\)。你可以进行以下操作若干次,使得最终字符串长度最小。选择一个字串of。然后删掉of以及这之后的\(i\)个字符。\(i\)由你决定,但要满足\(0\leqi\leqk\)。输出这个最小长度。\(1\leqn,k\leq300\)。做完以后感觉很简单。但......
  • CTFpwn格式化字符串两种应用及2023ISCTF的fmt题解wp
    三个例子的引入目前我遇到的格式化字符串漏洞(formatstring,后文简称fmt)主要存在于printf函数,本文也就以printf举例。例一,标准格式的printf read(0,buf,33);printf("%s",buf);例二,占位符与变量 printf("%d%c%s",a,b,c);//%d%c%s会访问变量以输出整型,字符等。其中a,b,c为三......
  • [AGC032D] Rotation Sort 题解
    题目链接点击打开链接题目解法题目中的操作可以理解为一个点移动位置首先给出一个结论:每个点只会动至多一次考虑\(dp\)一个比较妙的状态设定是\(f_i\)表示\(i\)不动的方案数不妨枚举\(j\)表示上一个不动点,限制是\(j<i\)且\(p_j<p_i\)中间满足\(j<k<i\)且\(p_......
  • [AGC037D] Sorting a Grid 题解
    题目链接点击打开链接题目解法从后往前推一下,可以得到\(C\)一定要把每一行的数都归位到那一行,\(B\)一定要每一列的目标行数互不相同考虑构造\(B\)这个限制看起来略有些网络流,所以考虑如何建图令\(a_{i,j}\)的目标行数为\(ln_{i,j}\),我们由\(i\toln_{i,j}\)连边不......