热门标签 | 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;
}



推荐阅读
  • 在洛谷 P1344 的坏牛奶追踪问题中,第一问要求计算最小割,而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值,可以在求解最小割时优先选择边数较少的方案,从而同时解决两个问题。这种策略不仅简化了问题的求解过程,还确保了结果的最优性。 ... [详细]
  • 在探讨P1923问题时,我们发现手写的快速排序在最后两个测试用例中出现了超时现象,这在意料之中,因为该题目实际上要求的是时间复杂度为O(n)的算法。进一步研究题解后,发现有选手使用STL中的`nth_element`函数成功通过了所有测试点。本文将详细分析这一现象,并提出相应的优化策略。 ... [详细]
  • 寒假作业解析:第三周 2月12日 第7题
    尽快完成之前的练习任务!每日一练2.1 Problem A Laurenty and Shop 的题目要求是选择两条不同的路线以最小化总的等待时间。简要分析:通过对比不同路线的等待时间,可以找到最优解。此问题可以通过动态规划或贪心算法来解决,具体取决于路线的复杂性和约束条件。 ... [详细]
  • 探索偶数次幂二项式系数的求和方法及其数学意义 ... [详细]
  • 单链表的高效遍历及性能优化策略
    本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中,插入操作的时间复杂度为O(n),而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装,我们实现了创建和销毁功能的优化,提高了单链表的使用效率。此外,文章还介绍了几种常见的优化技术,如缓存节点指针和批量处理,以进一步提升遍历性能。 ... [详细]
  • Android中将独立SO库封装进JAR包并实现SO库的加载与调用
    在Android开发中,将独立的SO库封装进JAR包并实现其加载与调用是一个常见的需求。本文详细介绍了如何将SO库嵌入到JAR包中,并确保在外部应用调用该JAR包时能够正确加载和使用这些SO库。通过这种方式,开发者可以更方便地管理和分发包含原生代码的库文件,提高开发效率和代码复用性。文章还探讨了常见的问题及其解决方案,帮助开发者避免在实际应用中遇到的坑。 ... [详细]
  • 具备括号和分数功能的高级四则运算计算器
    本研究基于C语言开发了一款支持括号和分数运算的高级四则运算计算器。该计算器通过模拟手算过程,对每个运算符进行优先级标记,并按优先级从高到低依次执行计算。其中,加减运算的优先级最低,为0。此外,该计算器还支持复杂的分数运算,能够处理包含括号的表达式,提高了计算的准确性和灵活性。 ... [详细]
  • 本文介绍了如何在iOS平台上使用GLSL着色器将YV12格式的视频帧数据转换为RGB格式,并展示了转换后的图像效果。通过详细的技术实现步骤和代码示例,读者可以轻松掌握这一过程,适用于需要进行视频处理的应用开发。 ... [详细]
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
  • 蓝桥杯算法实战:节点选取策略优化分析
    本文针对蓝桥杯算法竞赛中的节点选取策略进行了深入分析与优化。通过对比不同节点选择方法的效果,提出了基于贪心算法和动态规划的综合优化方案,旨在提高算法效率和准确性。实验结果表明,该优化策略在处理大规模数据集时表现出色,显著提升了算法性能。 ... [详细]
  • 本文对常见的字符串哈希函数进行了全面分析,涵盖了BKDRHash、APHash、DJBHash、JSHash、RSHash、SDBMHash、PJWHash和ELFHash等多种算法。这些哈希函数在不同的应用场景中表现出各异的性能特点,通过对比其算法原理、计算效率和碰撞概率,为实际应用提供了有价值的参考。 ... [详细]
  • PHP服务接口的专业测试方法与实践 ... [详细]
  • SRM 553:深入解析供应链管理系统的最新进展与应用本文详细探讨了供应链管理系统(SCM)的最新发展及其在实际应用中的影响。通过对当前技术趋势的分析,文章揭示了 SCM 在提高效率、降低成本和增强透明度方面的关键作用。此外,还介绍了几种创新的 SCM 解决方案,如区块链技术和人工智能的应用,以及这些技术如何帮助企业更好地应对市场变化和挑战。 ... [详细]
  • 题目链接:http://codeforces.com/gym/101190/attachments题意:在一个共享三轮车站点,某些用户需要租用车辆。该问题涉及如何通过离线查询和排序优化策略来高效地管理和分配车辆资源。具体来说,需要设计一种算法,在满足所有用户需求的同时,最小化总等待时间和资源浪费。通过合理的数据结构和算法优化,可以显著提高系统的整体性能和用户体验。 ... [详细]
  • 在处理遗留数据库的映射时,反向工程是一个重要的初始步骤。由于实体模式已经在数据库系统中存在,Hibernate 提供了自动化工具来简化这一过程,帮助开发人员快速生成持久化类和映射文件。通过反向工程,可以显著提高开发效率并减少手动配置的错误。此外,该工具还支持对现有数据库结构进行分析,自动生成符合 Hibernate 规范的配置文件,从而加速项目的启动和开发周期。 ... [详细]
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社区 版权所有