• 周四. 12 月 12th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[WC2019] I 君的商店

admin

11 月 28, 2021

Problem

V 君、I 君、和 Y 君是好朋友。

I 君最近开了一家商店,商店里准备了 (n) 种物品(编号为 (0sim n-1) 中的整数),每种物品均有无限个可供出售,每种物品的单价是 (0) 或者 (1)

V 君想知道每个物品的价格,他已经通过某种超自然力量知道,这 (n) 个物品里,价格是 (1) 的物品恰好有奇数/偶数个,且 至少存在一个物品的价格是 (1)

然而, V 君并不想自己去问 I 君,他选择了这样一种方法:他准备了 (+infty) 的钱给 Y 君。然后让 Y 君帮他跑腿:每一次,他会给 Y 君指定两个非空物品 集合 (S,T)(同一个集合内的物品必须两两不同,即每种物品在每个集合类最多包含一个),Y 君会跑到商店,分别买下这两个集合的物品,把他们送回来,并告诉 V 君哪个集合的物品价格之和更高。但是,当 两集合价格之和相等 的时候,Y 君会按照 I 君的指示来回答 V 君。(博主解释一下:就相当于返回任意一种情况,可以是最坏情况)

带着很多物品跑腿是一个很累的事情,因此,我们定义一次跑腿的体力消耗是 (|S|+|T|)(|S|,|T|) 表示集合大小)。

你的任务是:写一个程序,帮助 V 君决定如何合理地让 Y 君跑腿,从而推算出每种物品的价值。Y 君的体力有限,你当然不能让他过于劳累,也即,你不能让他的总体力消耗超过某个预设的阈值 (m)

需要实现:

void find_price(int task_id, int n, K, int ans[]);

(m task\_id) 表示子任务标号,(n) 如上,(K) 表示价格为 (1) 的物品,若为奇数则 (=1),若为偶数则 (=0)

你可以调用

int query(int S[], int nS, int T[], int nT)

其中 ({m nS}=|S|)({m nT}=|T|)。如果 (S) 中价格总和更大,返回 (0);如果 (T) 中价格总和更大,返回 (1);否则返回任意值((0) 或者 (1) 均可)。

多组数据。

  • 子任务 1:(nle 5)(mle 100)
  • 子任务 2:(nle 10^3)(mle 10^6)
  • 子任务 3:(nle 10^5)(mle 100),保证 (forall i<j<k),若 (ans_i=ans_k),则必有 (ans_j=ans_i)
  • 子任务 4:(nle 10^4)(mle 2 imes 10^5)
  • 子任务 5:(nle 5 imes 10^4)(mle 350100)
  • 子任务 6:(nle 10^5)(mle 500100)

Sol

博主花了不少时间才切此题,在这里写一写“心动历程”~~

第一下想到要先找一个 (1),然后拿这个 (1) 做事嘿嘿…

有一个很粗暴的想法:分治一下,假设区间 ([l,r]) 中含有 (1),然后选取一个 (mid),判断 ([l,mid])([mid+1,r]) 中谁的 (1) 多,每次往多的部分走,最后总能找到 (1)。这样的代价约为 (2n)

(1) 能做什么?能判断出来一个集合 (>1),或者 (<1)。但如何知道其是否 (=1)

非常悲观的一件事是:我们无法简单通过比较大小得知。即使我们拥有无穷多的 (1),通过二分,每次取出来 (a)(1),与 (S) 比较,最终停止,只能推断出 ({m val}(S)in{b,b+1}),想确定其是 (b) 还是 (b+1) 我们无能为力。

但,注意到这样的一件事:({m val}(S)+{m val}(T)in{c,c+1,c+2})(同向不等式的合并),({m val}(Scup T)in{d,d+1}),发现分开查询和合并查询可以推断出一种不存在的情况。这并没有什么用,但至少启迪我们 要利用集合间的关系去寻找答案,而不是去揣摩它真正的取值是多少。

想象一下 (n=2),你只有 ({1,x})。发现 (x) 的取值光靠查询是查不出来的,所以出题人良心地给了 (K),根据 (1) 数量的奇偶性推出来 (x)

想象一下 (n=3),你只有 ({1,x,y}),这次奇偶性不能直接救你,你必须至少知道 (x)(y) 中至少一个的 真实取值,最后才能利用奇偶性得出答案。幸运的是,我们可以做到!

构造两次查询:(({x},{y}))(({1},{x,y}))。前者知道 (x)(y) 的大小关系,后者若返回 (0),则 (x)(y)必然有一个 (0),若返回 (1)(x)(y)必然有一个 (1)

假设 (xle y),若含有 (0),则 (x) 必为 (0);若含有 (1),则 (y) 必为 (1)

