首页 > 试题广场 >

夜揽星河入梦

[编程题]夜揽星河入梦

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

$\hspace{15pt}$ 给定一维棋盘上的 $n$ 个黑色棋子，第 $i$ 个棋子的坐标是 $a_i$ ，任意两个棋子的坐标互不相同。若存在 $m$ 个棋子满足如下情况，我们则认为是 $m$ 子连珠：
$\hspace{23pt}\bullet\,$ 将这 $m$ 个棋子的坐标按照从小到大排序后，它们构成一个公差为 $1$ 的等差数列。
$\hspace{15pt}$ 你现在需要判断：是否可以再下一个黑色棋子，使得局面出现 $m$ 子连珠。保证初始局面不存在 $m$ 子连珠。

【名词解释】
$\hspace{15pt}$ 等差数列：是一种数列，满足相邻两项之差相等，这个差值被称作等差数列的公差。例如，对于长度为 $n$ 的数列 $a_1,a_2,\dots,a_n$ ，若存在常数 $d$ ，使得对于任意的 $i\left(1\leqq i<n\right)$ ，都有 $a_{i+1}-a_i=d$ ，则称这个数列是等差数列， $d$ 是这个数列的公差。

输入描述:

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

第一行两个整数 ，表示初始给定的黑色棋子数量和连珠数量。
第二行输入  个整数 ，表示棋子的坐标，保证任意两个棋子的坐标互不相同。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行。如果可以使得局面出现  子连珠，输出 ，否则输出 。

示例1

输入

输出

YES
NO
YES

说明

对于第一组测试数据，可以在  的位置再下一个黑色棋子，此时，棋盘上  三个棋子构成一个公差为  的等差数列，因此局面出现  子连珠。

对于第二组测试数据，无论如何再下一个黑色棋子，都无法使得局面出现  子连珠，因为棋盘上至多只有  个棋子。

算法知识视频讲解

牛客62089986280号

发表于 2025-12-30 21:26:41

C题流氓写法（可以发现，只需要在排序后的数组中，找到长度为的区间内，个数形成等比数列 or 再加个数后个数形成等比数列即可。注意到如果满足以上条件，这个区间的两端端点的值之差分别为： or 所以只需要遍历从 (下标从1开始)到，每次判断该点和该点对应的长度的区间的展开全文

camellia6476

发表于 2026-01-09 18:13:55

第一次发题解，请多包涵由于题目保证给出的数据是不存在个坐标直接满足题意，因此题目要求我们找到个棋子的坐标，从小到大排列之后再插入一个棋子，能使原先这些棋子的坐标构成一个公差为 1 的等差数列。那么我们在在读入数据之后可以先对这些数据进行从小到大的排序。而由于公差为 1 ，所以我们找到的最展开全文

_yuts_

发表于 2026-03-05 11:26:43

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

问题信息

难度：

0条回答 0收藏 139浏览

夜揽星河入梦

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题