专栏文章

题解：CF1991F Triangle Formation

WWilliam2022
CF1991F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio6jr8p
此快照首次捕获于
2025/12/02 14:11
3 个月前
此快照最后确认于
2025/12/02 14:11
3 个月前
查看原文

题目大意

给你 nn 个数字 a1,a2,…,ana_1,a_2,\ldots,a_n。
有 qq 个问询，每次询问区间 [l,r][l,r]，询问将区间内的数字作为边长能否构建出两个非退化三角形（不能重复使用一个数字）。
n,q≤105,ai≤109n,q\leq10^5, a_i\leq10^9。

入手

先简化问题，如果只要一个三角形，并且只有一次问询 [1,n][1,n]，怎么做。
直接排序，然后对所有相邻的三个数字检查是否满足 ai+ai+1>ai+2a_i+a_{i+1} > a_{i+2} 即可。
如果再算几组样例，就会发现一个特殊性质：当 nn 足够大时，总能找出一个三角形。
尝试构造最长无三角形的序列，需要满足排序后 ai+ai+1≯ai+2a_i+a_{i+1} \ngtr a_{i+2} 并且数字最小，不难想到是 ai+ai+1=ai+2a_i+a_{i+1} = a_{i+2}，也就是等差数列。
而 ai≤109a_i\leq10^9，就导致 nn 大概最大在 log⁡ϕ109\log_{\phi} 10^9 左右，使用程序验证可得 n<45n < 45。
因此，当 n≥45n \geq 45 时，一定存在一个三角形。
稍微推导可得，当 n≥48n \geq 48 时，一定存在两个三角形。

解法

分类讨论，若 r−l+1≥48r-l+1\geq48 直接返回 Yes。
否则就代表区间长度非常小，这就比较简单了，可以先取出区间内的元素并排序。
如果三个数要组成三角形，那么它们在排序后一定相邻，但两个三角形有个特殊情况就是两个三角形的六个数相邻，但一个三角形的三个数不相邻，需要特判。
先判断是否有两组不重叠的 ai,ai+1,ai+2a_i,a_{i+1},a_{i+2} 能组成三角形。
再判断所有相邻的 66 个数 ai,ai+1,ai+2,ai+3,ai+4,ai+5a_i,a_{i+1},a_{i+2},a_{i+3},a_{i+4},a_{i+5} 是否能组成两个三角形。
判断这两种情况就够了。
时间复杂度 O(n+q⋅log⁡A⋅log⁡log⁡A)O(n+q \cdot \log A \cdot \log\log A)，其中 AA 为 aia_i 的值域大小。

代码

CPP
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10,C=50;

bool tri(int a,int b,int c){return a+b>c;}//判断有序的三个数能否组成三角形
bool check(int a,int b,int c,int d,int e,int f){//判断有序的六个数能否组成两个三角形
    if(tri(a,b,c) && tri(d,e,f))return 1;
    if(tri(a,b,d) && tri(c,e,f))return 1;
    if(tri(a,b,e) && tri(c,d,f))return 1;
    if(tri(a,b,f) && tri(c,d,e))return 1;

    if(tri(a,c,d) && tri(b,e,f))return 1;
    if(tri(a,c,e) && tri(b,d,f))return 1;
    if(tri(a,c,f) && tri(b,d,e))return 1;

    if(tri(a,d,e) && tri(b,c,f))return 1;
    if(tri(a,d,f) && tri(b,c,e))return 1;

    if(tri(a,e,f) && tri(b,c,d))return 1;

    return 0;
}

int n,Q,a[N];

bool quest(int l,int r){//一次询问，返回布尔类型，1是yes，0是no
    if(r-l+1>=C)return 1;

    vector<int> v;
    for(int i=l;i<=r;i++)v.emplace_back(a[i]);
    sort(v.begin(),v.end());//排序

    bool flg=0;
    for(int i=0;i+2<v.size();i++){
        if(tri(v[i],v[i+1],v[i+2])){//两组 "相邻的三个"
            if(flg)return 1;
            flg=1;
            i+=2;
        }
    }

    for(int i=0;i+5<v.size();i++){//特殊情况，相邻的六个
        if(check(v[i],v[i+1],v[i+2],v[i+3],v[i+4],v[i+5]))return 1;
    }

    return 0;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin>>n>>Q;
    for(int i=1;i<=n;i++)cin>>a[i];

    while(Q --> 0){
        int l,r; cin>>l>>r;
        cout<<(quest(l,r)?"Yes":"No")<<"\n";
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...