首页 > 其他分享 >P5208 [WC2019] I 君的商店 题解

P5208 [WC2019] I 君的商店 题解

时间：2024-01-29 19:34:03浏览次数：35  
标签：query2 P5208 题解 mid int vec ans query WC2019

第一道黑题，发个题解。

很好玩的一道交互题。

题意

  • 有一个长为 \(n\) 的 01 字符串，保证至少有一个 1，且已知 1 的数量的奇偶性。

  • 每次可以询问两个下标集合，返回哪个下标集合中 1 的个数更多（相同则可能返回其中任意的一个）。

  • 求该字符串，查询次数有限。

题解

我们约定 a,b,c 等字母表示下标，\(ans_a\) 表示 \(a\) 处的值。

Subtask 3

我们首先注意到这个特殊的 subtask 3：\(N\leq 10^5,M=100\)，保证序列单调（不降或不增）。

这意味着这个序列一定是形如 0000…1111 或者 1111…0000 这样的形式。

我们很自然的想到可以二分出 0 和 1 的分界点，可是该如何二分呢？

首先虽然原题说可以让我们查询任意长度的数列，但是只有以下两种查询有用，我们把它记作 query1 和 query2 。

  • query1(a,b) : 只查询 a 和 b 两个位置的量（query({a},1,{b},1) ) ，这样可以确定 a 与 b 之间的相对大小关系（若返回 0 ，则 \(ans_a\ge ans_b\) ; 否则 \(ans_a\le ans_b\) ) ;
  • query2(a,b,c) :查询两个数{a,b} 和 c 的关系（query({a,b},2,{c},1))，这样可以确定 {a,b} 中有多少个 1。

既然序列保证单调并且一定至少有一个 1，那么我们就可以先进行一次 query1(0,n-1) 判断序列是单调不增还是不降（若返回 0 ，那么一定单调不增（为 1111…0000 形式）；否则一定单调不降（为0000…1111 形式））。为了叙述方便，我们认为它单调不增。

接下来确定了 1 的位置，我们就可以愉快的二分了！我们认为 l 是最右且必定为 1 的位置，r 为最左且必定为 0 的位置 -2（否则会死循环）。

记now 为必定为 1 的位置，进行query2(mid,mid+1,now) ，如果返回 1 ,那么 \(ans_{mid},ans_{mid+1}\) 中至多有一个为 1，又因为单调不增，所以 \(ans_{mid+1}\) 一定为 0。如果返回 0，那么\(ans_{mid},ans_{mid+1}\) 中至少有一个为 1，又因为单调不增，所以 \(ans_{mid}\) 一定为 1。

这样我们可以二分出除了最中间的分界点以外的所有点，只有 \(ans_{l+1}\) 不知道。这时通过题目给的我们的奇偶性判断即可。

二分每次消耗 3 个体力，一开始消耗 2 点，最多消耗体力值为\(2+3\times\log_2 10^5 \approx 52 < 100\) ，可以通过。

Code：（这个代码不好写，调试技巧)

#include<bit/stdc++.h>

int query(int *S, int nS, int *T, int nT);
int query1(int a, int b) {
	int tmp1[1] = {a}, tmp2[1] = {b};
	return query(tmp1, 1, tmp2, 1);
}
int query2(int a, int b, int c) {
	int tmp1[2] = {a, b}, tmp2[1] = {c};
	return query(tmp1, 2, tmp2, 1);
}

vector<int>vec;
void find_price(int task_id, int n, int k, int ans[]) {
	vec.clear();
	if (task_id == 3||n<=2) {
		int bigger = query1(0, n - 1);
		int now = bigger ? (n - 1) : 0;
		ans[now] = 1;
		for (int i = 0; i < n; i++) vec.push_back(i);
		if (now)
			reverse(vec.begin(), vec.end()); // 从大到小 111...000
		int l = 0, r = n - 1;
		while (l < r) { // 3*lg(1e5)=50
			int mid = (l + r + 1) >> 1;
			if (mid + 1 < n && query2(vec[mid], vec[mid + 1], now) ==
				1) { // 最少 1 个为 1 因为单调不增，所以ansmid=1
				r = mid - 1;              // 最左且必定为 0 的位置-2
			} else
				l = mid; // l 表示最右且必定为 1 的位置
			// cout<<l<<" "<<r<<endl;
		}
		for (int i = 0; i <= l; i++)
			ans[vec[i]] = 1;
		ans[vec[l + 1]] = (l&1)==k ? 0 : 1;
		// for(int i=0;i<n;i++)cout<<ans[i]<<" ";
		return;
	}
}

