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

CodeForces722C数组破坏算法解析与优化策略

题意: 先给你一个序列,然后给你n个1-n的一个数,让你求前i个元素销毁的时候,区间字段和区间最大; 思路: 离线处
题意:

先给你一个序列,然后给你n个1-n的一个数,让你求前i个元素销毁的时候,区间字段和区间最大;

思路:

离线处理,维护新区间首尾位置的起点和终点,倒着处理;


#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairPII;
const double eps=1e-5;
const double pi=acos(-1.0);
//const int mod=1e9+7;
const int INF=0x3f3f3f3f;const int N=1e5+10;
struct asd{int s,t;
};
asd q[N];LL a[N];
LL ans[N],sum[N];
int sp[N],temp[N];int main()
{int n;scanf("%d",&n);sum[0]&#61;0;for(int i&#61;1;i<&#61;n;i&#43;&#43;){scanf("%lld",&a[i]);sum[i]&#61;sum[i-1]&#43;a[i];}for(int i&#61;1;i<&#61;n;i&#43;&#43;)scanf("%d",&sp[i]);memset(temp,0,sizeof(temp));for(int i&#61;1;i<&#61;n;i&#43;&#43;)q[i].s&#61;q[i].t&#61;i;ans[n]&#61;0;LL TMAX&#61;0;for(int i&#61;n;i>&#61;2;i--){temp[sp[i]]&#61;1;if(temp[sp[i]-1])q[sp[i]].s&#61;q[sp[i]-1].s;if(temp[sp[i]&#43;1])q[sp[i]].t&#61;q[sp[i]&#43;1].t;q[q[sp[i]].t].s&#61;q[sp[i]].s;q[q[sp[i]].s].t&#61;q[sp[i]].t;TMAX&#61;max(TMAX,sum[q[sp[i]].t] - sum[q[sp[i]].s-1]);ans[i-1]&#61;TMAX;
// printf("%d %d\n",q[sp[i]].s,q[sp[i]].t);}for(int i&#61;1;i<&#61;n;i&#43;&#43;)printf("%lld\n",ans[i]);return 0;
}






推荐阅读
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本教程涵盖OpenGL基础操作及直线光栅化技术,包括点的绘制、简单图形绘制、直线绘制以及DDA和中点画线算法。通过逐步实践,帮助读者掌握OpenGL的基本使用方法。 ... [详细]
  • 探索1000以内的完美数:因数和等于自身
    本文探讨了如何在1000以内找到所有完美数,即一个数的因数(不包括自身)之和等于该数本身。例如,6是一个完美数,因为1 + 2 + 3 = 6。通过编程实现这一过程,可以更好地理解完美数的特性。 ... [详细]
  • 本题通过将每个矩形视为一个节点,根据其相对位置构建拓扑图,并利用深度优先搜索(DFS)或状态压缩动态规划(DP)求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]
author-avatar
飘香的风中栀子
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有