专栏首页数据结构与算法codeforces415D. Glad to see you!

codeforces415D. Glad to see you!

题意

交互题。

有$k$个值域为$[1, n]$的数。

请在不超过$60$次询问内找出其中的两个数。

每次询问形式为1 x y

交互库会返回$|x - a| <= |y - b| ? "TAK" : "NIE"$

其中$a, b$分别是使得$|x - a|,|y - b|$最小的且存在于序列中的数。

Sol

若询问$x, x + 1$的结果为“TAK”,说明在$1, x$内一定有解。

我们可以不断这样二分下去。直到找到一个解。

再在$1, x - 1$和$x +1, N$中重复以上操作,找到另一组解。

#include<iostream>
using namespace std;
int N, K;
string Yes = "TAK";
int check(int x) {
    if(x + 1 > N) return 1;
    printf("1 %d %d\n", x, x + 1);
    fflush(stdout);
    string buf;
    cin >> buf;
    return buf == Yes ? 1 : 0;
}
int Query(int l, int r) {
    int ans = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N >> K;
    int a1 = Query(1, N);
    int a2 = Query(1, a1 - 1);
    int a3 = Query(a1 + 1, N);
    printf("2 %d %d", a1, a2 == -1 ? a3 : a2);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)

    答案=任意一种方案 - 至少有\(1\)位为\(1\)的方案 + 至少有两位为\(1\)的方案 - 至少有三位为\(1\)的方案

    attack
  • HDU4352 XHXJ's LIS(LIS 状压)

    刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

    attack
  • BZOJ3509: [CodeChef] COUNTARI(生成函数 分块)

    发现 ,那么有一种暴力思路是枚举j,对于之前出现过的数构造一个生成函数,对于之后出现过的数构造一个生成函数,求一下第 项的值。复杂度

    attack
  • cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)

    答案=任意一种方案 - 至少有\(1\)位为\(1\)的方案 + 至少有两位为\(1\)的方案 - 至少有三位为\(1\)的方案

    attack
  • 【每日算法Day 63】LeetCode 第 179 场周赛题解

    https://leetcode-cn.com/problems/generate-a-string-with-characters-that-have-odd...

    godweiyang
  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • 查找算法

    查找,作为应用最为广泛和最基础的算法思想之一,几乎在所有应用程序之中都有它的思想身影。往细一点说:查找可以有 顺序查找、二分查找、散列表查找,下面依次来看一下这...

    指点
  • [PHP] 算法-二位有序数组中查找的PHP实现

    陶士涵
  • 分治法(Divide-and-Conquer Algorithm)经典例子分析

    上一篇文章里给大家介绍了归并排序,今天首先给大家带来同样运用分治法来解决问题的快速排序。

    用户1621951
  • 动态规划算法举例解析(最大收益和最小损失选择)

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可

扫码关注云+社区

领取腾讯云代金券