Codeforces Round #655 (Div. 2) F

文章目录[x]
  1. 1:题目链接
  2. 2:题面
  3. 3:题意
  4. 4:思路
  5. 5:参考代码




F

题目链接

https://codeforces.com/contest/1372/problem/F

题面

在这里插入图片描述

题意

这个是交互题,要求的是个长度为的单调不降的序列,每次给一个询问 ,返回的是该区间的最小众数以及其出现的次数

思路

由于要求的数组是单调不降的,这样可以保证 区间内必定是 ,所以可以考虑分治来不断缩小区间。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define MP(a, b) make_pair(a, b)
#define P pair<int, int>
const int N = 2e5 + 10;
int ans[N];
P query(int l, int r) {
  printf("? %d %d\n", l, r);
  fflush(stdout);
  int x, f;
  scanf("%d%d", &x, &f);
  return MP(x, f);
}
void solve(int l, int r) {
  if (l <= r) {
    P x = query(l, r);
    int L = r - x.second + 1, R = l + x.second - 1;
    if (L <= R) {
      for (int i = L; i <= R; i++) {
        ans[i] = x.first;
      }
      solve(l, L - 1);
      solve(R + 1, r);
    } else {
      int mid = (l + r) / 2;
      solve(l, mid);
      solve(mid + 1, r);
    }
  }
  return;
}
int main() {
  int n;
  scanf("%d", &n);
  solve(1, n);
  printf("! ");
  for (int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  puts("");
  fflush(stdout);
  return 0;
}


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像