type
status
date
slug
summary
tags
category
icon
password
今日学习让我怀疑我的数学真是个lj，算法真的难，难的是他的思想

例题一：

题目来源：

题目描述：

给定一个长度为 nn 且不包含 00 的整数序列 a1,a2,…,ana1,a2,…,an。
请你计算以下两值：
  1. 使得  为负的索引对  的数量。
      2. al×al+1×…×ar
      al×al+1×…×ar
      (l,r)(l≤r)
      (l,r)(l≤r)
  1. 使得  为正的索引对  的数量。
      2. al×al+1×…×ar
      al×al+1×…×ar
      (l,r)(l≤r)
      (l,r)(l≤r)

输入格式

第一行一个整数 nn。
第二行包含 nn 个整数 a1,…,ana1,…,an。

输出格式

共一行，输出单个空格隔开的两个整数，分别表示负的索引对数和正的索引对数。

数据范围

1≤n≤2×1051≤n≤2×105,
−109≤ai≤109,ai≠0−109≤ai≤109,ai≠0。

输入样例1：

输出样例1：

输入样例2：

题解：

 

解析与重点：

首先，这个题目关键在于想到是怎么使用前缀和的，我本来用的是前几个的乘积，但是是二重循环，复杂度到了O(n2)，只能考虑别的，这时候嗨哟可能是负数的个数，这样也可以区分乘积是否是负数
其次，还要考虑的就是最后结果的求法，我们需要想到排列组合的使用，我们已经知道了他的负数个数
这时候的正数的个数就是
  • 1、两个奇数之间肯定不会有负数
  • 2、偶数之间的排列组合
但是这些不包括单个的区间就是（1，1）的这样的，所以正数的还要加上这个单数的
 
算法学习模板——链表、单调栈、单调队列、KMP10.11算法学习：
Loading...