思维+构造，CF 1936A - Bitwise Operation Wizard

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1936A - Bitwise Operation Wizard

---

二、解题报告

1、思路分析

考虑 假设 n - 1 的 二进制位长为 b，我们能构造 2^b - 1 吗？

显然可以

假如我们最终要得到 p[a] ^ p[b] = 2^b - 1

我们在 O(3N) 内找到 一个比较特殊的 <a, b> 的下标吗？

query(x, x, y, y) 支持我们比较 x, y 的大小

那么：

我们显然可以在 O(N) 内找到 n - 1

对于 n - 1 而言，我们又可以 O(N) 找到 所有 满足 n - 1 | x = 2^b - 1 的 x 的下标

O(N)选出的这些值里面的最小值 mi，它一定满足 mi ^ n - 1 = 2^b - 1

2、复杂度

时间复杂度： O(3(N - 1))空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;const int P = 1'000'000'007;char query(int a, int b, int c, int d) {std::cout << "? " << a << ' ' << b << ' ' << c << ' ' << d << std::endl;char res;std::cin >> res;return res;
}void solve() {int n;std::cin >> n;int mai = 0;for (int i = 1; i < n; ++ i) {if (query(mai, mai, i, i) == '<') {mai = i;}}std::vector<int> vj{0};int maj = 0;for (int i = 1; i < n; ++ i) {char res = query(maj, mai, i, mai);if (res == '<') {maj = i;vj.clear();vj.push_back(maj);} else if(res == '=') {vj.push_back(i);}}int mij = vj[0];for (int i = 1; i < vj.size(); ++ i) {if (query(mij, mij, vj[i], vj[i]) == '>') {mij = vj[i];}}std::cout << "! " << mai << ' ' << mij << std::endl;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint cur = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - cur << '\n';
#endifreturn 0;
}