2024icpc武汉站邀请赛F.Custom-Made Clothes（交互题）

本文主要是介绍2024icpc武汉站邀请赛F.Custom-Made Clothes（交互题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\Huge{2024icpc武汉站邀请赛F.Custom-Made Clothes}$

文章目录

- 题意
- 思路
- 标程

题目链接：F. Custom-Made Clothes

题意

本题是一道交互题。

给出一个 $n\times n$ 的矩阵， $a_{i-1,j} \le a_{i,j},a_{i,j-1} \le g_{i,j}，(1\le a_{i,j}\le n^2)$ ， $1\le n \le 1000$ 。

题目首先给出 $n, k$ ，求矩阵中第k大的值，提供不超过 $50000$ 次查询。

题目有两种输出：

? i j x：表示查询 $a_{i,j} \le x$ 。返回 $0$ 或 $1$ 。
! x：表示输出结果，即 $x$ 为第 $k$ 大的值。

思路

通过观察发现，矩阵每行和每列都具有单调性，并且答案具有单调性。

因此我们可以二分答案，然后计算出当前答案为第几大的值。
在计算当前答案为第几大时，直接计算显然会超过交互次数，因此我们根据每行每列的单调性来计算。
对于二分过程中的 $mi d$ ，如果第 $i$ 行第 $j$ 列后面都大于 $mi d$ ，那么第 $i + 1... n$ 行第j列后都会大于 $mi d$ 。
优化后减少至少一半询问，则不会超过查询次数。

标程

bool query(int x, int y, int v) {cout << "? " << x << ' ' << y << ' ' << v << endl;fflush(stdout);int t; cin >> t;return t;
}void Solved() { int n, k; cin >> n >> k;k = n * n - k + 1;int l = 1, r = n * n, mid, res = 1;while(l <= r) {mid = l + r >> 1;int now = n, tmp = 0;for(int i = 1; i <= n; i ++ ) {while(now >= 1 && query(i, now, mid) == 0) now --;tmp += now;if(tmp >= k) break;}if(tmp >= k) r = mid - 1, res = mid;else l = mid + 1;}cout << "! " << res << endl;
}