长乐集训 - NOI模拟赛（二十八）「订正未完成」

今日依旧三道集训队原题，无部分分，连续三次

真该问候搬题人他母亲大人

$\text{score：NULL rk：NULL}$

Problem A：Sasha And Circles

Problem B：Choosing Ads

题目描述

给定一个长度为 $n$ 的序列和一个整数 $p$。

有 $m$ 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 $p\%$ 的数。

输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 $\lfloor \frac{100}p \rfloor$

数据范围

对 $100\%$ 的数据，$n, m \le 1.5 \times 10^5, ~ 20 \le p \le 100$

题解

先考虑 $p = 51$ 的情况，很明显就是求区间众数

有一个经典区间众数套路，给数字 $i$ 一个数组 $c_i$，设当前众数 $p$，每次加一个数字 $t$，若该数字等于 $p$，则 $c_p ++$，反之则 $c_p –$，若删前 $c_p = 0$，则 $p = t$，同时 $c_p = 1$

这样子虽然没有计算每种数字的出现次数，但保留了相对数字个数大小的关系，毕竟若一个数的出现概率 $> 50\%$，则它必定会留到最后

那么现在考虑 $20 \le p \le 50$，则考虑存每个出现次数至少占 $p\%$ 的数，则它们最多 $5$ 个，在线段树上维护，每次加入一个数，若它与其中一个数相等则对应的数的 $c$ 加一，反之所有数的 $c$ 减一，然后用该数替代最终应当被替代的数，合并复杂度最多 $5 \times 5 = 25$，复杂度正确

复杂度 $O (nk^2 \log n)$，其中 $k = \lfloor \frac{100}p \rfloor$

代码

#include <iostream>
#include <cstdio>
#include <cstring>

#define lson root << 1
#define rson root << 1 | 1

using namespace std;

const int MAXN = 15e05 + 10;

int N, Q, P, m;
int ori[MAXN]= {0};

struct node {
	int a[6], cnt[6], n;
	void init () {
		memset (a, 0, sizeof (a));
		memset (cnt, 0, sizeof (cnt));
		n = 0;
	}
	void operator = (const node& p) {
		n = p.n;
		memcpy (a, p.a, sizeof (a));
		memcpy (cnt, p.cnt, sizeof (cnt));
	}
	node operator + (const node& p) const {
		node ret = p;
		for (int i = 1; i <= n; i ++) {
			bool in = false;
			for (int j = 1; j <= ret.n; j ++)
				if (a[i] == ret.a[j]) {
					ret.cnt[j] += cnt[i];
					in = true;
					break;
				}
			if (in) continue;
			if (ret.n < m) {
				ret.a[++ ret.n] = a[i];
				ret.cnt[ret.n] = cnt[i];
				continue;
			}
			int k = 0;
			for (int j = 1; j <= ret.n; j ++)
				if (k == 0 || ret.cnt[j] < ret.cnt[k])
					k = j;
			if (ret.cnt[k] > cnt[i]) {
				for (int j = 1; j <= ret.n; j ++) ret.cnt[j] -= cnt[i];
			}
			else {
				int tp = ret.cnt[k];
				ret.a[k] = a[i]; ret.cnt[k] = cnt[i] - ret.cnt[k];
				for (int j = 1; j <= ret.n; j ++)
					if (j != k)
						ret.cnt[j] -= tp;
			}
		}
		return ret;
	}
} ;
node T[MAXN << 2];
int lazy[MAXN << 2]= {0};
inline void setup (int root, int left, int right, int x) {
	T[root].a[T[root].n = 1] = x;
	T[root].cnt[1] = right - left + 1;
}
void build (int root, int left, int right) {
	T[root].init ();
	if (left == right) {
		setup (root, left, right, ori[left]);
		return ;
	}
	int mid = (left + right) >> 1;
	build (lson, left, mid); build (rson, mid + 1, right);
	T[root] = T[lson] + T[rson];
}
inline void pushdown (int root, int left, int right) {
	if (! lazy[root]) return ;
	int mid = (left + right) >> 1;
	setup (lson, left, mid, lazy[root]);
	setup (rson, mid + 1, right, lazy[root]);
	lazy[lson] = lazy[rson] = lazy[root];
	lazy[root] = 0;
}
void modify (int root, int left, int right, int L, int R, int x) {
	if (L <= left && right <= R) {
		setup (root, left, right, x);
		lazy[root] = x;
		return ;
	}
	pushdown (root, left, right);
	int mid = (left + right) >> 1;
	if (L <= mid) modify (lson, left, mid, L, R, x);
	if (R > mid) modify (rson, mid + 1, right, L, R, x);
	T[root] = T[lson] + T[rson];
}
node query (int root, int left, int right, int L, int R) {
	if (L <= left && right <= R) return T[root];
	pushdown (root, left, right);
	int mid = (left + right) >> 1;
	node ret; ret.init ();
	if (L <= mid) ret = ret + query (lson, left, mid, L, R);
	if (R > mid) ret = ret + query (rson, mid + 1, right, L, R);
	return ret;
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), Q = getnum (), P = getnum (); m = 100 / P;
	for (int i = 1; i <= N; i ++) ori[i] = getnum ();
	build (1, 1, N);
	for (int q = 1; q <= Q; q ++) {
		int type = getnum ();
		if (type == 1) {
			int l = getnum (), r = getnum (), id = getnum ();
			modify (1, 1, N, l, r, id);
		}
		else {
			int l = getnum (), r = getnum ();
			node ans = query (1, 1, N, l, r);
			printf ("%d", ans.n);
			for (int i = 1; i <= ans.n; i ++) printf (" %d", ans.a[i]);
			puts ("");
		}
	}

	return 0;
}

