HZNU 2019 校赛-Little Sub and Triples(小撒布与三数数对)(初见难收的非算法题类型之一)
Little Sub has learned a new word ’Triple’, which usually means a group with three elements in it. Now he comes up with an interesting problem for you.
小撒布学了一个新单词:“Triple”,这个词经常用来表示一个三个元素的构成的组合。现在他想了一个有趣的问题请你解答。
Define F(a,b,c) = e^a∗e^b / e^c
定义多元函数F(a,b,c)=
Given an positive integer sequence A and some queries. In each query, you have to tell if there exists a triple T = (x, y, z) such that:
给定一个正整数序列A以及一些询问。对于每组询问,你得去回答:是否存在一组数T=(x,y,z)满足下列条件:
1.x, y, z are unique integers.
x,y,z为不同数字
2.l ≤ x, y, z ≤ r.
3.Ax ≤ Ay ≤ Az.
4.F(Ax,Ay,Az) > 1.
The first line contains two positive integers n, q(1 ≤ n, q ≤ 200000).
第一行包含两个正整数n,q
The second line contains n positive integers, indicating the integer sequence. The next q lines describe each query by giving two integer l, r(1 ≤ l ≤ r ≤ n). All given integers will not exceed 2^31 − 1.
第二行包含n个正整数,代表整数序列.接下来的q行以两个整数l,r的形式代表每组询问。所有整数不会超过int范围。
Due to some reasons, when l>r, please consider it as an empty interval. Sorry for it.
由于某种原因,当l>r的时候,请把它当做一个空区间。为此感到抱歉。
For each query, print YES if it exists any legal triple or NO otherwise.
对于每组询问,如果有这么一组合法数对,那么输出yes,反之no
input:
4 2 1 2 3 4 1 3 2 4
output:
NO YES
倘若不是见过,谁知道解决这个鬼东西必须要借助斐波那契数列呢?
根据题意,观察一下Ax ≤ Ay ≤ Az和F(Ax,Ay,Az) > 1这两个条件,根据原函数可以把他们改编成如下形式:
x+y>z 且Ax ≤ Ay ≤ Az,也就是说要解决这个问题,需要A序列是单调递增的。然而题目中可没这么说。
所以我们转而考虑临界值:x+y=z,也就正好是斐波那契数列的形式,同时不满足以上条件的两数之和只能是斐波那契值,所以在int的数据范围内只有不足50组这样的三数数对,从而得出长度大于50的区间必然有满足条件的数。
如果区间长度小于50呢?这个时候的数据很小,所以我们直接把这段数据复制下来,在排序后一个一个判断就可以了。
所以思路如下:
代码:
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cmath>
#define DETERMINATION main
#define lldin(a) scanf("%lld",&a)
#define din(a) scanf("%d",&a)
#define printlnlld(a) printf("%lld\n",a)
#define printlnd(a) printf("%d\n",a)
#define printlld(a) printf("%lld",a)
#define printd(a) printf("%d",a)
#define reset(a,b) memset(a,b,sizeof(a))
const long long int INF=0x3f3f3f3f;
using namespace std;
const double PI=acos(-1);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod=1000000007;
const int tool_const=1999112620000907;
const int tool_const2=33;
inline ll Unnamed_Scanner()
{
ll tmp=0,si=1;
char c=getchar();
while(c>'9'||c<'0')
{
if(c=='-')
si=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
tmp=tmp*10+c-'0';
c=getchar();
}
return si*tmp;
}
///Schlacht von Stalingrad
/**Although there will be many obstructs ahead,
the desire for victory still fills you with determination..**/
ll fib[65];
ll container[200930];
int DETERMINATION()
{
fib[1]=1,fib[2]=1;
//cout<<(1<<31)-1<<endl;
for(int i=3; i<=50; i++)
{
fib[i]=fib[i-1]+fib[i-2];
//cout<<fib[i]<<endl;
}
ll n,q;
lldin(n),lldin(q);
for(int i=1; i<=n; i++)
lldin(container[i]);
for(int j=1; j<=q; j++)
{
ll left,right;
lldin(left),lldin(right);
if(right-left>50)
{
printf("YES\n");
}
else if(left>right)
{
printf("NO\n");
}
else if(right-left<=50)
{
ll tmp[5656];//存储临时数据的数组
reset(tmp,0);
int cnt=1;
for(int i=left;i<=right;i++)
{
tmp[cnt++]=container[i];
}
// for(int i=1;i<cnt;i++)
// cout<<tmp[i]<<endl;
sort(tmp+1,tmp+cnt+1);
bool sign=false;
for(int i=3; i<=cnt; i++)
{
//cout<<tmp[i]<<endl;
if(tmp[i]<tmp[i-1]+tmp[i-2])
{
sign=true;
break;
}
}
if(sign)
printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}
优质内容筛选与推荐>>