Codeforces Round 963 (Div. 2)

A题:Question Marks

题目:

Tim正在做一个由 4n 个问题组成的测试,每个问题都有 4 个选项:“A”、“B”、“C”和“D”。对于每个选项,有 n 个正确答案对应于该选项,这意味着有 n 个问题的答案为“A”。 n 个答案为“B”的问题, n 个答案为“C”的问题以及 n 个回答为“D”的问题。每道题,蒂姆都把答案写在答题纸上。如果他想不出答案,他就会留下一个问号。为了这个问题。您将获得 4n 个字符的答题卡。蒂姆最多能得到多少个正确答案?


输入

第一行包含单个整数 t ( 1 <= t <= 1000 )—测试用例的数量。

每个测试用例的第一行包含一个整数 n ( 1 <= n <= 100 )。

每个测试用例的第二行包含 4n 个字符( si 属于{A, B, C, D, ?} )的字符串 s —Tim对问题的回答。

输出

对于每个测试用例,打印一个整数—Tim可以达到的最大分数。

样例

注意

在第一个测试用例中,每个答案“A”、“B”、“C”和“D”,只有一个问题,所以蒂姆有可能所有的答案都是正确的。在第二个测试案例中,只有两个正确答案'A',这使得他在任何情况下都能得到2 分。在第三个测试用例中,Tim最多可以得到 2 个选项'A'的正确答案和 2 个选项'B'的正确答案。例如,如果答案是'AACCBBDD',他将得到 4 分。在第四个测试案例中,他拒绝回答任何问题,这使他获得 0 分。


解题思路:

问题问的是他的最大得分,例如第一个样例他的答案为ABCD,那么我们默认正确的答案为ABCD,所以能得到4分,这种确认正确答案要建立在条件之上,确保每个选项出现的次数是一样的,当为5个问题时,必然有四个答案为A,B,C,D,还剩一个答案那就可以是任意一个,因为是要得最大的分,那么剩余那一个一定是答案出现两次的选项。当出现‘ ?’时可视为他空着这个题,没写答案,必然不得分。