Subtask 1 2 4 5

首先我们发现对于两个数 x,y (进行一次 query1 保证 \(ans_x\le ans_y\))，把他们与 1 比较（执行query2({x,y},2,{1},1))，如果返回 0 ，那么 \(ans_y=1\) ;否则 \(ans_x=0\) 。这样我们每次花 5 个代价就可以确定一位。

证明显然。

所以我们就可以先找到 1 个 1 , 然后执行上面的操作直到只剩 1 个数，用奇偶性判断即可。

那么该如何找到 1 呢？

我们可以考虑二分的思想，每次查询 \([l,mid]\) 和 \([mid+1,r]\) 哪边 1 多，因为至少有一个 1，所以最后一定能找到。代价约为 \(2n\)。

总代价为 \(5n+2n=7n\)。

Subtask 6

我们可以优化找 1 的过程：具体的说，我们不需要一开始找到一个 1 , 随便找一个数 m 进行上面的操作：

对于两个数 x,y (进行一次 query1 保证 \(ans_x\le ans_y\))，把他们与 m 比较（执行query2({x,y},2,{m},1))，如果返回 1 ，那么 \(ans_x=0\) ;否则 : 若 \(ans_m=1\), 则 \(ans_y\) 一定等于 \(1\),所以一定有 \(ans_y \ge ans_m\)。

我们用 y 替换 m，记录这个操作，并继续进行。

最终我们会得到一堆 0 和一条链，记录了这些数相对的大小情况。另外还剩下 1 个数，和链的最大值比较一次得到一个 1,最后在链上按照 Subtask 3 的规则二分即可。

总代价 \(5n+\mathcal O(\log_2{n})\)。

Code:AC记录

// WC2019 I君的游戏
#include <bits/stdc++.h>
using namespace std;
int query(int *S, int nS, int *T, int nT);
int query1(int a, int b) {
	int tmp1[1] = {a}, tmp2[1] = {b};
	return query(tmp1, 1, tmp2, 1);
}
int query2(int a, int b, int c) {
	int tmp1[2] = {a, b}, tmp2[1] = {c};
	return query(tmp1, 2, tmp2, 1);
}
#define MAXX 1145141919
vector<int> vec;
void find_price(int task_id, int n, int k, int ans[]) {
	vec.clear();
	if (task_id == 3||n<=2) {
		int bigger = query1(0, n - 1);
		int now = bigger ? (n - 1) : 0;
		ans[now] = 1;
		for (int i = 0; i < n; i++) vec.push_back(i);
		if (now)reverse(vec.begin(), vec.end());
		int l = 0, r = n - 1;
		while (l < r) { 
			int mid = (l + r + 1) >> 1;
			if (mid + 1 < n && query2(vec[mid], vec[mid + 1], now) ==
				1) { 
				r = mid - 1;              
			} else
				l = mid; 
		}
		for (int i = 0; i <= l; i++)ans[vec[i]] = 1;
		ans[vec[l + 1]] = (l + k ^ 1) & 1;
		return;
	}
	int z = 0, t, x = 1, y, s;
	for (int i = 2; i < n; i++) {
		y = i;
		t = query1(x, y);
		if (!t) swap(x, y);
		t = query2(x, y, z);
		if (t) {
			ans[x] = 0;
			x = y;
		} else {
			vec.push_back(z);
			z = y;
		}
	}
	t = query1(x, z);if (!t)swap(x, z);
	ans[z] = 1;
	if (!vec.size()) {
		ans[x] = k ^ 1;
		return;
	}
	vec.push_back(z);
	reverse(vec.begin(), vec.end()); 
	int nnnn = vec.size();
	int l = 0, r = nnnn - 1;
	while (l < r) { 
		int mid = (l + r + 1) >> 1;
		if (mid + 1 < nnnn && query2(vec[mid], vec[mid + 1], z) ==
			0) { 
			l=mid ;                
		} else
			r=mid-1;
	}
	for (int i = 0; i <= l; i++)
		ans[vec[i]] = 1;
	int c = vec[l + 1];
	if(l+1==vec.size())goto AAA;//可能会越界
	if (query1(c, x))
		swap(c, x);
	if (!query2(c, x, z)) {
		ans[c] = 1;
		l++;
	} else {
		ans[x] = 0;
		x = c;
	}
AAA:	ans[x] = (l + 1 ^ k) & 1;
	return;
}

