当前位置: 首页 > news >正文

AtCoder Beginner Contest 365 A~E

A.Leap Year(思维)

题意:

给你一个介于 1583 1583 1583 2023 2023 2023之间的整数 Y Y Y

求公历 Y Y Y年的天数。

在给定的范围内, Y Y Y年的天数如下:

  • 如果 Y Y Y不是 4 4 4的倍数,则为 365 365 365天;
  • 如果 Y Y Y 4 4 4的倍数,但不是 100 100 100的倍数,则为 366 366 366天;
  • 如果 Y Y Y 100 100 100的倍数,但不是 400 400 400的倍数,则为 365 365 365天;
  • 如果 Y Y Y 400 400 400的倍数,则为 366 366 366天。

分析:

判断年份是否为闰年。

  • 如果 n n n不能被 4 4 4整除,那么不是闰年。
  • 如果 n n n可以被 400 400 400整除,那么是闰年。
  • 如果 n n n不可以被 100 100 100整除但是可以被 4 4 4整除,那么是闰年。

否则就不是闰年。使用if-else语句判断即可。

代码:

#include<bits/stdc++.h>using namespace std;int main() {int n;cin >> n;if (n % 4 != 0) {cout << 365 << endl;} else if (n % 400 == 0) {cout << 366 << endl;} else if ((n % 100 != 0) && n % 4 == 0) {cout << 366 << endl;} else {cout << 365 << endl;}return 0;
}

B.Second Best(模拟)

题意:

给你一个长度为 N N N的整数序列 A = ( A 1 , … , A N ) A=(A_1,\ldots,A_N) A=(A1,,AN)。这里的 A 1 , A 2 , … , A N A_1,A_2,\ldots,A_N A1,A2,,AN都是不同的。

A A A中,哪个元素是第二大元素?

分析:

按照题意,使用mappair或结构体对元素进行排序即可。

代码:

#include<bits/stdc++.h>using namespace std;
const int N = 1000100;struct s {int x, id;bool operator<(const s &r) const {return x > r.x;}
} a[N];int main() {int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i].x;a[i].id = i;}sort(a + 1, a + n + 1);cout << a[2].id << endl;return 0;
}

C.Transportation Expenses(二分答案)

题意:

N N N人参加一项活动,第 i i i个人的交通费用是 A i A_i Ai日元。

活动组织者高桥决定设定交通补贴的最高限额为 x x x。第 i i i个人的补贴为 min ⁡ ( x , A i ) \min(x,A_i) min(x,Ai)日元。这里, x x x必须是一个非负整数。

高桥的预算为 M M M日元,他希望所有 N N N人的交通补贴总额最多为 M M M日元,那么补贴限额 x x x的最大可能值是多少?

如果补贴限额可以无限大,输出infinite

分析:

本题我们分情况讨论,首先考虑答案为无限大的情况。对于这种情况可以先计算序列的总和和 M M M比较,如果这个都小于等于 M M M,那么肯定答案是无穷大。

对于不是无穷大的情况,考虑尝试枚举一个 x x x,然后对于每一个 x x x判断是否满足题目条件,然后记录最大的 x x x,时间复杂度 O ( N M ) O(NM) O(NM)

x x x的枚举我们采用二分,然后来判断,题目要求 x x x的最大值,可以发现若此时的 x x x为最大,那么对于每一个 k ≤ x k\le x kx都可以满足题条件,而对于每一个 k ≥ x k\ge x kx都不能满足题目条件,满足单调性。

代码:

#include<bits/stdc++.h>typedef long long LL;
using namespace std;
const int N = 200005;
LL n, m, a[N], ans = -1e17;bool check(LL x) {LL res = 0;for (int i = 1; i <= n; i++)res += min(a[i], x);return (res <= m);
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];if (check(1e17)) {cout << "infinite" << endl;return 0;}LL l = 0, r = m;while (l <= r) {LL mid = (l + r) >> 1;if (check(mid)) {ans = mid;l = mid + 1;} elser = mid - 1;}cout << ans << endl;return 0;
}

D.AtCoder Janken 3(动态规划)

题意:

高桥和青木玩了 N N N次剪刀石头布。注:在这个游戏中,石头赢剪刀,剪刀赢布,布赢石头。

青木的动作由长度为 N N N的字符串 S S S表示,字符串由"R"、"P"和"S"组成。 S S S中的第 i i i个字符表示青木在第 i i i个对局中的出招:“R"表示"石头”,“P"表示"布”,“S"表示"剪刀”。

高桥的出招满足以下条件:

  • 高桥从未输给过青木。
  • 对于 i = 1 , 2 , … , N − 1 i=1,2,\ldots,N-1 i=1,2,,N1,高桥在第 i i i场对局中的出招与他在第 ( i + 1 ) (i+1) (i+1)场对局中的出招不同。

确定高桥可能赢得的最大对局数。

可以保证存在一个满足上述条件的高桥出招顺序。

分析:

因为相邻两场对局出招不同,发现之前的对局存在后效性,考虑动态规划。

d p i , [ 0 / 1 / 2 ] dp_{i,[0/1/2]} dpi,[0/1/2]表示当前为第i场对局,当前出的拳是 R , P , S R,P,S R,P,S,最多可以赢多少局。

特殊计算一下 d p 1 , [ 0 / 1 / 2 ] dp_{1,[0/1/2]} dp1,[0/1/2] d p i , j dp_{i,j} dpi,j的值可以通过 d p i − 1 , k dp_{i-1,k} dpi1,k转移来当且仅当 k ≠ j k\neq j k=j,对于会输的出招直接赋值为一个极小值,取一个最大值然后增加对答案的贡献即可。

代码:

#include<bits/stdc++.h>using namespace std;
const int N = 1000100;
const int MIN_INF = -2e9;
int n;
int dp[N][3];int main() {cin >> n;string s;cin >> s;s = ' ' + s;if (s[1] == 'R') {dp[1][0] = 0;dp[1][1] = 1;dp[1][2] = MIN_INF;} else if (s[1] == 'P') {dp[1][0] = MIN_INF;dp[1][1] = 0;dp[1][2] = 1;} else {dp[1][0] = 1;dp[1][1] = MIN_INF;dp[1][2] = 0;}for (int i = 2; i <= n; ++i) {if (s[i] == 'R') {dp[i][0] = max({dp[i - 1][1], dp[i - 1][2]});dp[i][1] = max({dp[i - 1][0], dp[i - 1][2]}) + 1;dp[i][2] = MIN_INF;} else if (s[i] == 'P') {dp[i][0] = MIN_INF;dp[i][1] = max({dp[i - 1][0], dp[i - 1][2]});dp[i][2] = max({dp[i - 1][0], dp[i - 1][1]}) + 1;} else {dp[i][0] = max({dp[i - 1][1], dp[i - 1][2]}) + 1;dp[i][1] = MIN_INF;dp[i][2] = max({dp[i - 1][0], dp[i - 1][1]});}}cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;return 0;
}

E.Xor Sigma Problem(数学)

题意:

给你一个长度为 N N N的整数序列 A = ( A 1 , … , A N ) A=(A_1,\ldots,A_N) A=(A1,,AN)。求以下表达式的值:

∑ i = 1 N − 1 ∑ j = i + 1 N ( A i ⊕ A i + 1 ⊕ … ⊕ A j ) \displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N(A_i\oplus A_{i+1}\oplus\ldots\oplus A_j) i=1N1j=i+1N(AiAi+1Aj)

分析:

看到异或我们考虑拆位计算答案。设当前枚举到第 k k k位,这一位有 i i i0 j j j1,因为异或为 1 1 1要求两个异或的数互不相同,所以这一位对答案的贡献即为 i × j × 2 k i\times j\times 2^k i×j×2k

将所有位对答案的贡献累加即可。

代码:

#include<bits/stdc++.h>typedef long long LL;
using namespace std;
const int N = 200001;
LL a[N], s[N];int main() {LL n;cin >> n;for (LL i = 1; i <= n; ++i) {cin >> a[i];s[i] = a[i];a[i] ^= a[i - 1];}LL res = 0;for (LL k = 0; k < 30; ++k) {LL cnt = 0;for (LL j = 0; j <= n; ++j)cnt += a[j] >> k & 1;res += cnt * (n - cnt + 1) * (1LL << k);}for (LL i = 1; i <= n; ++i)res -= s[i];cout << res << endl;return 0;
}

