首页 > 其他分享 >2023-10-26 模拟赛

2023-10-26 模拟赛

时间:2023-11-01 09:25:33浏览次数:33  
标签:10 26 方案 text popcount 答案 2023 前导 我们

C

很久没见到过这么清晰的讲题人了。

我们先来考虑一些边界情况。

全是 \(0\) 时

这个时候其实就是划分成至少 \(k\) 段的方案数,组合数计算即可。答案大概为

\[\sum_{i = k - 1}^{n}\binom{n - 1}{i} \]

存在前导零长度大于等于 \(k - 1\) 时

例如 001111 想分成至少 \(3\) 段,发现仅仅是开头的 00 就已经可以分出去两段了,这个时候我们把最后的一段直接分给除前导零外的段即可。最大值即为除去前导零的剩余段,方案数可以组合数计算,设前导零长度为 \(c(c \ge k - 1)\) 则答案大致为

\[\sum_{i=k-1}^c\binom{c-1}{i}\]

事实上,第一种情况就是第二种情况中 \(c = 0\) 时,这里拿出来单独讨论了。

一般情况

实际上,这里的 一般情况 指的就是前导零不够分的时候。我们可以从前导零够分段的情况获得一些启示,显然分开算两段一定是没有合在一起算好的。

还是简要证明一下吧。

考虑两个二进制数 \(A, B\),如果分开算的话,和为 \(A+B\),如果合到一起算的话和为 \(A \times 2^{|B|}+B\)。结论显然。

根据上面的证明,我们一定是要从前 \(c(0 \le c < k - 1)\) 个前导零中分出尽量多的段出来,则 \(k' = k - c, n' = n - c\)。

这一部分的方案数就是 \(1\),我们已经确定了每一位单独一段。

问题进行了转化,我们有一个第一位为 \(1\) 的二进制串,根据我们上面的证明,我们分段的策略也仍然是分出 \(k'- 1\) 段长度为 \(1\) 的段和一段长度为 \(n' - k' + 1\) 的段,我们考虑它答案的形式。

令当前选择的大段为 \(S\),那么整段的答案变为 \(S - \text{popcount(S)} + c\),后面这个 \(c\) 实际上就是整段的 \(1\) 数量,将 \(S\) 内计入大段的 \(1\) 减掉即为长度为 \(1\) 的 \(1\) 的贡献。

问题来了,关于方案数,我们是否可以对当前的 \(S\) 进行一些小变化使得答案还是最大的。

考虑当 \(S\) 的末尾为 \(1\) 时,如果这一位变成了 \(0\),\(S \to S - 1, \text{popcount(S)} \to \text{popcount(S)} - 1\),\((S - 1) - (\text{popcount(S)} - 1) = S - \text{popcount(S)}\),答案没有任何变化。

注意,当 \(n = k\) 时,答案为 \(\text{popcount(S)}\),方案数为 \(1\)。

标签:10,26,方案,text,popcount,答案,2023,前导,我们
From: https://www.cnblogs.com/Rainsheep/p/17802273.html

相关文章

  • 2023-10-3 模拟赛
    这模拟赛质量对于我来说疑似有点高了,整篇题解。A感觉是很感性的贪思想,大爷讲的挺详细。合法的括号串每个前缀肯定都是\(\ge0\)的,考虑设置正反串左右括号分别的数量,然后贪心的分别放到左括号的计数里,每次结束后判下r1>l1或者r2>l2。B考虑dp,设\(f_{i,j}\)表示从......
  • 【爬虫实战】用Python采集任意小红书笔记下的评论,爬了10000多条,含二级评论!
    目录一、爬取目标二、爬虫代码讲解2.1分析过程2.2爬虫代码三、演示视频一、爬取目标您好!我是@马哥python说,一名10年程序猿。我们继续分享Python爬虫的案例,今天爬取小红书上指定笔记("巴勒斯坦"相关笔记)下的评论数据。老规矩,先展示结果:截图1:截图2:截图3:共爬取了1w多条"......
  • AtCoder Beginner Contest 326 F
    F-RobotRotation一句话不开LL,见祖宗感谢大佬,和洛谷上的题解上面已经将的很清楚了,但是如果你跟我一样一开始看不懂他们的代码,那么这篇可能为你解惑点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglong#defineintLL//LL!map<LL,LL>ma;......
  • 10.24
    跟着模板敲代码(1)项目的架构 Dao为数据持久层,用于实现数据库的增删改查entity为javabean用于封装数据库中的对象servlet为前端数据的处理层jsp为前端页面现在来一个个实现 BaseDao用于链接mysql数据库publicclassBaseDao{static{try{C......
  • win10实现用VSCode打开文件夹
    1.修改注册表1.【Win+R】打开运行,输入【regedit】,打开【注册表】2.【HKEY_CLASSES_ROOT】==>【*】==>【shell],如果没有【shell】,则在【*】下右键,【新建】==>项,建立【shell分支】3.【shell】下【新建】==>【项】==>【VisualCode】,【双击】右侧窗口的【默认】,在......
  • 10.31
    10.31字符与字符串字符字符在计算机中以ASCII码进行存储(从0到127->对应7位二进制)字符A```Z```的ASCII码值从6590字符a```z```的ASCII码值从97122对应的⼤⼩写字符(a和A)的ASCII码值的差值是32数字字符09的ASCII码值从4857换⾏\n的ASCII值是:10第一位二进制位代表扩......
  • 10.23
    学习jdbc的基础概念,快速入门1.jdbc的概念JDBC(JavaDataBaseConnectivity:java数据库连接)是一种用于执行SQL语句的JavaAPI,可以为多种关系型数据库提供统一访问,它是由一组用Java语言编写的类和接口组成的。JDBC的作用:可以通过java代码操作数据库2.jdbc的本质其实就是java官方提供......
  • 【专题】2023年中国新消费潜力洞察蓝皮书报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34074近年来,随着中国消费升级的趋势,新兴消费品牌在市场上逐渐崭露头角。这些品牌以挑战者的身份进入市场,通过创新的供应链、产品和营销策略,以用户为核心满足新的消费需求,实现了短期内的强劲增长和销售规模的快速扩张。然而,经济环境、疫情冲击和激烈......
  • 【专题】2023文化娱乐新消费报告报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34074近年来,随着中国消费升级的趋势,新兴消费品牌在市场上逐渐崭露头角。这些品牌以挑战者的身份进入市场,通过创新的供应链、产品和营销策略,以用户为核心满足新的消费需求,实现了短期内的强劲增长和销售规模的快速扩张。然而,经济环境、疫情冲击和激烈......
  • 【专题】2023国潮美食新消费产业洞察报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34074近年来,随着中国消费升级的趋势,新兴消费品牌在市场上逐渐崭露头角。这些品牌以挑战者的身份进入市场,通过创新的供应链、产品和营销策略,以用户为核心满足新的消费需求,实现了短期内的强劲增长和销售规模的快速扩张。然而,经济环境、疫情冲击和激烈......