首页 > 其他分享 >[BZOJ P2771] 天才ACM

[BZOJ P2771] 天才ACM

时间:2025-01-18 17:21:44浏览次数:1  
标签:int sum 校验 ACM ++ ans P2771 排序 BZOJ

[BZOJ P2771] 天才ACM

传送门

朴素算法

枚举终点 \(r\),对区间 \([l, r]\) 排序求校验值 \(sum\),比较 \(sum\) 和 \(t\)

  • $ sum \le t $ r++
  • $ sum > t $ l=++r,ans++

时间复杂度N2log N

初步优化

考虑校验值单调不下降,可枚举左端点l时二分右端点r,再对区间l~r求校验值,更新方法如上

时间复杂度 \(O(N\log^2N)\)

但是我们会发现这道题还是过不去,于是仔细读题,发现有一个很恶心的K组数据,那么就需要进一步卡常优化

卡常 最后优化

可以发现,当我们二分右端点r时计算校验值会重复排序已排序的部分,考虑不去重复计算

  1. 使用归并的思想对满足条件的部分和待排序的部分合并,常数优化
  2. 前一步的基础是区间长度单调不减,所以考虑使用倍增思想增加长度,定义一个变量p,每次判断l~r+p是否满足校验值不大于T
    • 满足 r+=p,p<<=1;
    • 不满足 p>>=1
    • p==0 ans++,r++,l=r,p=1;

最后

总结一下,这道题是一道抽象的倍增和二分,思维难度较高但知识难度不是很高的好题,稍微需要一点卡常优化技巧

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
int t, n, m, ans;
LL s, sum;
LL a[N], f[N], mg[N];
inline void merge(int l, int r, int mid) {
    int i = l, j = mid + 1;
    for (int k = l;k <= r;k++)
        if (j > r || i <= mid && f[i] <= f[j]) mg[k] = f[i++];
        else mg[k] = f[j++];
}
inline bool check(int l, int r, int mid) {
    for (int i = mid;i <= r;i++) f[i] = a[i];
    sort(f + mid, f + r + 1);
    merge(l, r, mid - 1);
    sum = 0;
    for (int i = 1;i <= ((r - l + 1) >> 1) && i <= m;i++) sum += (mg[r - i + 1] - mg[l + i - 1]) * (mg[r - i + 1] - mg[l + i - 1]);
    if (sum <= s) {
        for (int i = l;i <= r;i++) f[i] = mg[i];
        return true;
    }
    else return false;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        ans = 0;
        scanf("%d%d%lld", &n, &m, &s);
        for (int i = 1;i <= n;i++) scanf("%lld", &a[i]);
        int l = 1, r = 1, p = 1;
        f[1] = a[1];
        while (r <= n) {
            if (p == 0) {
                ans++, r++;
                l = r, f[l] = a[l], p = 1;
            }
            else if (r + p <= n && check(l, r + p, r + 1)) r += p, p <<= 1;
            else p >>= 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

标签:int,sum,校验,ACM,++,ans,P2771,排序,BZOJ
From: https://www.cnblogs.com/keysky/p/18678626

相关文章

  • [BZOJ2194] 快速傅立叶之二 题解
    看名字,然后准备转化为多项式乘法。\[c_k=\sum_{i=0}^{n-k-1}a_{i+k}b_i\]将\(a\)反转,得:\[c_k=\sum_{i=0}^{n-k-1}a_{n-i-k-1}b_i\]这已经是多项式乘法的格式了,直接多项式乘法,最后对函数\(c\)的\(0\)到\(n-1\)次项倒序输出即可。时间复杂度\(O(n\logn)\)。#include......
  • 【ACM独立出版,南通大学主办-往届均已检索】第二届智慧教育与计算机技术国际学术会议(IE
      【会议亮点】ACM独立出版,EI、SCOPUS双检索首届ACM独立出版,会后4个月内完成EI、SCOPUS双检索教育与人工智能、计算机等研究方向相结合的主题均可投递由南通大学主办,教育科学学院参与会议,并做大力支持支持线上参会,线上做口头报告,线上做海报展示大会名称:第二届智慧教育......
  • 【西南科技大学计算机学院、智能计算与系统结构实验室主办 | ACM独立出版 | 往届均已
    ACM独立出版|往届均已成功检索,最快刊后1个月内实现EI检索征稿主题范围广:计算机网络安全、软件工程、信号处理、程序分析等领域主办单位:西南科技大学计算机学院、智能计算与系统结构实验室第五届计算机网络安全与软件工程国际学术会议(CNSSE2025)20255thInternational......
  • (即插即用模块-Attention部分) 三十四、(2022) FACMA 频率感知跨通道注意力
    文章目录1、Frequency-AwareCross-ModalityAttention2、WeightedCross-ModalityFusionmodule3、代码实现paper:FCMNet:Frequency-awarecross-modalityattentionnetworksforRGB-DsalientobjectdetectionCode:https://github.com/XiaoJinNK/FCMNet1、......
  • [Linux]pacman命令详解
    以下只是一些pacman的简单操作实例。1.更新系统在Archlinux中,使用一条命令即可对整个系统进行更新: pacman-Syu如果你已经使用pacman-Sy将本地的包数据库与远程的仓库进行了同步,也可以只执行:pacman-Su2.安装包#pacman-S包名:例如,执行pacman-Sfirefox......
  • BZOJ4399 魔法少女LJJ —— 线段树合并
    题意提示对100%的数据0<=m<=400000,c<=7,所有出现的数均<=1000000000,所有出现的点保证存在【HINT】请认真阅读题面考语文分析由于只有合并,没有分裂,所以只需要考虑合并联通块中的信息即可。具体而言,在联通块的根对应的线段树下标存储该联通块下元素对应的权值。直接线段......
  • [BZOJ3159] 决战 题解
    个人感觉各方面难度高于《在美妙的数学王国中畅游》,也不知道是不是求导的关系,这题\(luogu\)难度评级还更低。不过感觉这题作完对\(LCT\)理解更顺畅了。前四个操作简单,关键在第五人格操作。注意力惊人的注意到我们无法像普通\(Splay\)一样,直接对\(LCT\)中的\(Splay\)......
  • [BZOJ4665] 小 w 的喜糖
    思路坏了这次没啥思路转化题意,求存在多少种数列\(B\),使得\(B\)与\(A\)中,每种元素出现的次数相同并且满足\(A_i\neqB_i\)是这样转化的吗你考虑直接算,但是这样无论如何你要记录每种元素当前的出现次数作为状态,不可能啊怎么做比较方便?看下标签发现可以使用......
  • [BZOJ3230] 相似子串 题解
    \(\text{[BZOJ3230]相似子串题解}\)巧妙地利用了后缀数组的一些奇妙性质。先考虑第一问。首先去处理本质不同的子串这个东西。这个东西我们显然是见过的,于是套路地建出SA求出\(\operatorname{height}\)数组。每一个子串对应的都是一个后缀的前缀。由于串都是本质不同的,那......
  • [BZOJ2839] 集合计数
    思路直接计算不好计算,套路的,考虑「至少」「至多」来转化容易发现你「钦定」\(k\)个元素在交集之中,也就是说交集大小「至少」为\(k\),怎么处理这个的方案数,其实比较容易可以发现,这个的方案数为\[f(k)={n\choosek}\sum_{i=0}^{n-k}2^i\]不够优,考虑转......