首页 > 其他分享 >CF1141F2 Same Sum Blocks (Hard)

CF1141F2 Same Sum Blocks (Hard)

时间:2022-11-02 16:23:34浏览次数:78  
标签:CF1141F2 Sum Hard Same int vector sum

题目传送门

思路

简单题。

不妨先预处理出每一个区间的 \(\sum\),然后离散化 \(\sum\),对于每个 \(\sum\) 开一个 \(\mathcal vector\) 记录所有区间的左右端点。

然后枚举每个 \(\sum\),求最多的区间,这是一个简单的贪心问题,可以用 \(\mathcal set\) 轻松完成。

代码

#include<bits/stdc++.h>
using namespace std;
int const N=3e6+10;
int a[N],lsh[N];
vector< pair<int,int> >qans,anss;
struct node{int l,r,val;}q[N];
vector< pair<int,int> >ins[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;cin>>n;int k=0;
    for (int i=1;i<=n;++i) cin>>a[i];
    for (int i=1;i<=n;++i){
        int res=0;
        for (int j=i;j<=n;++j){
            res+=a[j];lsh[++k]=res;
            q[k]={i,j,res};
        }
    }
    sort(lsh+1,lsh+k+1);int l=unique(lsh+1,lsh+k+1)-lsh-1;
    for (int i=1;i<=k;++i) ins[lower_bound(lsh+1,lsh+l+1,q[i].val)-lsh].push_back({q[i].l,q[i].r});
    for (int i=1;i<=l;++i) sort(ins[i].begin(),ins[i].end());
    for (int i=1;i<=l;++i){
        int len=(int)ins[i].size(),l=0;
        set< pair<int,int> >s;
        for (int j=0;j<len;++j) s.insert({ins[i][j].second,ins[i][j].first});
        int res=0;qans.clear();
        while (s.size()){
            while (s.size() && (*s.begin()).second<=l) s.erase(s.begin());
            if (!s.size()) break;
            l=(*s.begin()).first;
            qans.push_back({(*s.begin()).second,(*s.begin()).first});
            s.erase(s.begin());
        }
        if (qans.size()>anss.size()) anss=qans;
    }
    cout<<(int)anss.size()<<'\n';
    for (auto i:anss) cout<<i.first<<' '<<i.second<<'\n';
    return 0;
}

标签:CF1141F2,Sum,Hard,Same,int,vector,sum
From: https://www.cnblogs.com/tx-lcy/p/16851409.html

相关文章

  • Weird Sum (二维图->拆分为x和y, 整体贡献转化为单个贡献)
     思路:二维图,朴素做法:一个一个枚举优化:发现规律,将x和y分开看来计算是没有影响的单看x,颜色相同的点,按照x从小到大的顺序排序,来计算贡献的时候:通......
  • 线上kafka消息堆积,consumer掉线,怎么办?
    线上kafka消息堆积,所有consumer全部掉线,到底怎么回事?最近处理了一次线上故障,具体故障表现就是kafka某个topic消息堆积,这个topic的相关consumer全部掉线。整体排查过程和......
  • 1分钟学会SUMIFS函数,从此山水永相逢 ,莫问兄长谁更强
    Hi,大家好,本专栏将会从零开始和大家用图文的方式,30天让你从不会到熟练使用函数,0基础开始学习Excel函数,让你喜欢上它!有兴趣的小伙伴可以持续关注我,或者在专栏进行查看学习,愿与......
  • 15. 3Sum
    Givenanarray S of n integers,arethereelements a, b, c in S suchthat a + b + c =0?Findalluniquetripletsinthearraywhichgivesthe......
  • SUMPRODUCT函数10倍提效,只需一步就可秒变大神
    Hi,大家好,本专栏将会从零开始和大家用图文的方式,让你从零基础学会VBA!有兴趣的小伙伴可以持续关注我,或者在专栏自我查看学习,愿与君携手共进!有的小伙伴们说很想了解一下SUMPROD......
  • array_sum/array_column(二维数组指定字段求和)
    二维数组指定字段求和<?php$arr=[["goods_id"=>37,"goods_name"=>"铁砂锅37","goods_weight"=>2,"goods_price"=>......
  • 1005.maximize-sum-of-array-after-k-negations K次取反后最大化数组和
    问题描述1005.K次取反后最大化的数组和解题思路贪心算法代码classSolution{staticboolcmp(inta,intb){returnabs(a)>abs(b);}public:intlar......
  • 【XSY3313】异或和(xorsum)(结论)
    先上一个结论。一个长度为\(n\)的\(01\)序列,其每个子序列的异或和的和为\([序列中包含1]2^{n-1}\)。证明:考虑若不存在\(1\),则显然。否则若存在\(1\),随便选一个......
  • 用sumif取代vlookup
    问题:将补贴表里的数据按姓名填入工资表中。 解题思路:这是一个典型的查找问题,可以使用VLookup函数。=VLOOKUP(B3,P:Q,2,)事实上,只要单位里不存在同名同姓,这题还可......
  • 7.区块链系列之hardhat框架部署合约
    先前讲解的本地部署只能合约的方式编码较多,现在我们介绍目前比较流行的智能合约框架hardhat1.环境准备yarninityarnadd--devhardhatyarnhardhatnpminstall--sa......