可喜可贺!我们找出了一个通用的做法:每次找出来两个未知情况的数 (x,y),每次花费 (5) 的代价确定二者中的一个数的真正取值。未知的数字有 (n-1) 个,我们需要使用这个方法 (n-2) 次,直到剩余最后一个不知道答案的数字,再利用奇偶性就能得到答案了!这部分操作次数约为 (5n)

加上找 (1),总共需要 (7n) 次左右。发现能过掉子任务 1、2、4、5,加起来有 57 Pts。这个 子任务 3 是咋回事啊?看起来很需要二分!

通过比较 (0) 号和 (n-1) 号元素可以得到 (1) 在哪里,以及序列的顺序((0ightarrow 1) 或者 (1ightarrow 0))。这里假设顺序 (0ightarrow 1)。同样我们可以通过 (({1},{ans_x,ans_{x+1}})),由于 (ans_xle ans_{x+1}),我们不仅能知道谁为 (0) 谁为 (1),而且还能知道接下来二分的方向。最后仍然不确定一个元素,根据奇偶性查出来即可。操作次数约为 (3log n)

此时就有 69 Pts 了,我们应该选择跑路继续想一想 (7n) 做法的瓶颈,如果我们能够去掉那个 (2n) 的找 (1) 过程就好了。可不可以不需要 (1)?把 (({1},{x,y})) 使用 (({a},{x,y})) 代替((a) 是随便挑的,可能为 (0),可能为 (1))?

我们来分析一下 (({0},{x,y})) 的影响(也就是我们把 (0) 当成 (1) 来看,结果的偏差),这里仍然让 (xle y)。如果返回值为 (0),我们会把 (x)(0),这一步在换成 (0) 也没有影响;但如果返回值为 (1),我们会把 (y) 当成 (1),但事实上 (y) 也可以为 (0) 了。

接下来的想法就很巧妙了!我们假设查询的结果为 (1),仍然把 (y) 看成 (1),并且将 (a) 换成 (y),往后继续操作。把曾经的 (a) 按照顺序构成序列,发现它们按照 真实值 是单调的!

这值得我们惊呼!最后再对着这个序列做 子任务 3,把真实值求出来,是不是就只剩下一个数字不确定了?利用奇偶性!做完了!总操作次数约为 (5n+3log n)

实现细节请诸位小心,别像我一样过了后 5 个 subtask 挂了 1。

#include <bits/stdc++.h>
#include "shop.h"
#define pb push_back
const int N = 5e5 + 5;
int S[N], T[N];
int qry1(int a, int b) {
	S[0] = a, T[0] = b;
	return query(S, 1, T, 1);
}
int qry2(int a, int b, int c) {
	S[0] = a, T[0] = b, T[1] = c;
	return query(S, 1, T, 2);
}
std::vector<int> vec;
void find_price(int task_id, int n, int K, int ans[]) {
	vec.clear();
	if (task_id == 3) {
		int now = qry1(0, n - 1) ? n - 1 : 0;
		ans[now] = 1;
		for (int i = 0; i < n; i++)
			if (i != now) vec.pb(i);
		if (now == 0) std::reverse(vec.begin(), vec.end());
		int l = 0, r = vec.size() - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (qry2(now, vec[mid], vec[mid + 1])) r = mid; else l = mid + 1;
		}
		for (int i = 0; i < l; i++) ans[vec[i]] = 0;
		for (int i = l + 1; i < n - 1; i++) ans[vec[i]] = 1;
		int sum = n - l - 1;
		ans[vec[l]] = (sum & 1) ^ K;
	} else {
		int now = 0, tmp = 0;
		for (int i = 1; i < n; i++) {
			int x = tmp, y = i;
			if (!qry1(x, y)) std::swap(x, y);
			if (qry2(now, x, y)) {
				ans[y] = 1; tmp = x;
				vec.pb(now), now = y;
			} else {
				ans[x] = 0; tmp = y;
			}
		}
		if (qry1(now, tmp)) vec.pb(now), now = tmp;
		ans[now] = 1;
		for (int i = 1; i < vec.size(); i++)
			if (vec[i] == 0) { vec.erase(vec.begin() + i); break; }
		int l = 0, r = vec.size() - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (qry2(now, vec[mid], vec[mid + 1])) r = mid; else l = mid + 1;
		}
		for (int i = 0; i < l; i++) ans[vec[i]] = 0;
		for (int i = l + 1; i < vec.size(); i++) ans[vec[i]] = 1;
		if (tmp != now) {
			int x = vec[l], y = tmp;
			if (x != y) {
				if (!qry1(x, y)) std::swap(x, y);
				if (qry2(now, x, y)) ans[y] = 1, tmp = x;
				else ans[x] = 0, tmp = y;
			}
		}
		else if (vec.size()) tmp = vec[l];
		int sum = 0;
		for (int i = 0; i < n; i++)
			if (i != tmp) sum += ans[i];
		ans[tmp] = (sum & 1) ^ K;
	}
}

发表回复