赛后交流

在比赛结束后,会在交流群中给出比赛题解,同学们可以在赛后查看题解进行补题。

群号: 704572101,赛后大家可以一起交流做题思路,分享做题技巧,欢迎大家的加入。

相关文章:

AtCoder Beginner Contest 365 A~E

A.Leap Year&#xff08;思维&#xff09; 题意&#xff1a; 给你一个介于 1583 1583 1583和 2023 2023 2023之间的整数 Y Y Y。 求公历 Y Y Y年的天数。 在给定的范围内&#xff0c; Y Y Y年的天数如下&#xff1a; 如果 Y Y Y不是 4 4 4的倍数&#xff0c;则为 365 365 …...

多机部署, 负载均衡-LoadBalance

目录 1.负载均衡介绍 1.1问题描述 1.2什么是负载均衡 1.3负载均衡的一些实现 服务端负载均衡 客户端负载均衡 2.Spring Cloud LoadBalancer 2.1快速上手实现负载均衡 2.2负载均衡策略 自定义负载均衡策略 3.服务部署&#xff08;Linux&#xff09; 3.1服务构建打包…...

(回溯) LeetCode 78. 子集

原题链接 一. 题目描述 给你一个整数数组 nums &#xff0c;数组中的元素 互不相同 。返回该数组所有可能的 子集 &#xff08;幂集&#xff09;。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&…...

DQL数据查询语言(多表处理)—/—<7>

一、多表处理 当前有两个表&#xff0c;一个是学生表student&#xff0c;一个是分数表score student表字段名表示如下&#xff08;共1000条数据&#xff09;&#xff1a; score表字段表示如下&#xff08;共6000条数据&#xff09;&#xff1a; 1、求每个学生的总分 SELECT …...

力扣刷题总结

去年有段时间一直在刷题&#xff0c;进步神速&#xff0c;解决了以往刷完就忘的问题&#xff0c;这里总结下经验&#xff0c;给有需要的人参考下&#xff0c;核心观点就仨&#xff1a; 1. 打好数据结构与算法基础 2. 多刷题多练习 3. 形成自己的知识体系 下图是我梳理的知识体…...

BLDC ESC 无刷直流电子调速器驱动方式

BLDC ESC 无刷直流电子调速器驱动方式 1. 源由2. 驱动方法2.1 Trapezoidal 1202.2 Trapezoidal 1502.3 Sinusoidal 1802.4 Field-Orientated Control (FOC) 3. FOC&#xff08;Field-Oriented Control&#xff09;3.1 引入坐标系3.2 Clarke and Park变换Clarke 变换&#xff08…...

解决 IntelliJ IDEA 编译错误 “Groovyc: Internal groovyc error: code 1” 及 JVM 内存配置问题

在使用 IntelliJ IDEA 进行开发时&#xff0c;我们可能会遇到各种编译和运行错误&#xff0c;其中之一就是 Groovy 编译器错误&#xff08;Groovyc: Internal groovyc error: code 1&#xff09;或 JVM 内存不足错误。这类错误可能会影响开发效率&#xff0c;但通过调整 JVM 内…...

LeetCode.2940.找到Alice和Bob可以相遇的建筑

友情提示&#xff1a;这个方法并没有通过案例&#xff0c;只通过了944个案例&#xff08;很难受&#xff09;&#xff0c;超时了&#xff0c;但是想着还是分享出来吧 题目描述&#xff1a; 给你一个下标从 0 开始的正整数数组 heights &#xff0c;其中 heights[i] 表示第 i …...

OFD板式文件创建JAVA工具-EASYOFD 四、文字 Text

JAVA版本的OFD板式文件创建工具easyofd. 功能包含了图像、 图像、 文字、和模版页功能。同时也支持OFD文件的数字签名及验签&#xff0c;电子签章及验签。 本JAVA版本的easyofd使用原生方式创建板式文件&#xff0c;不依赖JAVA的SWT库。 项目地址&#xff1a;http://…...

【概念速通】李群 lie group

李群 lie group 概念速通 快速示例介绍&#xff1a;【引入】单位复数 (The unit complex numbers) 是李群 (lie group) 最简单的例子之一【进一步】SO(2): The 2D rotation matrices【Typical uses】SE(2): Pose of a robot in the plane Group & Lie Group 定义&#xff1…...

