二分+模拟,CF1461D - Divide and Summarize

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1461D - Codeforces


二、解题报告

1、思路分析

我们发现每次分裂操作结果都是固定的

我们从初始序列分裂出两个确定的子序列,两个确定的子序列又分裂出4个确定的子序列

那么也就是说我们最终能够分裂出的子序列的数目是O(n)的

我们预处理出所有的子序列就预处理出了所有可以得到的和(当然这个和要在分裂的过程中维护)

而分裂要求我们得到小于等于mid的部分和大于的部分

所以我们需要对原序列进行排序,模拟的过程通过二分来找到分裂的位置

同时预处理前缀和以便每次分裂前都记录一下当前得到的值

值得注意的是nums[l] = nums[r]的时候说明当前子序列是相同的,我们无法继续向下分裂

2、复杂度

时间复杂度: O(NlogN)空间复杂度:O(N)

3、代码详解

#include <bits/stdc++.h>
using PII = std::pair<int, int>;
using i64 = long long;
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());

const int P = [](int x) {
    auto isprime = [](int x) {
        if (x <= 1) return false;
        for (int i = 2; i <= x / i; i ++ )
            if (x % i == 0) return false;
        return true;
    };
    while (!isprime(x)) x ++;
    return x;
}(rnd() % 900000000 + 100000000);

void solve() {
    /*  直接模拟    */
    int N, Q, s;
    std::cin >> N >> Q;
    std::vector<int> nums(N);
    std::vector<i64> pre(N + 1);
    for (int i = 0; i < N; i ++ ) 
        std::cin >> nums[i];
    std::sort(nums.begin(), nums.end());

    for (int i = 0; i < N; i ++ ) 
        pre[i + 1] += nums[i] + pre[i];
    
    std::vector<std::array<int, 2>> segs { { 0, N - 1 } };  segs.reserve(N);
    std::unordered_set<i64> st;

    while (segs.size()) {
        std::vector<std::array<int, 2>> nxt;
        for (auto& [l, r] : segs) {
            st.insert(pre[r + 1] - pre[l] + P);

            if (nums[l] != nums[r]) {
                int mid = std::upper_bound(nums.begin(), nums.end(), (nums[l] + nums[r]) >> 1) - nums.begin();
                nxt.insert(nxt.end(), { { l, mid - 1 }, { mid, r } });
            }
        }
        segs = std::move(nxt);
    }

    for (int i = 0, s; i < Q; i ++) {
        std::cin >> s;
        if (st.count(1LL * s + P))
            std::cout << "YES\n";
        else
            std::cout << "NO\n";
    }
}


int main () {
    std::ios::sync_with_stdio(false);   std::cin.tie(0);  std::cout.tie(0);
    int _ = 1;
    std::cin >> _;
    while (_ --)
        solve();
    return 0;
}

相关推荐

  1. CF1918 D. Blocking Elements [二分+数据结构优化dp]

    2024-06-09 07:46:02       26 阅读
  2. CF988D题解

    2024-06-09 07:46:02       6 阅读
  3. 题解:CF1923D(Slimes)

    2024-06-09 07:46:02       17 阅读
  4. CF1547F Array Stabilization (GCD version) 二分+ST表

    2024-06-09 07:46:02       31 阅读
  5. 题解:CF1946D(Birthday Gift)

    2024-06-09 07:46:02       8 阅读

最近更新

  1. 【gdb使用】

    2024-06-09 07:46:02       0 阅读
  2. nginx入门与实践

    2024-06-09 07:46:02       0 阅读
  3. 深入理解 JVM 的几种常见垃圾回收算法

    2024-06-09 07:46:02       0 阅读
  4. Aeron:Online Resources

    2024-06-09 07:46:02       0 阅读
  5. 安卓gradel下载失败解决方案

    2024-06-09 07:46:02       0 阅读
  6. 实战

    实战

    2024-06-09 07:46:02      0 阅读
  7. 力扣719.找出第K小的数对距离

    2024-06-09 07:46:02       0 阅读
  8. 10月,2024北京养老展,北京老年生活用品展览会

    2024-06-09 07:46:02       0 阅读

热门阅读

  1. 使用 LLaMA-Factory 实现对大模型函数调用功能

    2024-06-09 07:46:02       4 阅读
  2. 二叉树----7-3 列出叶结点

    2024-06-09 07:46:02       4 阅读
  3. bat指令踩坑记录

    2024-06-09 07:46:02       3 阅读
  4. Web Dart前端:探索、挑战与未来展望

    2024-06-09 07:46:02       5 阅读
  5. 计算机视觉中的low-level与 high-level任务

    2024-06-09 07:46:02       5 阅读
  6. python记录之字符串

    2024-06-09 07:46:02       5 阅读
  7. Playwright 这个强大的自动化测试工具

    2024-06-09 07:46:02       4 阅读
  8. 安装 hbase(伪分布式)

    2024-06-09 07:46:02       4 阅读
  9. 密码学基本概念

    2024-06-09 07:46:02       4 阅读
  10. Python为项目中添加上彩色日志

    2024-06-09 07:46:02       5 阅读
  11. perl use HTTP::Server::Simple 轻量级 http server

    2024-06-09 07:46:02       3 阅读
  12. 面试 Redis 八股文十问十答第二期

    2024-06-09 07:46:02       3 阅读
  13. ASP.NET Core 中使用基本消息的 RabbitMQ 消费者

    2024-06-09 07:46:02       4 阅读