热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【CF125D】Twoprogressions划分等差数列

翻译:有一个整数序列a[],你需要将它划分成两个非空序列,满足两个序列都是等差数列。等差数列定义为相邻两项间差值相等的非空序列;特别地,长度为1或2的序列也是等差数列,但长度为0的不是(因为
翻译:有一个整数序列a[],你需要将它划分成两个非空序列,满足两个序列都是等差数列。"等差数列"定义为相邻两项间差值相等的非空序列;特别地,长度为1或2的序列也是等差数列,但长度为0的不是(因为必须非空)。"划分"定义为,将原序列中的所有元素分成两个序列,满足每个元素都在恰好一个序列中,且保留其在原序列中的顺序。例如[1, 3, 4]和[2, 5]就是[1, 2, 3, 4, 5]的一个划分,[1, 2, 3]和[4, 5]也是,但[1, 2]和[3, 4]不是(不全),[2, 1]和[3, 4, 5]也不是(顺序不对)。
输入格式:第一行一个正整数n,第二行n( 2 ≤ n ≤ 30000)个用空格分隔的整数,表示序列a(  - 108 ≤ ai ≤ 108),且序列中没有重复的元素。
输出格式:假如不存在这样的方案,输出"No solution"(不含引号);否则,输出两行,每行描述划分出的一个等差序列。如果有多个方案,输出任意一个。
样例输入1:
6
4 1 2 7 3 10
样例输出1:
1 2 3
4 7 10

思考过程:很好的贪心题,首先,考试的时候并没有做出来这个题,考完以后,开始搜题解,并没有搜到,于是陷入思考,想了半天,写了个暴力,16个点大数据T掉了。

没办法,直接看的别人的提交记录,看了一下别人的代码,恍然大悟。


题解:因为题目中说要构造两个等差数列,而且顺序还不能变,所以第一个元素一定在某一个序列的开头,明确这一点后考虑,先确定一个数列,生成此数列为等差数列,然后在把剩下的数按顺序加入到第二个序列当中,判断是否为等差数列。生成第一个等差数列可以用公差相等处理,现在已知确定两个数就一定可以计算出。在两个等差数列的公差中,其中一个的公差是固定的,比如说 原序列为{a1,a2,a3,a4,a5} ,那么考虑生成序列的公差,只可能是a2-a1  a3-a2, a3-a1 三个当中的一种,因为无论怎么选,只要选3个,至少有两个在同一个序列当中(抽屉原理)。所以就可以枚举三个公差,判断可行性。有了第一个序列的公差,很容易生成出第一个序列(要生成到不能再生成),那剩下的一定就是第二个数列。但是,每一次维护第一个序列不一定能找到最优解,比如9 12 0 5 10 15 20 25 30,如果按以上的操作进行,会生成9 12 15 和 0 5 10 20 25 30显然这不是最优解。现在考虑在生成第一个数列以后,第二个数列不满足条件时,如何去调整方案。在调整的时候要注意,不能破坏第一个数列的等差数列的合法性,所以就枚举删除第一个数列的末尾元素,插入到第二个数列中,判断是否等差,直到数列一被删空。关于维护第二个数列是否等差, 可以记录每个数的位置,用map暴力记录公差。

successful hack

12
0 6 12 18 23 24 25 26 27 28 29 30


#,include 
using namespace std;
int a[30010], n;
bool vis[30010];
void print(vector  v){
	for(int i = 0; i  v){
	if(!v.size()) return false;
	if(v.size() == 1 || v.size() == 2) return true;
	int d = v[1] - v[0];
	for(int i = 2; i  v1, v2;
	for(int i = 1; i <= n; i ++) vis[i] = 0;
	int d = a[r] - a[l];
	int last = -1, get = a[l];
	for(int i = 1; i <= n; i ++)
		if(a[i] == get) get += d, v1.push_back(a[i]), last = i;
		else vis[i] = 1;
	for(int i = 1; i <= n; i ++) if(vis[i]) v2.push_back(a[i]);
	if(check(v2)){print(v1),print(v2); return true;}
	vis[last] = 1, v1.pop_back(), v2.clear();
	for(int i = 1; i <= n; i ++) if(vis[i]) v2.push_back(a[i]);
	if(check(v2)){print(v1),print(v2);return true;}
	return false;
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	if(n == 2) printf("%d\n%d", a[1], a[2]);
	else if(!solve(1,2) && !solve(2,3) && !solve(1,3)) printf("No solution");
	return 0;
}



推荐阅读
  • 本问题涉及在给定的无向图中寻找一个至少包含三个节点的环,该环上的节点不重复,并且环上所有边的长度之和最小。目标是找到并输出这个最小环的具体方案。 ... [详细]
  • 本文详细介绍了在Luat OS中如何实现C与Lua的混合编程,包括在C环境中运行Lua脚本、封装可被Lua调用的C语言库,以及C与Lua之间的数据交互方法。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 题目概述:Sereja 拥有一个由 n 个整数组成的数组 a1, a2, ..., an。他计划执行 m 项操作,这些操作包括更新数组中的特定元素、增加数组中所有元素的值,以及查询数组中的特定元素。 ... [详细]
  • 本文介绍了使用Python和C语言编写程序来计算一个给定数值的平方根的方法。通过迭代算法,我们能够精确地得到所需的结果。 ... [详细]
  • 本文详细探讨了HihoCoder平台上的1398号问题——最大权闭合子图的求解方法。通过具体实例,深入分析了最大权闭合子图的概念及其算法实现。 ... [详细]
  • Hanks博士是一位著名的生物技术专家,他的儿子Hankson对数学有着浓厚的兴趣。最近,Hankson遇到了一个有趣的数学问题,涉及求解特定条件下的正整数x,而不使用传统的辗转相除法。 ... [详细]
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • td{border:1pxsolid#808080;}参考:和FMX相关的类(表)TFmxObjectIFreeNotification ... [详细]
  • 本文通过C++语言实现了一个递归算法,用于解析并计算数学表达式的值。该算法能够处理加法、减法、乘法和除法操作。 ... [详细]
  • 问题描述现在,不管开发一个多大的系统(至少我现在的部门是这样的),都会带一个日志功能;在实际开发过程中 ... [详细]
  • 本文探讨了Linux环境下线程私有数据(Thread-Specific Data, TSD)的概念及其重要性,介绍了如何通过TSD技术避免多线程间全局变量冲突的问题,并提供了具体的实现方法和示例代码。 ... [详细]
  • 编码unicode解决了语言不通的问题.但是.unicode又有一个新问题.由于unicode是万国码.把所有国家的文字都编进去了.这就导致一个unicode占用的空间会很大.原来 ... [详细]
  • 想把一组chara[4096]的数组拷贝到shortb[6][256]中,尝试过用循环移位的方式,还用中间变量shortc[2048]的方式。得出的结论:1.移位方式效率最低2. ... [详细]
  • 本文详细介绍如何在 Apache 中设置虚拟主机,包括基本配置和高级设置,帮助用户更好地理解和使用虚拟主机功能。 ... [详细]
author-avatar
小Reve_942
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有