首页 > 试题广场 >

小A弹吉他

[编程题]小A弹吉他

热度指数：3268 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

$\hspace{15pt}$ 小 A 不想成为不被需要的人，所以她决定要努力练习吉他。但是她现在被一个作业题卡着了，为了珍惜练习时间，她现在向你求助。

$\hspace{15pt}$ 对于给定的正整数 $m$ ，小 A 需要选一个正整数 $n$ ，并构造一个长度为 $n$ 的正整数序列 $\{a_1,a_2,\dots,a_n\}$ 使得它们的和等于 $m$ 。
$\hspace{15pt}$ 小 A 想知道，对于所有可能的构造，令 $t_i$ 表示 $a_1,a_2,\dots,a_n$ 中等于 $i$ 的元素个数，最大的 $\operatorname{mex}\big\{t_1,t_2,\dots,t_{114^{514}}\big\}$ 是多少。请你求出这个值。

$\hspace{15pt}$ 本题有多组数据，请你对每组数据的 $m$ 都求出相应的结果。

$\hspace{15pt}$ 整数序列的 $\operatorname{mex}$ 定义为没有出现在序列中的最小非负整数。例如 $\operatorname{mex} \{1,2,3 \} =0$ 、 $\operatorname{mex} \{0,2,5\} =1$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

在一行上输入一个正整数  代表规定的数组和。

输出描述:

对于每一组测试数据，在单独的一行上输出一个整数，表示最大的  。

示例1

输入

输出

2
3
4

说明

对于第一组数据，其唯一可能的构造是选取  且 ，这样 ，因此 。
对于第二组数据，其中一种可能的构造是选取  且 ，这样 ，因此 。可以证明这是更优的。

算法知识视频讲解

L9999_

发表于 2025-11-22 11:06:18

题目要求: 的最大值。思路解析：比方说时，最小和为可以发现上述两个式子是等价的，当的时候就在这个前提再加上。这样的话我们提前预处理一下，最后结果再二分查找即可。预处理阶段：计算对于每个，和式的值是如何累积的。这种结构的累加和可以通过递推方式计算。即每增加一个，展开全文

quchen666

发表于 2025-11-22 00:59:10

思路这题我们不难发现，要使得最终的mex尽可能的大，需要我们使用一个贪心策略，假设最终的mex为x+1，那么我们需要构造一个式子, ,要使得式子的求和尽量的少，我们只需要令即可，那么最终的求和就是个平方推导之后的结果就是 ,然后接下来就是二分答案的事情。题解 #include < 展开全文

drawer

发表于 2025-11-22 10:46:47

mathematical formula:四面体数也叫三角锥体数是可以排成底为三角形的锥体（即四面体）的数。四面体数每层为三角形数，其公式是首n个三角形数之和，即n(n+1)(n+2)/6其首几项为：1, 4, 10, 20, 35, 56, 84, 120.(1) 先在vector里标记每个i对展开全文

hushuqi

发表于 2025-11-22 00:16:52

#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int> PII; constexpr int MOD = 1e6 + 3, INF = 2e6; mt 展开全文

此在Dasein

发表于 2025-11-22 03:27:04

核心问题与数学模型本题要求我们构造一个和为的正整数序列，使得序列中各元素出现次数集合的值（最小未出现的非负整数）最大化。 1. MEX 的约束要使，要求该集合必须包含所有小于的非负整数：。由于序列长度有限，总有未使用的数字使得成立，因此总是存在。我们实际需要确保序展开全文

ddb酱

发表于 2025-11-22 11:29:47

#include <bits/stdc++.h> using namespace std; #define endl "\n" #define int long long void solve() { int m;cin >> m; in 展开全文

FoolBlade

发表于 2025-11-22 11:56:01

#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define dbg(x) cout<<#x<<&q 展开全文

怎么不AC啊

发表于 2025-11-22 22:10:56

题目简略描述：给定正整数，长为的正整数数列满足限制，记为中的个数，求解答：记，利用集合的无序性，有如下引理引理1：任意的，都能找到一个（除去0之后）单调递减的同样有. 不妨设单调递增，由于单调递增，由排序不等式，上式，其中单调递减.此时只改变了的顺序，换言之，不变()，因此仍然保持，但是求和展开全文