Problem C：Distance Sums

题目描述

给出 $n$ 个互不相同的数 $d_i$，表示树上的节点 $i$ 到其他所有点的距离和。

请判断是否存在这样一棵树，其中每条边的长度均为 $1$。若存在请输出一种方案，否则输出 -1。

数据范围

对 $100\%$ 的数据，$1 \le n \le 10^5, ~ 1 \le d_i \le 10^{12}$

题解

这题感觉是一直来做的比较水的。。

先给所有结点 $i$ 按 $d_i$ 排个序，将 $d$ 最小的看作根节点，那么显然子结点的 $d$ 比其祖先节点小

设结点 $u$ 子树大小 $s_u$，则考虑由 $u$ 走到其子结点 $v$ 时 $d$ 的增量，有 $\Delta d = n - 2s_v$

那么从排序后第 $n$ 个结点开始往上扫，每次将它与计算后与它相连的父结点连边，如若找不到父结点则无解

注意最后建完树要计算新建出的树的根节点的 $d$ 是否与输入所给相同

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;

int N;
pair<LL, int> d[MAXN];

int subsize[MAXN]= {0}, fa[MAXN]= {0};
void solve () {
	for (int i = N; i > 1; i --) {
		subsize[d[i].second] ++;
		int up = N - 2 * subsize[d[i].second];
		if (up < 0) { puts ("-1"); exit (0); }
		int p = lower_bound (d + 1, d + N + 1, make_pair (d[i].first - up, 0)) - d;
		if (p >= i || d[p].first != d[i].first - up) { puts ("-1"); exit (0); }
		fa[d[i].second] = d[p].second;
		subsize[d[p].second] += subsize[d[i].second];
	}
}

vector<int> G[MAXN];
LL dist[MAXN]= {0}, total = 0;
void DFS (int root) {
	total += dist[root];
	for (int i = 0; i < (int) G[root].size(); i ++) {
		int v = G[root][i];
		dist[v] = dist[root] + 1;
		DFS (v);
	}
}

inline LL getnum () {
	LL num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum ();
	for (int i = 1; i <= N; i ++) d[i].first = getnum (), d[i].second = i;
	sort (d + 1, d + N + 1);
	solve ();
	for (int i = 2; i <= N; i ++) G[fa[d[i].second]].push_back(d[i].second);
	DFS (d[1].second);
	if (total != d[1].first) { puts ("-1"); return 0; }
	for (int i = 2; i <= N; i ++)
		printf ("%d %d\n", fa[d[i].second], d[i].second);

	return 0;
}