首页 > 其他分享 >2022 百度之星初赛 第二场 A

2022 百度之星初赛 第二场 A

时间:2022-08-28 18:56:05浏览次数:78  
标签:第二场 cnt int tr cin 初赛 st 2022 ans

A题:

题目:

 

 

双指针,莫队回滚,线段树,归并树都可以过

线段树:

做法1.给每个节点存当前区间前 k 大的数

做法2.存最大值和它的位置

#define int ll
const int N = 1e5+10;
int n,q,k,x;

int a[N];
struct node {
    int l,r,mk;//
    V<int> v;
} tr[4 * N];
bool cmp(int a,int b) {
    return a > b;
}
void push_up(int p) {
    V<int> pp;
    for(auto it:tr[p<<1].v) {
        pp.push_back(it);
    }
    for(auto it:tr[p<<1|1].v) {
        pp.push_back(it);
    }
    int cnt = 0;;
    sort(pp.begin(),pp.end(),cmp);
    for(auto it:pp) {
        tr[p].v.push_back(it);
        cnt ++ ;
        if(cnt >= k) break;
    }
}

void build(int p,int l,int r) {
    tr[p] = {l,r};
    if(l == r) {
        tr[p].mk = a[l];
        tr[p].v.push_back(a[l]);
        rt;
    }
    int mid = l + r >> 1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    push_up(p);
}

V<int> query1(int p,int l,int r) {
    if(l <= tr[p].l && tr[p].r <= r) {
//        db(tr[p].v[0]);
//        dbb(l,r);
//        dbb(tr[p].l,tr[p].r);
        return tr[p].v;
    }
    int mid = tr[p].l + tr[p].r >> 1,ans = 0;
    V<int> que;
    if(l <= mid) {
        que = query1(p<<1,l,r);
    }
    
    if(mid < r) {
        
        V<int> tmp = query1(p<<1|1,l,r);
        for(auto it:tmp) {
            que.push_back(it);
        } 
    }
    V<int> tmp;
    sort(all(que),cmp); 
    int leng = que.size();
    for(int i = 0;i<min(k,leng) ;i++) {
        tmp.push_back(que[i]);
    }
//    dbb(l,r);
//    db(tmp.size());
    return tmp;
}

void solve()
{
    cin>>n>>q>>k>>x;
    fo(i,1,n) cin>>a[i];
    build(1,1,n);
    while(q -- ) {
        int l,r;cin>>l>>r;
        if(r < l) {
            cout<<"N"<<endl;
            continue;
        }
        V<int> tmp = query1(1,l,r);
        int cnt = 0;
        ll res = 0;
//        db(tmp.size());
        for(auto it:tmp) {
            res += it;
            cnt ++;
            if(cnt == k) break;
        }
//        cout<<res<<endl;
        if(res >= x) {
            cout<<"Y"<<endl;
        } else {
            cout<<"N"<<endl;
        }
    }
    rt;
}

双指针:

求对于每个r 最早的 l 在哪里。

如果[l,r]满足条件 [l,r+1] 也满足条件

所以可以用双指针判断对于每个 r 最早的 l 在哪里

可以用set<int,greater<int>> st存 每个数,挨个判断最前面的数在里面是否满足条件

如果满足条件就删掉,直到遇到不满足条件的时候,再重新装进去

这个时候枚举到的 j 就是对于这个 r 最早的 l

const int N = 1e5+10;
int n,q,k,x;

int a[N],ans[N];

void solve()
{
//    cin>>n>>m;
    ms(ans,-0x3f)
    set<int,greater<int>> st;
    cin>>n>>q>>k>>x;
    fo(i,1,n) cin>>a[i];
    int j = 1;
    fo(i,1,n) {
         auto check = [&]()->int{
             int sum = 0,cnt = 0;
             for(auto y:st) {
                 cnt ++ ;
                 sum += y;
                 if(sum >= x) return 1;
                 if(cnt == k) break;
             }
             return 0;
         };
         
         st.insert(a[i]);
         if(!check()) continue;
         while(check()) st.erase(st.find(a[j])),j++;
         j -- ;
         st.insert(a[j]);
         ans[i] = j;
    }
    while(q -- ) {
        int l,r;cin>>l>>r;
        if(ans[r] >= l) {
            cout<<"Y"<<endl;
        } else cout<<"N"<<endl;
    }
}

莫队回滚:不会

 

标签:第二场,cnt,int,tr,cin,初赛,st,2022,ans
From: https://www.cnblogs.com/er007/p/16633379.html

相关文章

  • 报告分享|2022广告营销行业人才趋势报告
    原文链接:http://tecdat.cn/?p=283392022上半年疫情反复,对广告营销行业产生了不小的影响,不少广告营销人的职业发展受限,广告公司也面临招人难等问题。此外,在广告营销行业存......
  • ECCV 2022 | 新方案: 先剪枝再蒸馏
    前言 论文提出了一个新的框架,“prune,thendistill”,该框架首先剪枝模型,使其更具可移植性,然后提取给student。并进一步从理论上证明了剪枝后的teacher在蒸馏中起到正则化......
  • 【动植物研究动态】20220815文献解读
    目录HorticRes|武汉大学李家儒:盾叶薯蓣高质量基因组解析与薯蓣皂苷生物合成进化TheCropJournal|华南农业大学肖德琴:一种新的水稻穗多发育期自动识别算法TheCropJo......
  • 【动植物研究动态】20220828文献解读
    目录ScienceBulletin|中国农科院作科所徐建龙&邱丽娟:大豆种质资源组学数据库SoyFGBv2.0搭建SCLS|种康、贾继增等:中国小麦基因组学和性状改良研究综述TheCropJourna......
  • 【2022最新教学】喜马拉雅音频提取导出mp3格式并保存到本地
    如何把喜马拉雅下载的音频声音导出来?手机上使用喜马拉雅app收听作品,听到喜欢的作品后,可能想要下载下来,这里介绍下下载方法。喜马拉雅会员FM专辑导出器它可以根据专辑ID......
  • 2022-8-28 每日一题-二分查找-剑指offer-字典树
    793.阶乘函数后K个零难度困难122收藏分享切换为英文接收动态反馈 f(x) 是 x! 末尾是0的数量。回想一下 x!=1*2*3*...*x,且 0!=1 。例如, ......
  • ZROI 2022 NOIP十连测 Day1
    赛后总结A是一个签到题,几分钟A掉了B是一个神仙题,打了20分,剩下的不会了!C是一个神仙题,连20分都不想打D是一个细节多题,死活过不了第二个样例。总结:坐牢。那我打模拟赛是......
  • 2022年8月28日
    经历了人生的大起大落,身边的人态度180度大转变,面目可憎!看清了人情冷暖,世态炎凉,虚情假意的同学,不再真诚的朋友,不再想见任何人了,虚情假意的亲戚,我不再假装有很多朋友,而是回到......
  • 数据库学习笔记 (本数据库学习笔记以SQL sever 2019 为例进行学习) 20220824 第二节课
    什么是数据模型?数据模型:是对现实世界数据特征的抽象,他是用来描述数据、组织数据和对数据进行操作的。在数据库中用数据模型这个工具来抽象、表示和处理现实世界中的数据......
  • NOI2022 游记
    NOI2022游记目录NOI2022游记08120820082108220823082408250826感觉还是应该写点游记什么的东西,不然可能到明年我高二退役的时候发现信竞相关的回忆都忘光光了。开始写......