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中,哪个元素是第二大元素?
分析:
按照题意,使用map、pair或结构体对元素进行排序即可。
代码:
#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 k≤x都可以满足题条件,而对于每一个 k ≥ x k\ge x k≥x都不能满足题目条件,满足单调性。
代码:
#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,…,N−1,高桥在第 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} dpi−1,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=1∑N−1j=i+1∑N(Ai⊕Ai+1⊕…⊕Aj)
分析:
看到异或我们考虑拆位计算答案。设当前枚举到第 k k k位,这一位有 i i i个0, j j j个1,因为异或为 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(思维) 题意: 给你一个介于 1583 1583 1583和 2023 2023 2023之间的整数 Y Y Y。 求公历 Y Y Y年的天数。 在给定的范围内, Y Y Y年的天数如下: 如果 Y Y Y不是 4 4 4的倍数,则为 365 365 …...
多机部署, 负载均衡-LoadBalance
目录 1.负载均衡介绍 1.1问题描述 1.2什么是负载均衡 1.3负载均衡的一些实现 服务端负载均衡 客户端负载均衡 2.Spring Cloud LoadBalancer 2.1快速上手实现负载均衡 2.2负载均衡策略 自定义负载均衡策略 3.服务部署(Linux) 3.1服务构建打包…...
(回溯) LeetCode 78. 子集
原题链接 一. 题目描述 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的 子集 (幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1: 输入:nums [1,2,3] 输出&…...
DQL数据查询语言(多表处理)—/—<7>
一、多表处理 当前有两个表,一个是学生表student,一个是分数表score student表字段名表示如下(共1000条数据): score表字段表示如下(共6000条数据): 1、求每个学生的总分 SELECT …...
力扣刷题总结
去年有段时间一直在刷题,进步神速,解决了以往刷完就忘的问题,这里总结下经验,给有需要的人参考下,核心观点就仨: 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(Field-Oriented Control)3.1 引入坐标系3.2 Clarke and Park变换Clarke 变换(…...
解决 IntelliJ IDEA 编译错误 “Groovyc: Internal groovyc error: code 1” 及 JVM 内存配置问题
在使用 IntelliJ IDEA 进行开发时,我们可能会遇到各种编译和运行错误,其中之一就是 Groovy 编译器错误(Groovyc: Internal groovyc error: code 1)或 JVM 内存不足错误。这类错误可能会影响开发效率,但通过调整 JVM 内…...
LeetCode.2940.找到Alice和Bob可以相遇的建筑
友情提示:这个方法并没有通过案例,只通过了944个案例(很难受),超时了,但是想着还是分享出来吧 题目描述: 给你一个下标从 0 开始的正整数数组 heights ,其中 heights[i] 表示第 i …...
OFD板式文件创建JAVA工具-EASYOFD 四、文字 Text
JAVA版本的OFD板式文件创建工具easyofd. 功能包含了图像、 图像、 文字、和模版页功能。同时也支持OFD文件的数字签名及验签,电子签章及验签。 本JAVA版本的easyofd使用原生方式创建板式文件,不依赖JAVA的SWT库。 项目地址:http://…...
【概念速通】李群 lie group
李群 lie group 概念速通 快速示例介绍:【引入】单位复数 (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 定义࿱…...
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冯诺依曼机的结构特点: 图示: 1.五大部分由运算器(ALU),控制器(CU),存储器(主存辅存),输入设备,输出设备五大部分组成2.指…...
java语言特点
Java语言是一种广泛使用的编程语言,它具有以下几个显著的特点: 面向对象:Java是一种纯面向对象的语言,它支持类的封装、继承和多态等特性。面向对象的设计使得Java程序更加模块化,易于维护和扩展。 平台无关性…...
单元测试注解:@ContextConfiguration
ContextConfiguration注解 ContextConfiguration注解主要用于在Spring框架中加载和配置Spring上下文,特别是在测试场景中。 它允许开发者指定要加载的配置文件或配置类的位置,以便在运行时或测试时能够正确地构建和初始化Spring上下文。 基本用途和工…...
大数据-72 Kafka 高级特性 稳定性-事务 (概念多枯燥) 定义、概览、组、协调器、流程、中止、失败
点一下关注吧!!!非常感谢!!持续更新!!! 目前已经更新到了: Hadoop(已更完)HDFS(已更完)MapReduce(已更完&am…...
MySQl 中对数据表的增删改查(基础)
MySQl 中对数据表的增删改查(基础) 新增演示插入一条数据插入多条数据 查询全列查询部分列查询查询关于列名的表达式查询时用别名查询去重后的结果查询排序后的结果条件查询比较运算符和逻辑运算符 分页查询 修改删除 黑白图是在命令行里的,彩…...
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版本:ubuntu24.04 主题下载地址:https://github.com/vinceliuice/WhiteSur-gtk-theme 参考的安装教程:https://blog.51cto.com/u_…...
计算机毕业设计选题推荐-办公用品管理系统-Java/Python项目实战
✨作者主页:IT毕设梦工厂✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…...
计算机毕业设计选题推荐-网上考试系统-Java/Python项目实战
✨作者主页:IT毕设梦工厂✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