AC代码:
#include<iostream>
using namespace std;
const int N=500;
int t,n;
char ch[N];
int main(){cin>>t;while(t--){cin>>n;cin>>ch;int suma=0,sumb=0,sumc=0,sumd=0;//记录四个选项出现次数for(int i=0;i<4*n;i++){if(ch[i]=='A')suma++;else if(ch[i]=='B')sumb++;else if(ch[i]=='C')sumc++;else if(ch[i]=='D')sumd++;}//因为4*n个问题每个选项最多出现n次if(suma>n)suma=n;if(sumb>n)sumb=n;if(sumc>n)sumc=n;if(sumd>n)sumd=n;cout<<suma+sumb+sumc+sumd<<endl;}return 0;
}

B题:Parity and Sum

题目: 

给定一个由n个正整数组成的数组 a 。

在一个操作中,您可以选择任意一对索引 (i, j) ,使 ai 和 aj 具有不同的奇偶校验,然后用它们的和替换较小的一个。更正式地说:

-如果ai < aj ,请将 ai 替换为 ai + aj

-否则,将 aj 替换为 ai + aj 。

找出使数组的所有元素具有相同奇偶性所需的最小操作数。


输入

第一行包含单个整数 t ( 1 <= t <= 10^4 )—测试用例的数量。

每个测试用例的第一行包含一个整数 n ( 1 <= n <= 2*10^5 )。

第二行包含 n 整数 a1, a2, ..., an ( 1 <= ai <= 10^9 )—数组 a 的元素。

保证所有测试用例的 n 之和不超过 2*10^5 。

输出

对于每个测试用例,输出一个整数——所需的最小操作数。

样例

注意

在第一个测试用例中,所有整数都具有相同的奇偶性。因此,不需要任何操作。

在第三个测试用例中,我们可以执行两个操作 (1, 2) 和 (1, 3) 。数组 a 转换如下: a = [2, 3, 4] -> [5, 3, 4] -> [5, 3, 9] 。

在第四个测试用例中,最优操作序列的示例是 (1, 2) 、 (1, 3) 、 (1, 4) 和 (1, 4) 。数组 a 转换如下: a = [3, 2, 2, 8] -> [3, 5, 2, 8] -> [3, 5, 5,8] -> [11, 5, 5, 8] -> [11, 5, 5, 19] 。


解题思路:

通过上面图片,我们知道了奇偶两两相加的特点,由此我们可以得出只有odd+even=odd是可行的,我们是这个式子中较小的为偶数,偶数与奇数相加为奇数,这就把偶数变为奇数了,当偶数>奇数时,通过这样的操作,可以把这个奇数的值变得更大,使得前面的条件偶数>奇数变为偶数<奇数,那么这样我们又可以通过操作一把偶数变为奇数。

那么我们的操作顺序是什么,先哪个奇数跟哪个偶数先操作,由题意知,我们要最大程度满足偶数<奇数这个条件,因为只有这个条件操作才是对目标序列有贡献的。这样我们的奇数使其最大,偶数使其最小,既能把偶数变为奇数的情况下,奇数的值也可能得到了更新。使偶数按照递增的顺序是最优的,例如a={2,3,4,8},开始奇数最大为3,偶数递增为{2,4,8},第一次把2变为5,此时奇数最大值为5,第二次5与4操作变为9,奇数最大值又得到更新变为9,第三次操作9与8变为17结束。这样最优没有奇数<偶数的情况。那么如果有奇数<偶数的情况,我们就让此时最大的奇数与最大的偶数进行一次操作,这样得到的奇数足够大,可以满足所有的偶数了,例如a={1,2,6},开始最大奇数一个也不满足,先让1与6进行一次操作,1变为7,这样7可以与2也可以与6进行操作了。如果1先于2进行操作,1变为3,在进行一次2变为5,5<6,最大奇数又小于偶数这样无非多一次操作。


AC代码:
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N];//原数组
ll n,t;
priority_queue<ll,vector<ll>,greater<ll>> q;//升序优先队列(偶数)
int main(){cin>>t;while(t--){cin>>n;ll maxodd=0,maxeven=0;//最大奇数,最大偶数ll sum=0;//操作次数while(!q.empty()){//多次输入,清空队列q.pop();}for(int i=1;i<=n;i++){cin>>a[i];if(a[i]%2==1){maxodd=max(maxodd,a[i]);//求奇数最大值}else{q.push(a[i]);maxeven=max(maxeven,a[i]);//求偶数最大值}}if(maxodd==0||q.empty()){//都为奇数或偶数cout<<0<<endl;}else{ll len=q.size();ll sum1=0;//队内偶数操作次数while(1){if(q.top()>maxodd){maxodd=maxodd+maxeven;}else{maxodd=maxodd+q.top();q.pop();sum1++;}sum++;if(sum1==len)break;}cout<<sum<<endl;}}return 0;
}

C题:Light Switches

题目:

有一个由 n 个房间组成的公寓,每个房间的灯最初都是关闭的。为了控制这些房间的灯光,公寓的主人决定在房间里安装芯片,这样每个房间只有一个芯片。并且在不同的时间安装芯片。具体来说,这些时间由数组 a1, a2,..., an 表示,其中 ai 是时间(以分钟为单位)芯片安装在第 i 个房间。一旦安装了芯片,它就会每隔 k 分钟改变一次房间的灯光状态—它会打开灯光 k 分钟。然后在接下来的 k 分钟内将其关闭,然后在接下来的 k 分钟内将其重新打开,依此类推。换句话说,芯片在分钟 ai 、ai + k 、ai + 2k 、ai + 3k 改变灯的状态,公寓里所有房间的灯最早什么时候打开?


输入

第一行包含单个整数 t ( 1 <= t <= 10^4 )—测试用例的数量。

每个测试用例的第一行包含两个整数 n 和 k ( 1 <= k <= n <= 2*10^5 )—公寓中的房间数和芯片的周期。

第二行包含 n 不同的整数 a1, a2, ..., an ( 1 <= ai <= 10^9 )—安装芯片的时刻。

保证所有测试用例的 n 之和不超过 2*10^5 。

输出

对于每个测试用例,打印一个整数—问题的答案(以分钟为单位)。如果不存在所有房间的灯都打开的时刻,则改为打印 -1。

样例

注意

在第一个测试案例中,所有的灯都会在 5 分钟内打开,而不会被芯片关闭。答案是 5 。在第二个测试案例中,由于第一个指示灯将在 2, 3, 4, 8, 9, 10, 14, ... 分钟时亮起。同时,第 4 个指示灯将在 5, 6, 7, 11, 12, 13, 17, ... 分钟亮起。这两个序列没有任何相同的数字,因此它们永远不会同时出现。在第三个测试案例中,可以看到第一个灯和第二个灯将在 6 和 7 分钟关闭。但芯片将在 9 和 10 分钟时重新打开它们。第 3 和第 4 个灯也将在第 10 分钟亮起,因此答案是 10 。


解题思路:

灯亮的时刻:

  • x→x+k−1
  • x+2k→x+3k−1
  • x+4k→x+5k−1

列表中的每个段(除了第一个)实际上是它前面的段,移动了 2k 分钟。这也意味着,如果我们除以 2k 并在每个线段的两端取余数,则所有这些线段都变得相等。因此,我们将第 i 个芯片的片段称为 (ai mod 2k,(ai+k−1) mod 2k) 。因此,我们的问题被简化为:找到最小整数 s ,使得:

  1. max(a)≤ s 出现在每个部分中

  2. s mod 2k 属于其中的每个段之中


AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[200001];
int main() {int t;cin>>t;while(t--){int n,k;cin >> n >> k;for(int i = 1; i <=n; ++i)cin>>a[i];sort(a+1,a+n+1);for(int i=1; i<=n; ++i)a[i]+=(a[n]+k-1-a[i])/(k*2)*k*2;sort(a+1,a+n+1);if(a[n]-a[1]+1>k) cout<<-1<<endl;else cout<<a[n]<<endl;}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/394374.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

个人知识库与RAG的技术

构建个人知识库时&#xff0c;采用RAG结合LangChain的方法极为有效。RAG&#xff0c;即检索增强生成技术&#xff0c;是一种前沿的自然语言处理手段&#xff0c;它融合了信息检索的精确匹配与语言模型的高效文本生成&#xff0c;为处理自然语言相关任务提供了一种既灵活又准确的…

未来已来:人工智能如何重塑Facebook的用户体验?

在数字化时代的浪潮中&#xff0c;人工智能&#xff08;AI&#xff09;正成为推动技术进步和用户体验优化的核心力量。Facebook&#xff08;现Meta Platforms&#xff09;作为全球领先的社交媒体平台&#xff0c;正在充分利用人工智能技术&#xff0c;以重塑用户体验&#xff0…

Spring Boot 3.0 热部署

idea开发环境下的spring boot 3.0热部署启用非常简单&#xff0c;并没有网上教程讲的需要对idea做一些设置。 只需引入依赖&#xff1a; developmentOnly org.springframework.boot:spring-boot-devtools其他不需要做任何设置。 服务启动中&#xff0c;改了代码或配置后&…

振动分析-18-基于振动分析进行故障诊断的思路和步骤

参考树立正确的振动诊断思路 参考振动分析相关知识的储备及振动分析仪的局限性 参考如何进行振动分析诊断(译文) 1 正确的故障诊断意识 我们通常在学习班听到的是大学教授以及专家讲解的故障诊断的基础理论,对于刚接触这个专业的人来说,微分方程和复杂的矩阵却有点让人忘…

JeecgBoot低代码平台简单记录

BasicModal弹窗 Usage 由于弹窗内代码一般作为单文件组件存在&#xff0c;也推荐这样做&#xff0c;所以示例都为单文件组件形式 注意v-bind"$attrs"记得写&#xff0c;用于将弹窗组件的attribute传入BasicModal组件 attribute&#xff1a;是属性的意思&#xff0c;…

Spring全家桶(三):Spring AOP

Spring AOP面向切面编程 1.面向切面编程思维&#xff08;AOP&#xff09; 1.1.面向切面编程思想AOP AOP&#xff1a;Aspect Oriented Programming面向切面编程 AOP可以说是OOP&#xff08;Object Oriented Programming&#xff0c;面向对象编程&#xff09;的补充和完善。O…

一键生成专业PPT:2024年AI技术在PPT软件中的应用

不知道你毕业答辩的时候有没有做过PPT&#xff0c;是不是也被这个工具折磨过。没想到现在都有AI生成PPT的工具了吧&#xff1f;这次我就介绍几款可以轻松生成PPT的AI工具吧。 1.笔灵AIPPT 连接直达&#xff1a;​​​​​​​https://ibiling.cn/ppt-zone 这个工具我最早是…

Nature Medicine:基于图像的深度学习和语言模型用于原发性糖尿病护理

首个糖尿病诊疗多模态大模型DeepDR-LLM已成功发表在Nature子刊。 这是全球首个面向糖尿病诊疗的视觉-大语言模型集成系统&#xff0c;结合了语言模型和基于眼底图像的深度学习技术。该系统旨在为基层医生提供个性化的糖尿病管理建议和辅助诊断结果&#xff0c;特别对中低收入国…

【实现100个unity特效之12】Unity中的冲击波 ——如何使用ShaderGraph制作一个冲击波着色器

最终效果 文章目录 最终效果新增LitShaderGraph圆环扭曲效果优化冲击波效果屏幕全屏冲击波圆形冲击波最终连线图代码控制补充源码完结 新增LitShaderGraph 圆环扭曲效果 让我们从一个UV节点开始 创建一个Vector2变量RingSpawnPosition表示冲击波生成位置,在X和Y上将其默认值…

PyTorch基于深度神经网络的语音情绪识别

【图书推荐】《PyTorch语音识别实战》-CSDN博客 《PyTorch语音识别实战&#xff08;人工智能技术丛书&#xff09;》(王晓华)【摘要 书评 试读】- 京东图书 (jd.com) 情绪数据的获取与标签的说明 首先是语音情绪数据集的下载&#xff0c;在这里使用瑞尔森情感语音和歌曲视听数…

sourcemap使用

sourcemap是什么以及怎么生成就不过多阐述了&#xff0c;这是之前看到的一篇文章感觉介绍的很详细&#xff1a;弄懂 SourceMap&#xff0c;前端开发提效 100% 浏览器加载sourcemap 我们线上代码一般不会开启sourcemap&#xff0c;在排查线上的问题时&#xff0c;可以通过浏览器…

DataX PostgreSQL 读写支持Geometry类型

这里写目录标题 简要说明依赖代码 简要说明 通过简单修改源码中关于相关的reader、writer和DBUtil工具类&#xff0c;实现表到表之间的Geometry字段类型数据的输送&#xff0c;目前修改仅测试过在postgresql的postgis插件下的Geometry类型可行。 依赖 1.通过gitclone 或者 到…

用户规模NO.1之后,钉钉还有多大的成长空间?

近日&#xff0c;第三方数据机构QuestMobile发布的《2024半年度中国移动互联网实力价值榜》显示&#xff0c;钉钉与微信、淘宝、抖音等一同入榜 “TOP50赛道用户规模NO.1 App”&#xff0c;蝉联效率办公赛道榜首。 可以看出&#xff0c;现阶段钉钉打开了较大的市场空间&#x…

Qt 跨平台APP单实例运行实现

一.调用方法 支持coreApplication和简单的application两种继承&#xff1a; 二.源码地址&#xff1a; SingleApp: Qt 单实例实现

android13 串口编号修改 串口名修改

总纲 android13 rom 开发总纲说明 目录 1.前言 2.技术分析 别名定义的语法规则 3.修改示例 使用别名 注意事项 4.不生效分析 5.编译查看 6.其他方法 7.彩蛋 1.前言 更改Android设备的串口编号涉及对系统深层次的配置进行修改,通常是为了解决硬件兼容性问题或满足特…

选择文件鼠标右键自定义菜单

注册表路径 计算机\HKEY_CLASSES_ROOT\*\shell 效果 操作 1.定位 winr&#xff0c;输入regedit, 地址栏输入以下路径&#xff0c;并回车。 计算机\HKEY_CLASSES_ROOT\*\shell 2.在shell上右键&#xff0c;新建项 3右键新建字符串值&#xff0c;Icon,Position 4 右键新建c…

LabVIEW压电陶瓷阻抗测试系统

开发了一种基于LabVIEW软件与PXI模块化仪器的压电陶瓷阻抗测试系统。该系统能在高电压工作条件下测量压电陶瓷的阻抗特性&#xff0c;包括阻抗模值与阻抗角的频率特性&#xff0c;为压电陶瓷的进一步分析与应用提供了重要参考。 项目背景 现有的阻抗测试仪大多只能在低电压条件…

【多模态】Flamingo: a Visual Language Model for Few-Shot Learning

链接&#xff1a;https://arxiv.org/pdf/2204.14198 论文&#xff1a;Flamingo: a Visual Language Model for Few-Shot Learning Introduction Motivation&#xff1a;仅使用少量标注样本来快速适应新任务的建模方式是多模态机器学习研究的一个挑战与难点定位&#xff1a;a …

案例分享-国外UI设计界面赏析

国外UI设计倾向于简洁的布局和清晰的排版&#xff0c;减少视觉干扰&#xff0c;提升用户体验。通过合理的色彩搭配和图标设计&#xff0c;营造舒适愉悦的使用氛围。 设计师不拘泥于传统框架&#xff0c;勇于尝试新元素和理念&#xff0c;使界面独特有趣。同时&#xff0c;强调以…

指纹失效,忘记iPhone屏幕解锁密码怎么应对?

为保证手机的安全及隐私&#xff0c;我们会给手机设置屏幕锁屏密码&#xff0c;通过输入设置密码来解锁手机屏幕锁&#xff0c;但为了给大家提供快速便捷的解锁方式&#xff0c;苹果公司提供了指纹解锁&#xff0c;不仅解锁更便捷了还极大地增强了设备的安全性。但有时我们手指…