二分+模拟，CF1461D - Divide and Summarize
一、题目1、题目形貌
https://img-blog.csdnimg.cn/direct/7ee91ccddfe7410eaeefd2491f3234fd.png
2、输入输出
2.1输入
https://img-blog.csdnimg.cn/direct/91e9cd47e6fc4351a7d40748b202fcf1.png
2.2输出
https://img-blog.csdnimg.cn/direct/4a8875cde9974f5f981d934f8d3577ee.png
3、原题链接
Problem - 1461D - Codeforces
二、解题报告
1、思绪分析
我们发现每次分裂操作效果都是固定的
我们从初始序列分裂出两个确定的子序列，两个确定的子序列又分裂出4个确定的子序列
那么也就是说我们最终能够分裂出的子序列的数量是O(n)的
我们预处理出所有的子序列就预处理出了所有可以得到的和（当然这个和要在分裂的过程中维护）
而分裂要求我们得到小于即是mid的部门和大于的部门
以是我们须要对原序列进行排序，模拟的过程通过二分来找到分裂的位置
同时预处理前缀和以便每次分裂前都记录一下当前得到的值
值得注意的是nums = nums的时候阐明当前子序列是雷同的，我们无法继承向下分裂
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;
std::sort(nums.begin(), nums.end());
for (int i = 0; i < N; i ++ )
pre += nums + pre;
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& : segs) {
st.insert(pre - pre + P);
if (nums != nums) {
int mid = std::upper_bound(nums.begin(), nums.end(), (nums + nums) >> 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;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]