Всем привет, добро пожаловать в тему codeforces.
Тема, которую мы сегодня выбрали, это вопрос D из 1461 сеансов, этот вопрос сдали 3702 человека, что является средним по сложности. Это несложно, а также очень подходит для того, чтобы ученики тренировали руки. Кроме того, этосовершенно новая идеяЭто не появлялось в наших предыдущих статьях, я думаю, это вдохновит вас.
Ссылка на сайт:codeforces.com/contest/146…
Без дальнейших церемоний, давайте начнем.
смысл названия
Нам дан массив из n положительных целых чисел, после того, как мы сможем выполнить некоторые операции над этим массивом, мы можемПусть сумма элементов в массиве будет числом, которое мы хотим.
Наша работа над массивом разделена на три шага.Первый шаг заключается в том, что мы сначала вычисляем промежуточное значение середины массива. Определение середины здесь не является ни медианой, ни средним значением, а средним значением максимального и минимального значений. То есть mid = (min + max)/2.
Получив мид, мыРазделите массив на две части в зависимости от размера элементов в массиве. Делим элементы меньше или равные середине на первую часть, а элементы больше середины делим на вторую часть. Это эквивалентно преобразованию исходного большого массива в два разных небольших массива.
Теперь у нас есть всего q запросов, каждый из которых содержит целое число k. Мы хотим, чтобы программа дала нам, можем ли мы сделать сумму элементов результирующего массива равной k с помощью вышеуказанных операций.
Если да, выведите Yes, иначе выведите No.
Образец
Сначала введите целое число t, которое представляет количество групп тестовых данных ().
Введите два целых числа n и q для каждого набора данных, где n — количество элементов в массиве, а q — количество запросов (). Затем введите строку из n целых чисел во второй строке, каждое из которых, оба.
Каждая из следующих q строк содержит целое число, представляющее число k, которое мы запрашиваем (), чтобы сумма всех n и q не превышала.
Для каждого запроса мы выводим Да или Нет, чтобы указать, может ли он быть выполнен.
В первом примере массив, с которого мы начинаем, равен[1, 2, 3, 4, 5]. При первом выполнении операции получаем mid=(1+5)/2=3. Таким образом, массив делится на[1, 2, 3]и[4, 5]. за[1, 2, 3]Двигаясь дальше, мы можем получить mid = (1 + 3) / 2 = 2, поэтому массив можно разделить на[1, 2]и[3].[1, 2]окончательно можно разделить на[1]и[2].
Мы можем найти, что k, которое можно найти, равно:[1, 2, 3, 4, 5, 6, 9, 15].
отвечать
Эта проблема не очень сложна, и решение относительно ясно.
Легко обнаружить, что операции над массивами на самом деле фиксированы, потому чтоОпределяются максимальное и минимальное значения в массиве. Нам просто нужно отсортировать массив побинарный поискРазделение массива может быть сделано легко. Точно так же для суммирования массивов нам не нужно использовать циклы для операций накопления, которые легко сделать с префиксными суммами.
Так что единственная трудность этого вопроса состоит в том, как судить о том, можно ли найти искомое k.На самом деле это не сложно, нам нужно только поставить егокак поисковый вопрос, чтобы найти все k, до которых можно добраться. Это базовый глубокий поиск, и он не слишком сложен.
bool examine(int l, int r, int k) {
if (l == r) return (tot[r] - tot[l-1] == k);
// 如果[l, r]的区间和已经小于k了，那么就没必要去考虑继续拆分了
if (l > r || tot[r] - tot[l-1] < k) {
return false;
}
if (tot[r] - tot[l-1] == k) {
return true;
}
// 中间值就是首尾的均值
int m = (nums[l] + nums[r]) / 2;
// 二分查找到下标
int md = binary_search(l, r+1, m);
if (md == r) return false;
return examine(l, md, k) | examine(md+1, r, k);
}
Этот кусок логики сам по себе написать несложно, но когда мы его запишем, мы обнаружим, что AC по-прежнему нельзя использовать, и он истечет по тайм-ауту. Я долго думал об этом и, наконец, понял, в чем проблема.
проблема иДело не в том, что сложность нашего поиска здесь слишком высока, а в том, что количество поисков слишком велико.. q В лучшем случае будет, а сложность каждого поиска. Поскольку наши поисковые слои, плюс получившийся, поэтому предельная сложность, где n равно, это значение приблизительно, плюс некоторые другие расходы, так что я застрял.
Для решения этой проблемы мы ввелиАвтономный механизм.
Офлайн-онлайн здесь хорошо понимается, так называемый онлайн-запрос означает, что каждый раз, когда мы получаем запрос, мы опрашиваем его один раз, а затем возвращаем результат. В офлайне наоборот, мыСначала запрашивайте все запросы, а затем возвращайте по одному. Многие студенты могут быть очень удивлены, разве это не одно и то же? Только порядок другой.
Большую часть времени это то же самое,Но иногда наш автономный запрос может выполняться в пакетном режиме.. Например, в этом вопросе мы можем через одну рекурсию узнать все k, которые могут быть сформированы за один раз, а затем сохранить их в наборе. После этого нам нужно только проверить, существует ли набор по входному запросу, потому что скорость запроса набора намного быстрее, чем поиск через рекурсию. Это эквивалентно сжатию q раз запросов в один, что экономит время работы, и в определенной степени это также алгоритм пространства-в-времени.
Давайте посмотрим на код для более подробной информации:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
const int N=100050;
const long long Mod=1000000007;
using namespace std;
int nums[N];
long long tot[N];
set<long long> ans;
int binary_search(int l, int r, int val) {
while (r - l > 1) {
if (nums[mid] <= val) {
l = mid;
}else {
r = mid;
}
}
return l;
}
// 离线查询，一次把所有能构成的k放入set当中
void prepare_ans(int l, int r) {
if (l > r) return ;
if (l == r) {
ans.insert(nums[l]);
return ;
}
ans.insert(tot[r] - tot[l-1]);
int m = (nums[l] + nums[r]) / 2;
int md = binary_search(l, r+1, m);
if (md == r) return ;
prepare_ans(l, md);
prepare_ans(md+1, r);
}
int main() {
int t;
scanf("%d", &t);
rep(z, 0, t) {
ans.clear();
MEM(tot, 0);
int n, q;
scanf("%d %d", &n, &q);
rep(i, 1, n+1) {
scanf("%d", &nums[i]);
}
sort(nums+1, nums+n+1);
rep(i, 1, n+1) {
tot[i] = tot[i-1] + nums[i];
}
prepare_ans(1, n);
rep(i, 0, q) {
int k;
scanf("%d", &k);
// 真正请求起来的时候，我们只需要在set里找即可
if (ans.find(k) != ans.end()) {
puts("Yes");
}else {
puts("No");
}
}
}
return 0;
}
Онлайн в оффлайн — очень распространенный навык в вопросах соревнований., который часто используется для решения очень больших проблем с запросами. Напрямую сказать не сложно, но немного хлопотно, если не знаешь и хочешь разобраться сам. Если у вас есть время, лучше всего испытать это на себе с кодом.
Сегодняшняя проблема алгоритма обсуждается здесь, и я искренне надеюсь, что каждый будет получать что-то каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)