day_39

198. 打家劫舍 class Solution:def rob(self, nums: List[int]) -> int:if len(nums) 1:return nums[0]dp [0] * len(nums)dp[0], dp[1] nums[0], max(nums[0], nums[1])for i in range(2, len(nums)):dp[i] max(dp[i - 1], dp[i - 2] nums[i])return dp[len(nums) - …...

计算机系统层次结构

1.计算机系统的组成 计算机系统的组成硬件系统软件系统 2.计算机的硬件部分 2.1冯诺依曼机的结构特点&#xff1a; 图示&#xff1a; 1.五大部分由运算器(ALU)&#xff0c;控制器(CU)&#xff0c;存储器(主存辅存)&#xff0c;输入设备&#xff0c;输出设备五大部分组成2.指…...

java语言特点

Java语言是一种广泛使用的编程语言&#xff0c;它具有以下几个显著的特点&#xff1a; 面向对象&#xff1a;Java是一种纯面向对象的语言&#xff0c;它支持类的封装、继承和多态等特性。面向对象的设计使得Java程序更加模块化&#xff0c;易于维护和扩展。 平台无关性&#xf…...

单元测试注解:@ContextConfiguration

ContextConfiguration注解 ContextConfiguration注解主要用于在‌Spring框架中加载和配置Spring上下文&#xff0c;特别是在测试场景中。 它允许开发者指定要加载的配置文件或配置类的位置&#xff0c;以便在运行时或测试时能够正确地构建和初始化Spring上下文。 基本用途和工…...

大数据-72 Kafka 高级特性 稳定性-事务 (概念多枯燥) 定义、概览、组、协调器、流程、中止、失败

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…...

MySQl 中对数据表的增删改查(基础)

MySQl 中对数据表的增删改查&#xff08;基础&#xff09; 新增演示插入一条数据插入多条数据 查询全列查询部分列查询查询关于列名的表达式查询时用别名查询去重后的结果查询排序后的结果条件查询比较运算符和逻辑运算符 分页查询 修改删除 黑白图是在命令行里的&#xff0c;彩…...

LVS知识点整理及实践

LVS知识点整理及实践 LVSlvs集群概念lvs概念lvs集群类型lvs-nat模型数据逻辑: lvs-DR模式数据传输和过程:特点: lvs-tun模式数据传输过程:特点: lvs-fullnet模式数据传输过程 lvs调度算法lvs调度算法类型lvs静态调度算法lvs动态调度算法4.15版本内核以后新增调度算法 ipvsadm命…...

Ubuntu gnome WhiteSur-gtk-theme类mac主题正确安装和卸载方式

目录 摘要目的安装和卸载特别说明 Ubuntu gnome WhiteSur-gtk-theme类mac主题正确安装和卸载方式 摘要 Ubuntu版本&#xff1a;ubuntu24.04 主题下载地址&#xff1a;https://github.com/vinceliuice/WhiteSur-gtk-theme 参考的安装教程&#xff1a;https://blog.51cto.com/u_…...

计算机毕业设计选题推荐-办公用品管理系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…...

计算机毕业设计选题推荐-网上考试系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

SpringCloud优势

目录 完善的微服务支持 高可用性和容错性 灵活的配置管理 强大的服务网关 分布式追踪能力 丰富的社区生态 易于与其他技术栈集成 完善的微服务支持 Spring Cloud 提供了一整套工具和组件来支持微服务架构的开发,包括服务注册与发现、负载均衡、断路器、配置管理等功能…...

【自然语言处理】大模型时代的数据标注(主动学习)

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;FreeAL: Towards Human-Free Active Learning in the Era of Large Language Models发表情况&#xff1a;2023-EMNLP作者单位&#xff1a;浙江大…...

FTPS、HTTPS、SMTPS以及WebSockets over TLS的概念及其应用场景

一、什么是FTPS&#xff1f; FTPS&#xff0c;英文全称File Transfer Protocol with support for Transport Layer Security (SSL/TLS)&#xff0c;安全文件传输协议&#xff0c;是一种对常用的文件传输协议(FTP)添加传输层安全(TLS)和安全套接层(SSL)加密协议支持的扩展协议。…...