二分+模拟,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
using PII = std::pair;
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 > N >> Q;
std::vector nums(N);
std::vector pre(N + 1);
for (int i = 0; i > 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> segs { { 0, N - 1 } }; segs.reserve(N);
std::unordered_set st;
while (segs.size()) {
std::vector<std::array> 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 > s;
if (st.count(1LL * s + P))
std::cout << "YES
";
else
std::cout <> _;
while (_ --)
solve();
return 0;
}