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

Codeforces Round 924(Div.2) A~E

A.Rectangle Cutting (模拟)

题意:

给出一个长方形,通过平行于原始矩形的一条边进行切割,将该矩形切割成两个边长为整数的矩形。询问是否能通过旋转和移动这两个矩形,得到新的矩形。

分析:

可以发现拼成的新长方形一定是原长方形的一条边减半,一条边翻倍,只要判断平分切开再拼接不会是正方形即可。

代码:

#include <bits/stdc++.h>using namespace std;void solve() {int n, m;cin >> n >> m;if ((n % 2 == 0 && n / 2 != m) || (m % 2 == 0 && m / 2 != n))cout << "Yes" << endl;elsecout << "No" << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

B.Equalize (双指针)

题意:

给出一个长度为 n n n的数组 a a a,将一个排列加到 a a a数组上之后,统计所有数字的出现次数,问怎样添加排列可以使得所有数字出现的次数中的最大值尽可能大。输出这个最大值。

分析:

元素之间差值小于 n n n可以通过加上一个排列变成相同的值,将题目转化成有多少不同元素满足它们之间的差值都小于 n n n。利用双指针快速计算。

代码:

#include <bits/stdc++.h>using namespace std;
set<int> s;
vector<int> a;void solve() {int n;cin >> n;s.clear();a.clear();for (int i = 0; i < n; i++) {int x;cin >> x;s.insert(x);}for (auto tmp: s)a.push_back(tmp);int maxval = 1, ans = 1, pos = 0;for (int i = 1; i < a.size(); i++) {if (a[i] - a[pos] >= n) {maxval = max(maxval, ans);while (pos < i && a[i] - a[pos] >= n)pos++;ans = i - pos + 1;} elseans++;}maxval = max(maxval, ans);cout << maxval << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

C. Physical Education Lesson (思维)

题意:

定义一个数组 a a a a 1 = 1 , a 2 = 2 … a k = k , a k + 1 = k − 1 , a k + 2 = k − 2 , … , a 2 k − 2 = 2 a_1 = 1,a_2 = 2 \dots a_k = k,a_{k + 1} = k - 1, a_{k + 2} = k - 2, \dots ,a_{2k - 2}=2 a1=1,a2=2ak=k,ak+1=k1,ak+2=k2,,a2k2=2,以 2 k − 2 2k - 2 2k2为一组重复。给定 n , x n, x n,x,询问使得 a [ n ] = x a[n] = x a[n]=x k k k有多少个。

分析:

n n n只有两种情况,在递增的序列上和递减的序列上,如果是递增序列那么 n − x n-x nx 2 × k − 2 2\times k-2 2×k2的倍数,如果是递减序列,那么 n + x − 2 n + x - 2 n+x2 2 × k − 2 2 \times k-2 2×k2的倍数,求出所有可能的 k k k,判断第 n n n个数是否为 x x x即可。

代码:

#include <bits/stdc++.h>using namespace std;void solve() {int n, x;cin >> n >> x;int l = n + x - 2;int r = n - x;set<int> s;for (int i = 1; i <= l / i; i++)if (l % i == 0) {if (i % 2 == 0 && (i + 2) / 2 >= x)s.insert(i);if ((l / i) % 2 == 0 && (l / i + 2) / 2 >= x)s.insert(l / i);}for (int i = 1; i <= r / i; i++)if (r % i == 0) {if (i % 2 == 0 && (i + 2) / 2 >= x)s.insert(i);if ((r / i) % 2 == 0 && (r / i + 2) / 2 >= x)s.insert(r / i);}cout << s.size() << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

D.Lonely Mountain Dungeons (思维)

题意:

n n n个种族,每个种族数量为 c i c_i ci。现在要组建军队,每对处于不同小队的同一种族的生物,都会为军队的总兵力增加 b b b个单位,然而小队越多,越不好管理, k k k个小队组成的军队总兵力会减少 ( k − 1 ) × x (k-1) \times x (k1)×x。询问怎样组建军队能使得总兵力最大。

分析:

假设当前有 k k k队,某个种族有 x x x人,当 x ≤ k x \le k xk时,战力会增加 C ( x , 2 ) C(x,2) C(x,2),当 x > k x > k x>k时,会存在同一种族的人在相同的队伍中,假设有 y y y人,那么需要减去 C ( y , 2 ) C(y,2) C(y,2)。考虑到种族数量加起来为 2 e 5 2e5 2e5,所以考虑暴力枚举 k k k

代码:

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const int MAXN = 2e5 + 5;
vector<LL> num(MAXN, 0);void solve() {LL n, b, x;cin >> n >> b >> x;num.clear();map<LL, LL> map1;LL maxval = 0;for (int i = 0; i < n; i++) {cin >> num[i];maxval = max(maxval, num[i]);map1[num[i]]++;}LL ans = 0;for (int i = maxval; i >= 1; i--) {LL sum = 0;for (auto tmp: map1) {LL x = tmp.first / i;LL cnt = tmp.first % i;sum += (tmp.first * (tmp.first - 1) / 2 - (cnt * (x + 1) * x / 2 + (i - cnt) * x * (x - 1) / 2)) *tmp.second;}LL tmp1 = b * sum;tmp1 -= (i - 1) * x;ans = max(ans, tmp1);}cout << ans << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

E.Modular Sequence (dp)

题意:

给出两个整数 x , y x,y x,y,询问是否存在一个序列 a a a,满足 a 1 = x a_1=x a1=x a i = a i − 1 + y a_i=a_{i-1}+y ai=ai1+y或者 a i = a i − 1 % y a_i=a_{i-1} \%y ai=ai1%y。再给定 n n n s s s,询问序列 a a a的前 n n n项和是否等于 s s s

分析:

可以发现序列 a a a中所有数的余数都是一个固定的数字, s s s先减去这个余数,如果 s s s是合法的,那么 s s s一定是 y y y的倍数,将 s / = y s/=y s/=y将问题转化成 a 1 = x / y , a i = a i − 1 + 1 a_1=x/y,a_i=a_{i-1}+1 a1=x/y,ai=ai1+1或者 a i = 0 a_i=0 ai=0。设 d p [ i ] dp[i] dp[i]表示总和为 i i i,需要的最短长度。 d p dp dp可以用完全背包进行预处理。由于 a 1 a_1 a1不一定为 0 0 0,所以需要枚举 a 1 a_1 a1往后加了多少位的 1 1 1。再用 d p dp dp判断是否有解。

代码:

#include <bits/stdc++.h>using namespace std;
const int MAXN = 2e5 + 5;
vector<int> dp(MAXN + 1, 1e9);void init() {dp[0] = 0;for (int i = 1;; i++) {int t = i * (i + 1) / 2;if (t > MAXN)break;for (int j = t; j <= MAXN; j++) {dp[j] = min(dp[j], dp[j - t] + i + 1);}}
}void solve() {int n, x, y, s;cin >> n >> x >> y >> s;int r = x % y;if (1LL * r * n > s) {cout << "NO" << endl;return;}s -= r * n;if (s % y != 0) {cout << "NO" << endl;return;}s /= y;vector<int> a(n + 1);a[1] = x / y;int pos = -1;int sum = a[1], k = a[1];for (int i = 1; i <= n && sum <= s; i++) {if (dp[s - sum] <= n - i) {pos = i;break;}k += 1;sum += k;}if (pos == -1) {cout << "NO" << endl;return;}for (int i = 2; i <= pos; i++) {a[i] = a[i - 1] + 1;}s -= sum;int minval = dp[s];for (int i = 1; s > 0; i++) {int t = i * (i + 1) / 2;while (s > 0 && dp[s - t] + i + 1 == minval) {s -= t;minval -= i + 1;for (int j = 0; j <= i; j++) {pos++;a[pos] = j;}}}cout << "YES" << endl;for (int i = 1; i <= n; i++) {cout << a[i] * y + r << " ";}cout << endl;
}int main() {init();int t;cin >> t;while (t--) {solve();}return 0;
}

赛后交流

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

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

相关文章:

Codeforces Round 924(Div.2) A~E

A.Rectangle Cutting (模拟) 题意&#xff1a; 给出一个长方形&#xff0c;通过平行于原始矩形的一条边进行切割&#xff0c;将该矩形切割成两个边长为整数的矩形。询问是否能通过旋转和移动这两个矩形&#xff0c;得到新的矩形。 分析&#xff1a; 可以发现拼成的新长方形…...

django中实现观察者模式

在Django中实现观察者模式&#xff0c;你可以利用Django的信号&#xff08;Signals&#xff09;系统。Django的信号提供了一种发布/订阅模型&#xff0c;允许解耦应用程序组件之间的交互。一个组件可以发送一个信号&#xff0c;而其他组件可以监听这个信号并响应它。 下面是如…...

Elasticsearch中的动态DSL解决方案

目录 问题背景 解决方案 编写es的mapper 动态dsl编写 使用mapper获取动态dsl 远程调用restful api查询 问题背景 在大数据量的业务系统中&#xff0c;一般都会引入Elasticsearch来作为搜索引擎&#xff0c;而搜索的条件又是多种多样的。回顾下&#xff0c;如果是mysql等…...

【操作系统】MacOS虚拟内存统计指标

目录 命令及其结果 参数解读 有趣的实验 在 macOS 系统中&#xff0c;虚拟内存统计指标提供了对系统内存使用情况和虚拟内存操作的重要洞察。通过分析这些指标&#xff0c;我们可以更好地了解系统的性能状况和内存管理情况。 命令及其结果 >>> vm_stat Mach Virtu…...

LeetCode:67.二进制求和

67. 二进制求和 - 力扣&#xff08;LeetCode&#xff09; 又是一道求和题&#xff0c;% / 在求和的用途了解了些&#xff0c; 目录 题目&#xff1a; 思路分析&#xff1a; 博主代码: 官方代码&#xff1a; 每日表情包&#xff1a; 题目&#xff1a; 思路分析&#xf…...

修改GI文件的权限

参考文档&#xff1a; How to check and fix file permissions on Grid Infrastructure environment (Doc ID 1931142.1) -- 验证二进制文件的权限 [gridnode19c01 ~]$ cluvfy comp software -n node19c01 -verbosePerforming following verification checks ...Software …...

OJ刷题:杨氏矩阵【建议收藏】

看见这个题目&#xff0c;很多人的第一反应是遍历整个数组查找数字&#xff0c;但是这种方法不仅效率低&#xff0c;而且远远不能满足题目要求。下面介绍一种高效的查找方法&#xff1a; 代码实现&#xff1a; #include <stdio.h>int Yang_Find_Num(int arr[][3], int …...

2024-02-13 Unity 编辑器开发之编辑器拓展4 —— EditorGUIUtility

文章目录 1 EditorGUIUtility 介绍2 加载资源2.1 Eidtor Default Resources2.2 不存在返回 null2.3 不存在则报错2.4 代码示例 3 搜索框查询、对象选中提示3.1 ShowObjectPicker3.2 PingObject3.3 代码示例 4 窗口事件传递、坐标转换4.1 CommandEvent4.2 GUIPoint 和 ScreenPoi…...

redis加锁实现方式

思考 是否有官方推荐&#xff08;自己先思考如何实现&#xff0c;然后再参考其他人的实践&#xff0c;总结优缺点&#xff09;通过哪些方式可以实现锁锁是否具有原子性锁请求失败了如何处理如果避免发生死锁如果避免发生资源抢占如果避免锁的误删 官方实现策略 安全性能&#…...

ClickHouse--08--SQL DDL 操作

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 SQL DDL 操作1 创建库2 查看数据库3 删除库4 创建表5 查看表6 查看表的定义7 查看表的字段8 删除表9 修改表9.1 添加列9.2 删除列9.3 清空列9.4 给列修改注释9.5 修…...

5种风格非常经典的免费wordpress主题

免费wordpress主题下载 高端大气上档次的wordpress主题&#xff0c;也可以是免费的&#xff0c;可以在线免费下载。 https://www.wpniu.com/themes/288.html wordpress免费主题 高端大气的wordpress免费主题&#xff0c;LOGO在顶部左侧&#xff0c;导航菜单在顶部右侧。 ht…...

「数据结构」哈希表2:实现哈希表

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;Java数据结构 &#x1f387;欢迎点赞收藏加关注哦&#xff01; 实现哈希表 &#x1f349;扩容&#x1f349;插入&#x1f349;获取value&#x1f349;源码 &#x1f349;扩容 在讲插入之前需要…...

ITK 图像分割(一):阈值ThresholdImageFilter

效果&#xff1a; Video: 区域增加分割 1、itkThresholdImageFilter 该类的主要功能是通过设置低阈值、高阈值或介于高低阈值之间&#xff0c;则将图像值输出为用户指定的值。 如果图像值低于、高于或介于设置的阈值之间&#xff0c;该类就将图像值设置为用户指定的“外部”值…...

2023.2.6

#include<stdio.h> #include<string.h> //冒泡排序 void bubb(int arr[],int len) {for(int i1;i<len;i){for(int j0;j<len-i1;j){if(arr[j1]<arr[j]){int tarr[j];arr[j]arr[j1];arr[j1]t;}}} } //select排序 void select(int arr[],int len) {int min0;…...

例39:使用List控件

建立一个EXE工程&#xff0c;在窗体上放一个文本框&#xff0c;一个列表框和三个按钮输入如下的代码&#xff1a; Sub Form1_Command1_BN_Clicked(hWndForm As hWnd, hWndControl As hWnd)List1.AddItem(Text1.Text)End SubSub Form1_Command2_BN_Clicked(hWndForm As hWnd, h…...

浏览器内核的主要功能模块介绍

浏览器内核是浏览器的核心部分&#xff0c;负责解析网页内容、渲染页面和处理用户交互。一个典型的浏览器内核主要包括以下几个功能模块&#xff1a; 1. **解析器&#xff08;Parser&#xff09;**&#xff1a; 解析器负责解析网页内容&#xff0c;包括HTML…...

如何流畅进入Github

前言 以下软件是免费的&#xff0c;放心用 一、进入右边的下载链接https://steampp.net/ 二、点击下载 三、点击接受并下载 四、随便选一个下载链接进行下载 五、软件安装好打开后&#xff0c;找到Github 六、点击全部启用 七、再点击左上角的一键加速 八、这个时候你再进Git…...

docker磁盘不足!已解决~

目录 &#x1f35f;1.查看docker镜像目录 &#x1f9c2;2.停止docker服务 &#x1f953;3.创建新的目录 &#x1f32d;4.迁移目录 &#x1f37f;5.编辑迁移的目录 &#x1f95e;6.重新加载docker &#x1f354;7.检擦docker新目录 &#x1f373;8.删掉旧目录 1.查看doc…...

法国实习面试——计算机相关专业词汇

法语 1.Spcialit - 专业 2.Systme - 系统 3.Embarqus - 嵌入式 4.Logicielle - 软件 5.Distribus - 分布式 6.lectronique - 电子 7.nergie lectrique - 电能 8.Automatisation - 自动化 9.Une exprience de stage - 实习经验 10.Automobiles - 汽车 11.tre charg…...

LeetCode刷题计划

LeetCode刷题计划 推荐 代码随想录&#xff1a;https://github.com/youngyangyang04/leetcode-master 卡码网 练习ACM模式 https://kamacoder.com/ 01 #include <iostream> using namespace std;int main() {int a ,b;while(cin>>a>>b){cout<<ab<…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...