完结撒花！

标签：query2,P5208,题解,mid,int,vec,ans,query,WC2019
From： https://www.cnblogs.com/wang-yishan/p/17995182/P5208_tijie

相关文章

  • 题解 [ABC338D] Island Tour
    【洛谷博客】被降智的一道简单题。题意\(n\)个岛屿，第\(i\)座桥连接\(i\)和\(i+1\)（第\(N\)座桥连接着\(1\)和\(N\)）。有一条长度为\(M\)的旅游序列\(X\)，你需要按照顺序依次经过这些点，选择断掉一座桥使得旅游经过的桥最少。分析设断掉第\(i\)座桥会因为绕行增......
  • P10114 [LMXOI Round 1] Size 题解
    题目链接：[LMXOIRound1]Size挺有意思的诈骗题，其实这类题都喜欢批一个外壳，例如数据范围提示之类的。记得以前遇到的很多诈骗题，有一道cf的高分题，问的是区间出现次数的次数\(mex\)，这玩意一开始感觉好难，出现次数还简单，还要考虑次数的次数，所以带修莫队的时候，一直没法确定怎么解决......
  • NOI 2017 蚯蚓排队 题解
    Meaning给定一些数字，对它们进行首尾相接和断开两种操作。对于每次询问，求对于每个数字，其后长度一定的数字串在给定数字串中出现的次数，并给出这些次数之积。Soultion对于每次首尾相接或断开的操作，如果直接对断点或合点两侧的整个数字串进行操作，时间复杂度不可接受。由于每次查询......
  • CF1764H Doremy's Paint 2 题解
    题目链接：CF或者洛谷高分题，感觉挺有意思的题，值得一提的是这个题的\(1\)和\(3\)版本却是两个基础题。一开始以为跟这道差不多：P8512[YnoiEasyRound2021]TEST_152题解。后面重新读了一下发现一个有趣的点：也就是是说操作的\(val\)并不太好搞了，如果\(val\)确定就基......
  • P5400 [CTS2019] 随机立方体 题解
    题目链接点击打开链接题目解法参考cmd的博客好复杂的推式子题，而且三维的对我来说好难想象/ll首先二项式反演，把恰好\(k\)个变成求至少\(i\)个的方案数令极大格子有至少\(i\)个的方案数为\(f_i\)，\(R=\min\{n,m,k\}\)特判掉\(k>R\)答案为\(0\)根据二项式反演，答案......
  • P1438 无聊的数列 题解
    背景看到题解都是差分，竟然还有建两颗线段树和二阶差分的大佬。我感到不理解，很不理解。题目正解本题正解很明显就是：线段树是的，你没有看错，就只有线段树。很显然我们直接按照线段树板题写就可以了，维护题目需要维护的，注意到只有单点查询，所以我们根本不需要维护区间和，对于区间来......
  • 洛谷P10114题解
    题意简述给定一个长度为\(n\)的序列，求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}{((d_i\oplusd_j)+(d_i\otimesd_j))}\)。思维路径观察数据范围可以发现\(n\le2\times10^6\)而\(\sum\limitsd_i\le5\times10^7\)，这说明\(d\)数组中的重复值较多，直接枚举数值可......
  • 洛谷题解-[ABC325E] Our clients, please wait a moment
    https://www.luogu.com.cn/problem/AT_abc325_e题目描述ある国には都市がNNN個あります。あなたは、都市111にある営業所から000個以上の都市を経由して都市NNNにある訪問先へ移動しようとしています。移動手段は社用車と電車の222種類があります。都市......
  • 洛谷P10115题解
    题意简述给定一个括号序列，求整个序列的美丽值最大。思维路径见到序列和权值，很容易想到需要用DP。我们定义\(f[i][j]\)表示第\(1\)到\(i\)个括号产生的美丽值最大值，其中\(j=0\)表示第\(i\)个括号本身不参与美丽值贡献，\(j=1\)表示第\(i\)个括号本身参与美丽值贡献......
  • B3929 [GESP202312 五级] 小杨的幸运数 题解
    因为一些众所周知的原因，不放代码。分享一种考场思路：\(a\le10^7\)，顺序查找肯定会废，所以可以用一种类似埃氏筛的方法将所有满足条件的数标记一下，并将其加入一个答案数组\(a\)当中。然后每次查询只需要用lower_bound函数二分查找一下，假如找到了第\(i\)个：\(a_i=x\),直接......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99