Решение задачи "Особые элементы" с Codeforces

С пояснением   Просмотров: 17


Обратите внимание на нестандартное ограничение по памяти в этой задаче.

С целью отсечения эффективных решений от неэффективных в этой задаче ограничение времени довольно строгое. Предпочтите использование компилируемых статически типизированных языков (например, C++). Если используете Python, то отсылайте решения на PyPy. Постарайтесь написать в самом деле эффективное решение.

Задан массив a=[a1,a2,…,an] (1≤ai≤n). Его элемент ai называется особым, если существует такая пара индексов l и r (1≤l
Выведите количество особых элементов заданного массива a.

Например, если n=9 и a=[3,1,4,1,5,9,2,6,5], то ответ равен 5:

a3=4 — особый элемент, так как a3=4=a1+a2=3+1;
a5=5 — особый элемент, так как a5=5=a2+a3=1+4;
a6=9 — особый элемент, так как a6=9=a1+a2+a3+a4=3+1+4+1;
a8=6 — особый элемент, так как a8=6=a2+a3+a4=1+4+1;
a9=5 — особый элемент, так как a9=5=a2+a3=1+4.
Обратите внимание, что среди элементов массива a могут быть равные — если несколько элементов равны и являются особыми, то все они должны быть посчитаны в ответе.

Код

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		vector<int> cnt(n + 1);
		int ans = 0;
		for (auto &it : a) {
			cin >> it;
			++cnt[it];
		}
		for (int l = 0; l < n; ++l) {
			int sum = 0;
			for (int r = l; r < n; ++r) {
				sum += a[r];
				if (l == r) continue;
				if (sum <= n) {
					ans += cnt[sum];
					cnt[sum] = 0;
				}
			}
		}
		cout << ans << endl;
	}
}

         

 Администратор Photo Автор: Администратор


Предполагаемое решение в этой задаче работает за O(n * n) времени и O(n) памяти. Сначала давайте посчитаем cnt[i] для каждого i от 1 до n, где cnt[i] равно количеству вхождений i в a. Эта часть может быть реализована за O(n).

Затем давайте переберем все отрезки a длины хотя бы 2, поддерживая сумму текущего отрезка sum. Мы можем заметить, что нам не нужны суммы больше n, потому что все элементы не превосходят n. Таким образом, если текущая сумма не превосходит n, добавим cnt[sum] к ответу и присвоим cnt[sum]:=0, чтобы предотвратить учет одинаковых элементов несколько раз. Эта часть может быть реализована за O(n * n).

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться