张家口百度免费做网站,制作网页怎样添加背景音乐,做哪个软件网站app,建筑设计机构一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
Problem - 1461D - Codeforces 二、解题报告
1、思路分析
我们发现每次分裂操作结果都是固定的
我们从初始序列分裂出两个确定的子序列#xff0c;两个确定的子序列又分裂出4个确定的子序列
那么也就是说…一、题目
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::pairint, 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::vectorint nums(N);std::vectori64 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::vectorstd::arrayint, 2 segs { { 0, N - 1 } }; segs.reserve(N);std::unordered_seti64 st;while (segs.size()) {std::vectorstd::arrayint, 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;elsestd::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;
}
