CF1973D(CFR 945) Cat, Fox and Maximum Array Split 题解

题意

题目链接

交互题。

狐狸给你两个正整数 $n,k$,并且她有一个长度为 $n$ 的隐藏数组。对于一段区间 $(l,r)$,其价值 $f(l,r)$ 等于长度乘以区间最大值。

你有 $2n$ 次查询次数,每次查询形如 ? l x,狐狸会告诉你一个数 $r$,表示最小的满足 $f(l,r)=x$ 的 $r$,或是 $n+1$ 表示不存在 $r$。

你的目标是找到最大的 $m$,使得原数组能够被分割成 $k$ 个子数组,且每个子数组的价值都为 $m$。

解析

爱做交互题。

根据对范围 $2n$ 的猜测,容易想到可以将查询分成两块查询次数分别不多于 $n$ 次的查询。发现数组的最大值是至关重要的,因而我们可以通过至多 $n$ 次形如 ? 1 n*i 的查询($i$ 从 $n$ 到 $1$)判断数组的最大值是多少。我们发现只有当数组的最大值为 $i$ 时,上述询问才会返回一个唯一的 $r=n$。

找到最大值后,不妨考虑 $m$ 的可能值。由于在这 $k$ 个区间后,必定有一个区间包含最大值(记作 $max$),且这个区间的长度一定不会超过 $\lfloor \frac{n}{k} \rfloor$。这是因为如果这个包含最大值的区间长度比 $\lfloor \frac{n}{k} \rfloor$ 要大,那么这 $k$ 的区间的长度和一定会超过 $n$。因此,我们可以枚举 $m$ 的可能性,即从 $\max \times \lfloor \frac{n}{k} \rfloor$ 到 $\max \times 1$。

对于每个可能的 $m$,我们可以这样判断其合法性:先询问 ? 1 m,然后若返回 $n+1$,显然不合法,否则若返回 $r$,再询问 ? r+1 m 即可。以此类推,我们可以通过至多 $k$ 次询问来判断这个 $m$ 是否合法。

具体的,在询问过程中,以下情况均为不合法:

  1. 任意一次询问返回了 $n+1$。
  2. 经过 $k$ 次询问后,数组仍然没有被全部覆盖。
  3. 还没有询问 $k$ 次,数组就被全覆盖了。

您可以通过查询代码中的 check 函数来理解详细的验证过程。

你发现这一部分的查询次数为 $\lfloor \frac{n}{k} \rfloor \times k$,不会超过 $n$。故问题解决。

代码

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
int n,k,maxx;
bool check(int len){
    int now=1,nowk=0;
    while(now<=n&&nowk<k){
        printf("? %lld %lldn",now,maxx*len);
        fflush(stdout);
        int tmp;   
        scanf("%lld",&tmp);
        if(tmp==n+1) return false;
        now=tmp+1;nowk++;
    }
    if(now>n&&nowk==k) return true;
    return false;
}
void solve(){
    scanf("%lld %lld",&n,&k);
    for(int i=n;i>=1;i--){
        printf("? 1 %lldn",i*n);
        fflush(stdout);
        int tmp;
        scanf("%lld",&tmp);
        if(tmp!=n+1){
            maxx=i;break;
        }
    }
    for(int i=n/k;i>=1;i--){
        if(check(i)){
            printf("! %lldn",i*maxx);
            fflush(stdout);
            int tmp;
            scanf("%lld",&tmp);
            if(tmp==-1) exit(0);
            return;
        }
    }
    printf("! -1n");
    fflush(stdout);
    int tmp;
    scanf("%lld",&tmp);
    if(tmp==-1) exit(0);
    return;
}
signed main(){
    int T;
    scanf("%lld",&T);
    while(T--) solve();
    return 0;
}
本文作者:water_tomato

评论

  1. mfyx
    1 月前
    2024-5-18 22:18:06

    根据博主的思路写得,过了!
    这是我写得第一道交互题!
    (☆ω☆)

    代码如下:
    https://codeforces.com/contest/1973/submission/261541299

    • 博主
      mfyx
      1 月前
      2024-5-18 22:20:09

      好耶!继续加油哇!

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