BAPC 2019 F. Find my Family set + 二分

一时失言乱红尘 2023-07-18 04:50 7阅读 0赞

题目链接：https://nanti.jisuanke.com/t/44322  
题意：给你n个数的序列，问你是否存在ai > aj, aj < ak, ai < ak, i < j < k  
思路：我们贪心的想，由于要是ak最大，所以我们从后往前取一个最大值，前面的用set维护一下  
二分找到第一个大于ai的，检查是否小于ak，并将找到的数从set中删除，扫描一遍即可。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define fi first
    #define se second
    #define ls rt << 1
    #define rs rt << 1|1
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    #define pll pair<ll, ll>
    #define pii pair<int, int>
    #define ull unsigned long long
    #define pdd pair<double, double>
    const int mod = 998244353;
    const int maxn = 3e5 + 10;
    const int inf = 0x3f3f3f3f;
    set<int> s;
    int a[maxn];
    vector<int> v;
    
    int main()
    {
        int t;
        scanf("%d", &t);
        for(int t1 = 1; t1 <= t; ++t1)
        {
            s.clear();
            int n;
            scanf("%d", &n);
            for(int i = 1; i <= n; ++i)
            {
                scanf("%d", &a[i]);
                if(i != n)
                    s.insert(a[i]);
            }
            int Max = a[n], f = 0;
            for(int i = n - 1; i > 1; --i)
            {
                auto x = s.upper_bound(a[i]);
                if(x != s.end() && *x < Max)
                {
                    f = 1;
                    break;
                }
                auto p = s.find(a[i]);
                Max = max(Max, *p);
                s.erase(p);
            }
            if(f) v.push_back(t1);
        }
        printf("%d\n", (int)v.size());
        for(auto x : v) printf("%d\n", x);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关 BAPC 2019 F. Find my Family set + 二分

题目链接：https://nanti.jisuanke.com/t/44322 题意：给你n个数的序列，问你是否存在ai > aj, aj < ak, ai < ak, i

一时失言乱红尘/ 2023年07月18日 04:50/ 0 赞/ 8 阅读

相关 BAPC 2019 E. Efficient Exchange 思维+ 贪心

题目链接：https://nanti.jisuanke.com/t/44331 题意：你有无限的1,10,100……金钱，现在你要花费n元，你的代价是花费的金币数和找零的金

Dear 丶/ 2023年07月18日 04:49/ 0 赞/ 8 阅读

相关 BAPC 2019 A. Appeal to the Audience 贪心 + DFS

题目链接：https://nanti.jisuanke.com/t/44317 题意：给你一棵树和k个值，要把这k个值放在k个叶子结点上，而对每个非叶子结点来说它的值

╰半夏微凉°/ 2023年07月18日 04:48/ 0 赞/ 6 阅读

相关 FIND_IN_SET

select \ from user where find\_in\_set(1,position) 精准查询字段中所包含的值 select \ from user wh

谁践踏了优雅/ 2022年12月16日 13:27/ 0 赞/ 120 阅读

相关 FIND_IN_SET

FIND\_IN\_SET支持查询某个字段以逗号分隔的string数据如想查询school\_id里面包含2,4的但是字段里的数据都是1,2,3或者2,3,4；2,4,8

港控/mmm°/ 2022年05月18日 00:47/ 0 赞/ 169 阅读

相关 FIND_IN_SET函数

FIND\_IN\_SET函数是IN函数的升级版.功能类似. 区别在于:如果是常量，则可以直接用IN，否则要用FIND\_IN\_SET()函数 MySQL中原型为：FI

Love The Way You Lie/ 2022年04月12日 04:50/ 0 赞/ 210 阅读

相关 MySQL find_in_set

[https://www.cnblogs.com/yzryc/p/6397953.html][https_www.cnblogs.com_yzryc_p_6397953.htm

不念不忘少年蓝@/ 2022年01月09日 07:41/ 0 赞/ 352 阅读

相关 2019南昌网络赛-M（二分）

题目链接：https://nanti.jisuanke.com/t/38232 题意：给定字符串s（长度<=1e5)，然后N组样例(N<=1e5)，每组输入一个字符串t判断t

冷不防/ 2021年12月21日 01:07/ 0 赞/ 200 阅读

相关 Gym 101170F Free Weights（二分）题解

题意：给出两行，每一行都有n个数组，一共有2 \ n个，大小为1~n，每个有两个。现在可以进行操作：拿出一个物品i，然后放到一个空格，花费i。可以任意平移物品，平移没有花费。每

素颜马尾好姑娘i/ 2021年12月20日 04:53/ 0 赞/ 173 阅读

相关 [HNOI2019]序列（单调栈+二分）

通过打表证明发现答案就是把序列划分成若干段，每段的b都是这一段a的平均数。50分做法比较显然，就是单调栈维护，每次将新元素当成一个区间插入末尾，若b值不满足单调不降，则将这个区

今天药忘吃喽~/ 2021年11月01日 08:42/ 0 赞/ 341 阅读