本文主要是介绍思维+二分，CF 1019B - The hat，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
1019B - The hat
二、解题报告
1、思路分析
一个很关键的信息就是 相邻两个人拿到的数相差1
亦即相邻两个人拿到数字的奇偶性不同
如果 n 不为 4 的倍数，那么n / 2为奇数，那么 a[i] 和 a[i + n / 2] 奇偶性一定不同，我们进行特判即可
我们定义函数 f(i) = a[i] - a[i + n / 2]. g(i) = a[i] - a[i - n / 2]
我们发现如果a[i] 不等 a[i + n / 2]，那么f(i) 和 g(i + n / 2)符号一定不同
而由于相邻两个人数字相差1，故 i 每变化1，其f / g值最多变化-2，0， 2，也就是说两个符号不同的值之间一定存在我们所要求的解
那么我们先提前求出f(1) 和 g(1 + n / 2)，然后不断二分即可
2、复杂度
时间复杂度： O(2 logn + 2)空间复杂度：O(1)
3、代码详解
#include <bits/stdc++.h>using i64 = long long;
using i32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 998'244'353;int query(int x) {std::cout << "? " << x << std::endl;int res;std::cin >> res;return res;
}void solve() {int n;std::cin >> n;if (n & 2) {std::cout << "! -1" << std::endl;return;}int l = query(1), r = query(1 + n / 2);int f = l == r ? 0 : (l < r ? 1 : -1);if (f == 0) {std::cout << "! " << 1 << std::endl;return;}int lo = 1, hi = n / 2 + 1;while (lo < hi) {int x = lo + hi >> 1;l = query(x), r = query(x + n / 2);int nf = l == r ? 0 : (l < r ? 1 : -1);if (nf == 0) {std::cout << "! " << x << std::endl;return;}if (nf == f)lo = x + 1;elsehi = x;}std::cout << "! " << -1 << std::endl;
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
}();int main () {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifint T = 1;// std::cin >> T;while (T --) {solve();}return 0;
}这篇关于思维+二分，CF 1019B - The hat的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
