D. Rocket

题目链接

Codeforces Round #499 (Div. 2)--D. Rocket

题解

中档题,交互题。题意大概是通过多次询问求出一个距离,距离小于等于一个给定的最大值,返回值包含了询问与答案的大小关系的信息。返回值有可能是错误的,返回的答案是否正确取决于一个长度不超过30的数组,数组长度已知,这个数组循环使用,如果当前位置的值为1返回正确答案,若为0返回错误答案。

注意到数据规模小于230,询问次数不大于60次。我们首先以最大值询问数组长度的次数,得到数组的信息,之后再通过二分来求出正确答案,极限情况下刚好询问次数为60次。

我的代码懒得写二分怕错不过原理差不多,注意询问的值不能超过最大值否则会返回Wrong Answer,我因此跪了七八次。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int m, n, q1;
int p[31], pow2[31];

int main()
{
    cin >> m >> n;
    pow2[0] = 1;
    for (int i = 1; i < 31; i++) {
        pow2[i] = pow2[i - 1] << 1;
    }
    for (int i = 0; i < n; i++) {
        printf("%d\n", m);
        fflush(stdout);
        scanf("%d", &q1);
        if (q1 == -1) p[i] = 1;
        else if (q1 == 1) p[i] = 0;
        else return 0;
    }
    int ans = 0;
    int num = 0;
    for (int i = 29; i >= 0; i--) {
        if (ans + pow2[i]>m)continue;
        printf("%d\n", ans + pow2[i]);
        fflush(stdout);
        scanf("%d", &q1);
        if (p[num%n] == 0)q1 = -q1;
        if (q1 == 1) {
            ans += pow2[i];
        }
        else if (q1 == 0) {
            return 0;
        }
        num++;
    }
    printf("%d\n", ans);
}

标签: binary search

添加新评论