stdKonjac's Blog

An AC a day keeps the WA away ~

【Sequence】

【题目描述】

Fiugou想要在一个长度为N的序列A中找到不同位置的三个数,以这三个数为三边长来构成一个三角形。但是它希望在满足条件下,这三个数的位置尽量靠前。具体地,设这三个数为A[i],A[j],A[k](i<j<k),Fiugou希望k尽量小;当k相等时,满足j尽量小;当k,j均相等时,满足i尽量小。

但是这个序列中的数可能会发生变化。所以Fiugou给出了M个操作,形式如下:

1 x y: 将A[x]改为y

2:查询最优的合法解,从小到大给出这三个数(而不是位置)。

【输入格式】

第一行一个整数N,代表序列的长度。

第二行有N个整数,代表初始序列。

第三行一个整数M,代表操作的个数。

接下来M行操作,两种操作格式如上所述。

【输出格式】

对于每一个2询问,每次输出三个数,从小到大给出。如果不存在合法的三边,输出-1 -1 -1

【样例输入】

6

7 1 3 4 5 1

3

2

1 3 5

2

【样例输出】

3 5 7

4 5 7

【数据范围】

0≤A[i]≤10^9  1≤x≤N 0≤y≤10^9

这道题玄学复杂度……,看似n^4的暴力实际上只有50^3的复杂度……

实际上你只需要知道对于斐波那契数列前50个数肯定是爆出longint范围了,所以只需要对前50个数进行50^3的枚举就行了。

枚举一定要倒着来,因为是保证最大的那个最小,正着来保证的是最小的那个最小。

这道题是根据构成三角形的条件想到斐波那契数列的特点。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.