数学——A. K-divisible Sum + D. Exam in MAC

A. K-divisible Sum

题目:

思路:

以下 “[xxx]” 符号均代表向上取整

我们假设总和是sum,那么就有sum = k * cnt

要想最大值最小,肯定是要让sum尽可能小,这样每个元素都能变小

最小情况是 sum 恰好等于 n 时,此时有 n <= k * cnt

则 cnt 满足 cnt >= [n / k],当其取最小值时,sum有最小

此时既然我们知道sum的最小值了,那我们来探讨一下数组中最大值的最小值应该是多少

显然最小值应该是 [sum / n],所以我们便可写出代码了

代码:

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"void solve()
{int n, k;cin >> n >> k;int cf = (k + n - 1)/ k;cout << (cf * k + n - 1) / n << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D. Exam in MAC

题目:

思路:

这题让我们选出满足题意的(x,y)数对,首先看数据,居然高达1e9,那么显然不能直接暴力枚举

这题要以反向的思路来求,因为满足的很多,但是不满足的很少

那我们先什么都不考虑,我们的数对有多少种选择呢?(无重复)

显然是 (c+1 +1) * (c+1) / 2 种,为什么?

当 x 选 0 时,y 可以选 c + 1种,当 x 选 1 时,y 可以选 c 种,以此类推,最后发现这是一个等差数列,那么直接求和就是以上公式了

接下来我们考虑不符合的

首先考虑 x + y ∈ s

也就是对于任意的 s[i],要使得 x + y = s[i],一共有多少种选择?

其实和上述一样的思路,这里的答案是 s[i] / 2 + 1 种(因为还有0)

接下来考虑 y - x ∈ s

对于 y - x = s[i],也就是 y = s[i] + x,可以看出 y 的取值范围是 s[i] <= y <= c,那么显然,对于范围内任选一个数,都有唯一确定的 x 与其对应,所以这里的答案是 c - s[i] + 1

那么到这就结束了吗?显然没有,因为还有可能这些情况中还有两种情况都符合的情况

那么根据容斥原理,我们只需要求出两种情况都符合的情况,然后减去即可

那么我们来看看如何计算呢,首先有以下式子

x + y = s[i] 且 y - x = s[j],其中 s[i] 可以等于 s[j],那么显然对于这个二元一次方程,我们可以解出对于 s[i] 和 s[j] 这种情况的唯一解,但是要注意,s[i] 与 s[j] 的奇偶性一定要相同,否则解不是整数,所以我们只需要统计 s 中的奇数和偶数就行了,那接下来算一下他们的奉献

对于任意奇偶,其奉献是 even/odd * (even/odd + 1) / 2,这其实和上面一样,自己草稿纸上也能写出来

至此题目分析完毕,还是比较简单的,将复杂变简单

代码:

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"void solve()
{int n, c;cin >> n >> c;vector<int> s(n);for (int i = 0; i < n; i++){cin >> s[i];}int ans = 1LL * (c + 1) * (c + 2) / 2LL;int even = 0, odd = 0;for (int i = 0; i < n; i++){ans -= s[i] / 2LL + 1;ans -= c - s[i] + 1LL;if (s[i] % 2)odd++;elseeven++;}ans += 1LL * even * (even + 1) / 2LL;ans += 1LL * odd * (odd + 1) / 2LL;cout << ans << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

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

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

相关文章

Docker 》》Docker Compose 》》network 网络 compose

docker 默认的网络 三种模式 # 列出所有当前主机上或Swarm集群上的网络 docker network ls#查看网络详情 docker network inspect network名称# 清除未使用的docker网络 docker network prune -f# 创建网络 ocker network create -d bridge 网络名称 docker network create –s…

RabbitMQ延迟消息

文章目录 延迟消息死信交换机延迟消息延迟消息应用场景 延迟消息 生产者在发送消息的时候指定一个时间&#xff0c;消费者不会立即收到该消息&#xff0c;而是在指定时间之后才收到消息&#xff0c;这就是延迟消息。 比如说这么一个场景&#xff0c;用户下单后将商品库存进行…

phpstudy+phpstorm+xdebug【学习笔记】

配置PHPStudy 配置PHPSTORM phpstorm选择PHP版本 配置DEBUG 设置服务器 编辑配置 学习参考链接&#xff1a;&#xff1a;https://blog.csdn.net/m0_60571842/article/details/133246064

58.Harmonyos NEXT 图片预览组件架构设计与实现原理

温馨提示&#xff1a;本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦&#xff01; Harmonyos NEXT 图片预览组件架构设计与实现原理 文章目录 Harmonyos NEXT 图片预览组件架构设计与实现原理效果预览一、组件架构概述1. 核心组件层…

Android 手机启动过程

梳理 为了梳理思路&#xff0c;笔者画了一幅关于 Android 手机启动的过程图片内容纯属个人见解&#xff0c;如有错误&#xff0c;欢迎各位指正

Chat-TTS-UI:文字转语音 - 本地部署方案

Chat-TTS-UI 是一个基于 ChatTTS 模型的本地网页界面,专为满足用户在信息过载时代轻松获取大量文字信息的需求而设计。它支持中英文混合输入、多种音色选择,并提供 API 接口,方便开发者集成到其他应用中。其简洁易用的网页界面、细粒度控制以及 GPU 加速等高级功能,使其广泛…

11. Pandas :操作Excel文件(Excel报表的案例研究)

从一个装有各种 Excel 文件的文件夹开始&#xff0c;这些文件需要被整合到 Excel 报表中。 它们包含了虚构的电信运营商在全美各营业厅的套餐&#xff08;金、银、铜&#xff09;销售情况。每个月有两个文件&#xff0c;子文件夹 new 中的是新用户&#xff0c;子文件夹 existin…

一周学会Flask3 Python Web开发-SQLAlchemy添加数据操作-班级模块

锋哥原创的Flask3 Python Web开发 Flask3视频教程&#xff1a; 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili SQLAlchemy提供session.add()方法添加model实体数据&#xff0c;以及提供session.commit()提交事务。 首先list.html加一个添…

大型语言模型与强化学习的融合:迈向通用人工智能的新范式——基于基础复现的实验平台构建

1. 引言 大型语言模型&#xff08;LLM&#xff09;在自然语言处理领域的突破&#xff0c;展现了强大的知识存储、推理和生成能力&#xff0c;为人工智能带来了新的可能性。强化学习&#xff08;RL&#xff09;作为一种通过与环境交互学习最优策略的方法&#xff0c;在智能体训…

Axure大屏可视化原型模板及素材:数据可视化的高效解决方案

数据可视化已成为企业决策、运营分析、市场洞察的重要工具。数据可视化大屏&#xff0c;作为数据展示和交互的直观平台&#xff0c;能够实时呈现关键数据&#xff0c;帮助企业快速做出决策。Axure作为原型设计领域的领先工具&#xff0c;以其丰富的组件库、强大的交互设计能力和…

图片填充容器,如何描述

【图片需要完全填充/拉伸以适应容器尺寸&#xff0c;不保持原始比例&#xff0c;使用 object-fit: fill 属性实现】 效果&#xff1a; 代码案例&#xff1a; <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8">&l…

缓存和客户端数据存储体系(Ark Data Kit)--- 应用数据持久化(首选项持久化、K-V、关系型数据库)持续更新中...

Core File Kit做怎删改查操作不便&#xff0c;用Ark Data Kit。 功能介绍 ArkData &#xff08;方舟数据管理&#xff09;为开发者提供数据存储、数据管理和数据同步能力&#xff0c;比如联系人应用数据可以保存到数据库中&#xff0c;提供数据库的安全、可靠以及共享访问等管…

RUOYI框架在实际项目中的应用三:Ruoyi微服务版本-RuoYi-Cloud

如需观看Ruoyi框架的整体介绍&#xff0c;请移步&#xff1a;RUOYI框架在实际项目中的应用一&#xff1a;ruoyi简介 一、Ruoyi微服务版本-Ruoyi微服务版本 1、官方资料 1&#xff1a;代码地址&#xff1a;https://gitee.com/y_project/RuoYi-Cloud.git 2&#xff1a;文档介绍…

windbg集成python环境(pykd)

背景: 调试FPU指令过程时&#xff0c;需要一直跟踪FPU Status寄存器TOP字段(ST寄存器对应的BC寄存器)&#xff0c;TOP寄存器位于FPU Status[13:11]&#xff0c;这种转换过程并非一目了然(如下图)&#xff1a; [Disassembly窗口fld指令执行后&#xff0c;Registers窗口中fpsw的…

微信小程序threejs三维开发

微信小程序threejs开发 import * as THREE from three; const { performance, document, window, HTMLCanvasElement, requestAnimationFrame, cancelAnimationFrame, core, Event, Event0 } THREE .DHTML import Stats from three/examples/jsm/libs/stats.module.js; im…

【算法】双指针、递归与回溯、排序、查找

⭐️个人主页&#xff1a;小羊 ⭐️所属专栏&#xff1a;Linux 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 持续更新中...1、双指针移动零复写零快乐数长度最小的子数组dd爱框框 2、递归与回溯3、排序算法4、查找算法 持续更新中… 1、双指…

How to install cangjie on Linux mint 22.1

概述 仓颉编程语言是一款面向全场景智能的新一代编程语言&#xff0c;主打原生智能化、天生全场景、高性能、强安全。主要应用于鸿蒙原生应用及服务应用等场景中&#xff0c;为开发者提供良好的编程体验。 今天&#xff0c;我们介绍一下仓颉语言在Linux mint 22.1上的安装。 …

杰理可视化SDK-手机三方通话控制

杰理可视化SDK-手机三方通话控制 手机三方通话功能杰理SDK三方通话控制SDK三方通话状态获取SDK三方通话处理 手机三方通话功能是手机常用的功能之一。本篇文章简单介绍了杰理可视化SDK在蓝牙耳机应用中&#xff0c;当手机存在三方通话来电或正在进行三方通话时&#xff0c;蓝牙…

【二分算法】-- 寻找旋转排序数组中的最小值

文章目录 1. 题目2. 题目解析3. 代码 1. 题目 在线oj 2. 题目解析 解法一&#xff1a;暴力查找最小值 时间复杂度&#xff1a;0(N) 解法二&#xff1a;二分查找算法 【二段性】&#xff1a; A~B&#xff1a;nums[i] > nums[i 1] C~D&#xff1a;nums[i] < nums[i…

音视频入门基础:RTCP专题(1)——RTCP官方文档下载

一、引言 实时传输控制协议&#xff08;Real-time Transport Control Protocol或RTP Control Protocol或简写RTCP&#xff09;是实时传输协议&#xff08;RTP&#xff09;的一个姐妹协议。RTCP由《RFC 3550》定义&#xff08;取代废弃的《RFC 1889》&#xff09;。RTP使用一个…