草庐IT

牛客小白月赛50解题报告

m0-51303687 2023-03-28 原文

签到题，模拟即可，注意除法不是整除。

贪心

int res=0;
while(n>x){
    n/=2;
    res++;
}
while(n>0){
    n-=x;
    res++;
}

这题没看清楚，以为取余也要从数组中选择。实际上这是没必要的，只要在全体>1的自然数集合中取值即可。
这样的话问题就简单了，可以直接mod 2，但实际上这样还不对，比如5 10 15 20 0这样的数据就可以直接mod 5。

参考思路：
如果数组中所有数互质且至少存在一个>=2的数，则直接先mod 2再把所有还剩1的数都-1，共2次操作；
否则，可以mod 所有数的gcd，只需1次操作；
否则，若只存在0，则只需0次操作；
否则（即只存在0和1），只需1次操作。

	int a, n, gc = 0;
	bool f2 = 0, allZero = 1; //是否有>=2的
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		gc = gcd(gc, a);
		if (a > 0)	allZero = 0;
		if (a > 1)	f2 = 1;
	}
	//全为0
	if (allZero)
		putchar('0');
	//互质，则对2取余，那么剩下0和1。注意排除全<2的情况
	else if (gc == 1&&f2)
		putchar('2');
	//不互质
	else    putchar('1');

一开始看成两两异或再相加，后来发现不是这样。
不难发现最多不超过三人可能相同，因此只要罗列所有可能性并计算贡献即可。具体思路见代码，其中[i]=j表示第i天选择j作为“生日”。

if (n == 1)         res = 0;
else if (n == 2)    res = a[1] ^ a[2];
else {
    initPow(n);
    for (int i = 1; i <= n - 1; i++) {
	if (2 * i <= n) {
		int p = a[i] ^ a[i * 2];
		if (2 * i + 1 <= n) {
			//[i]=i,[i*2]=i,[i*2+1]=i+1
			p = (p * pow2[n - 3]) % MOD;
			res = (res + p) % MOD;
			// [i]=i,[i*2]=i,[i*2+1]=i
			p = ((a[i] ^ a[i * 2] ^ a[i * 2 + 1]) * pow2[n - 3]) % MOD;
			res = (res + p) % MOD;
			//[i]=i,[i*2]=i+1,[i*2+1]=i
			p = ((a[i] ^ a[2 * i + 1]) * pow2[n - 3]) % MOD;
			res = (res + p) % MOD;
		}
		//[i]=i,[i*2]=i
		else {
			p = (p * pow2[n - 2]) % MOD;
			res = (res + p) % MOD;
		}
	}
        //[i]=i/2,[i+1]=i/2
	if (i % 2 == 0) {
		int p = ((a[i] ^ a[i + 1]) * pow2[n - 3]) % MOD;
		res = ((res + p)) % MOD;
	}
    }
}


a < c:全部自己加工，否则：

  1. b > c:可连续生产半成品，k件共需n=c+kb分钟,得k=(n-c)/b
  2. b <= c:k件共需n=b+kc,得k=(n-b)/c

两种情况均可以对加工半成品(c)的时间进行“紧凑”。剩下的时间做成品

if(a<=c)    printf("%d",n/a);
else {
    int half=(b<=c)?(n-b)/c:(n-c)/b;
    //(n-c*half)/a:"紧凑"过后剩下的时间还能做多少成品
    printf("%d",half+(n-c*half)/a);
}
解题牛客2823984res互质算法与数据结构

有关牛客小白月赛50解题报告的更多相关文章

  1. 报告回顾丨模型进化狂飙，DetectGPT能否识别最新模型生成结果？ - 2

    导读语言模型给我们的生产生活带来了极大便利，但同时不少人也利用他们从事作弊工作。如何规避这些难辨真伪的文字所产生的负面影响也成为一大难题。在3月9日智源Live第33期活动「DetectGPT：判断文本是否为机器生成的工具」中，主讲人Eric为我们讲解了DetectGPT工作背后的思路——一种基于概率曲率检测的用于检测模型生成文本的工具，它可以帮助我们更好地分辨文章的来源和可信度，对保护信息真实、防止欺诈等方面具有重要意义。本次报告主要围绕其功能，实现和效果等展开。（文末点击“阅读原文”，查看活动回放。）Ericmitchell斯坦福大学计算机系四年级博士生，由ChelseaFinn和Chri

  2. 牛客网专项练习30天Pytnon篇第02天 - 2

    1.在Python3中，下列关于数学运算结果正确的是:（B）a=10b=3print(a//b)print(a%b)print(a/b)A.3，3，3.3333...B.3，1，3.3333...C.3.3333...，3.3333...，3D.3.3333...，1，3.3333...解析：    在Python中，//表示地板除（向下取整），%表示取余，/表示除（Python2向下取整返回3）2.如下程序Python2会打印多少个数:（D）k=1000whilek>1:    print(k)k=k/2A.1000 B.10C.11D.9解析：    按照题意每次循环K/2，直到K值小于等

  3. ruby-on-rails - 是否有任何基于可定制模板的 Ruby 或 Rails 报告工具？ - 2

    我正在寻找一个用ruby​​或rails完成的报告生成器，它允许用户首先定义一个模板，然后将数据提取到模板中。我一直在浏览“TheRubyBox:报告部分”(https://www.ruby-toolbox.com/categories/reporting.html)有两个报告工具类似于我正在寻找的:ThinReports:这真的很好。您下载一个模板编辑器，然后定义您自己的报告模板，然后通过组合thinreportsgem，您可以从您的应用程序中获取SVG或PDF报告。ODFReport:它使用ODF文件作为模板，可以通过OpenOffice和MSWord2010进行编辑。然后你就可以

  4. 2023爱分析·流程中台市场厂商评估报告：微宏科技 - 2

     目录1. 研究范围定义2. 流程中台市场分析3. 厂商评估：微宏科技4. 入选证书 1.   研究范围定义近年来，随着外部市场环境快速变化、客户需求愈发多样，企业逐渐意识到，自身业务需要更加敏捷、高效，具备根据市场需求快速迭代的能力。业务流程的自动化能够帮助企业实现业务的敏捷高效，因此受到越来越多企业的关注。企业的“自动化武器库”品类丰富，包括低/零代码平台、RPA、BPM、AI等。企业可以使用多项自动化工具，但结果往往是各项自动化工具处于各自的“自动化烟囱”之中，仅能实现碎片式自动化。例如，某企业的IT团队可能在使用低代码平台、财务团队可能在使用RPA、呼叫中心则可能在使用聊天机器人。自动

  5. IDC最新MarketScape报告：DevOps市场需求广泛 - 2

    日前，全球著名咨询机构IDC最新MarketScape报告《中国DevOps平台市场厂商评估，2022》正式发布，此报告中对中国主流DevOps云厂商分别从现有能力和未来战略维度两个层面对厂商进行评估，IDC对具有代表性的8家提供商进行了深度研究，他们分别是（按照拼音字母顺序）：AWS、阿里云、百度、博云、华为云、京东云、微软、腾讯云（CODING）。华为云、阿里云和腾讯云CODING均在战略和能力两大维度表现强势，成功入席领导者(Leaders)位置。IDC MarketScape:中国DevOps平台市场厂商评估,2022华为云软件开发生产线DevCloud在市场份额和发展战略两大维度均排

  6. ruby-on-rails - Simplecov 覆盖率报告似乎遗漏了某些行 - 2

    在澄清了simplecov如何确定一条线是否已被测试执行之后。我有以下方法:defover?end_at其中end_at是对象的ActiveRecord属性。在以下规范中进行了练习:describeCalendarEntrydoit'candeterminethataneventhasended'do@entry.end_at=1.day.ago@entry.over?.shouldbe_trueendend在覆盖范围内运行规范后，它显示以下结果:我已经在Debug模式下运行了测试，并在此行上设置了一个断点，并确认规范确实符合它。这并不仅限于此方法中的这一行，包括使用ActiveRec

  7. ruby - 特拉维斯报告损坏的 Gemfile.lock 的奇怪消息 - 2

    我使用bundler来安装东西，因为我添加了Gemfile.lock，travis开始提示:YourGemfile.lockiscorrupt.ThefollowinggemismissingfromtheDEPENDENCIESsection:'echoe'当然，一切都在本地运行。它也可以使用DeployBot。我什至安装了dockerubuntu并尝试了，仍然可以。我的Gemfile.lock没有损坏。使用相同版本的ruby​​和bundler。这是怎么回事？更新这与bundler版本有关。我使用的是1.11.0，但收到报告说它可以与eg一起使用。1.8.3.??

  8. Ruby on Rails 报告工具？ - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于StackOverflow来说是偏离主题的，因为它们往往会吸引自以为是的答案和垃圾邮件。相反，describetheproblem以及迄今为止为解决该问题所做的工作。关闭9年前。Improvethisquestion我正在寻找ruby​​或rails中的报告生成工具，它允许用户定义模板，然后将数据提取到创建的模板中。我一直在翻“TheRubyBox:reportingsection.”我看过两种报告工具:ThinReports:这真的很好。您可以使

  9. ruby-on-rails - 解决 ruby​​ 中的旅行商问题(50 多个位置) - 2

    我在一家express公司工作。我们目前通过“手动”解决了50多个位置路线。我一直在考虑使用GoogleMapsAPI来解决这个问题，但我读到有24分的限制。目前我们在服务器中使用Rails，所以我正在考虑使用ruby​​脚本来获取50多个位置的坐标并输出合理的解决方案。您会使用什么算法来解决这个问题？Ruby是解决这类问题的好编程语言吗？你知道任何现有的ruby​​脚本吗？ 最佳答案 这可能是您正在寻找的:警告:此站点被firefox标记为攻击站点-但我似乎没有。其实我之前用过没问题[检查URL的修订历史]rubyquiz似乎已关

  10. 中国民用飞机制造行业市场现状规模及发展战略规划报告2021-2027年 - 2

    中国民用飞机制造行业市场现状规模及发展战略规划报告2021-2027年详情内容请咨询鸿晟信合研究院！【全新修订】：2022年2月【撰写单位】：鸿晟信合研究研究【报告目录】第1章：中国民用飞机制造行业发展综述1.1民用飞机制造行业概述1.1.1民用飞机的概念1.1.2飞机制造的概念1.1.3民用飞机的分类1.2民机制造行业周期特性1.2.1影响行业周期的因素（1）GDP增速分析（2）运量增量分析（3）飞机更替分析（4）航空公司获利水平1.2.2行业现阶段周期分析1.2.3行业现阶段景气分析1.3民机制造信息化分析1.3.1信息化技术应用状况分析（1）MDO技术应用分析（2）供应链协同研发分析（3

随机推荐