KismetOI Round 7「春影赛」A题 思考与总结记录

题面如下：

T724881 [KismetOI 2026 I] oo_vv_oo

题目描述

有一个长度为 n 的序列 A。

你每次可以给交互库一个下标序列 i1​,i2​,i3​,…,ik​。需保证 1≤ix​≤n，但可以有相同的。

交互库会返回 j1​,j2​,…,jK​。其中 jx​ 表示 Aijx​​​>max(Aijx​−1​​,Aijx​+1​​)，显然 1<jx​<k。

现在已知 n，并且 A 中存在唯一的最大值。同时一定有 A1​=An​=0。请在 m 次询问内回答最大值的下标。

请注意：查询的 k 不能超过 n，否则可能出现未知错误情况。

输入格式

首先输入一行两个整数 n,m。

对于你的每次查询，交互库会按如下格式输出一行：首先输出一个整数 K，接下来输出 K 个整数表示返回的 j 序列，用空格隔开。

输出格式

你可以以如下格式进行交互：

  • 输出一行 ? k i[1] i[2] ... i[k] 进行题目描述中给出的查询。

  • 输出一行 ! ans 表示你确定了最大值的下标 ans 并输出，请在此后自行结束程序运行以防止获得不可预知的结果。

请在每次执行完一次查询或给出答案的输出后，输出一个换行并清空缓冲区。

你可以使用如下语句来清空缓冲区：

  • 对于 C/C++：fflush(stdout)；

  • 对于 C++：std::cout << std::flush；

  • 对于 Java：System.out.flush()；

  • 对于 Python：stdout.flush()；

  • 对于 Pascal：flush(output)；

  • 对于其他语言，请自行查阅对应语言的帮助文档。

请保证你的程序的交互过程符合格式要求，否则你可能得到不可预知的错误结果。

如果您有更多疑问，可以参阅样例与样例解释。

思考过程

其实一开始看到题目，我真的是一脸？？？
因为我重来没有写过这种类型的题，看到样例更是云里雾里，反复读了4遍题目才看懂题目意思，就是你输出一些编号，交互库回还给你这些编号中的峰值，如 a[i-1] <a[i]>a[i+1],就会返回 下标i 在你的询问序列中的下标，说的有点抽象，如下图示

暴力写法

于是我想出了一个暴力写法，先判断返回的峰值个数是否唯一，如果唯一就直接退出，输出i在询问列表中的下标，不唯一则将返回的第一个峰值位置即i-1到最后一个峰值的位置i+1再次输出

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;

public class oo_vv_oo {
    public static StreamTokenizer sz = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static int sc() throws IOException {
        sz.nextToken();
        return (int) sz.nval;
    }

    public static void main(String... args) throws IOException {
        int n = sc(), m = sc();

        // 特判 n = 3 的情况
        if (n == 3) {
            System.out.println("! 2");
            System.out.flush();
            return;
        }

        // 维护当前查询区间的左边界 l 和右边界 r
        int l = 1, r = n;

        // 1. 第一次查询：? n 1 2 ... n
        StringBuilder out = new StringBuilder();
        out.append('?').append(" ").append(n);
        for(int i=1;i<=n; i=-~i) out.append(" ").append(i);
        System.out.println(out);
        System.out.flush();

        int cur = -1;
        while (m-- > 0) {
            cur = sc();

            // 当只剩 1 个峰值时，读取其相对位置，算出真实下标并输出答案
            if (cur == 1) {
                int pos = sc(); // 读入唯一峰值在当前区间内的相对位置
                System.out.println("! " + (l + pos - 1));
                System.out.flush();
                return;
            }

            // 读取本次返回的所有峰值（相对位置）
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < cur; i = -~i) list.add(sc());

            // 将相对位置换算为原数组的真实下标
            int p1 = l+list.get(0) - 1;
            int p2 = l+list.get(list.size() - 1) - 1;

            // 缩小下一次查询的区间范围 [l, r]
            l = Math.max(1, p1 - 1);
            r = Math.min(n, p2 + 1);

            // 构建并发送下一次查询
            out = new StringBuilder();
            int len = r-l+1;
            out.append('?').append(" ").append(len);
            for(int i=l;i<=r;i=-~i) out.append(" ").append(i);
            System.out.println(out);
            System.out.flush();
        }
    }
}

不用想肯定超时和WA（因为我交了一发），那就想怎么优化


第一个优化-对比优化

当区间内出现多个峰值时，额外花 1 次询问直接 PK 最左峰值与最右峰值的大小，根据结果斩断较小者那一侧的整个区间

题目不允许直接查询某个下标的数值，但利用护栏 $A_1 = 0$ 和 $A_n = 0$，我们可以构造一次特殊的 4 元素查询如
发送询问：? 1 p1(最左峰值) p2(最右峰值) n

交互库内部提取出的数值序列为：[A1, Ap1, Ap2, An] = [0, Ap1, Ap2, 0]。

然后进行裁剪


代码如下

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;

public class oo_vv_oo {
    public static StreamTokenizer sz = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static int sc() throws IOException {
        sz.nextToken();
        return (int) sz.nval;
    }

    public static void main(String... args) throws IOException {
        int n = sc(), m = sc();
        if (n == 3) {
            System.out.println("! 2");
            System.out.flush();
            return;
        }
        int l = 1, r = n;
        while (m > 0) {
            // 1. 查询当前连续区间 [l, r]
            int len = r - l + 1;
            StringBuilder out = new StringBuilder();
            out.append('?').append(" ").append(len);
            for (int i = l; i <= r; i = -~i) {
                out.append(" ").append(i);
            }
            System.out.println(out);
            System.out.flush();
            m--;

            int cur = sc();
            if (cur == 1) {
                int pos = sc();
                System.out.println("! " + (l + pos - 1));
                System.out.flush();
                return;
            }

            // 读取所有峰值相对位置并换算为真实下标
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < cur; i = -~i) list.add(sc());

            int p1 = l + list.get(0) - 1;
            int p2 = l + list.get(list.size() - 1) - 1;

            // 2. 额外询问 ? 4 1 p1 p2 n 比较 p1 和 p2 的大小
            System.out.println("? 4 1 " + p1 + " " + p2 + " " + n);
            System.out.flush();
            m--;

            sc(); // 读入返回数量 k (必定为 1)
            int pos = sc(); // 2 表示 p1 胜出，3 表示 p2 胜出

            // 3. 根据比较结果强行将区间砍半，彻底避免死循环
            if (pos == 2) {
                r = p2 - 1; // p1 更大，裁掉 p2 及其右侧
            } else {
                l = p1 + 1; // p2 更大，裁掉 p1 及其左侧
            }
        }
    }
}

这个也超时了，嘻嘻，所以这个也是错的，还要优化
既然对比优化每一轮要消耗 2 次询问，面对 N = 10^6, m = 20 的极限限制，最多只能缩减 10 轮，超时（TLE）也是意料之中。

离散化

核心逻辑

  1. 彻底放弃连续区间：区间中间那些递减或平庸的数字全是废料，我们根本不需要它们，只保留上一轮返回的“峰值点”。

  2. 加入 1 和 N 护栏：因为交互库规定序列的首尾元素绝不会被当成峰值返回，如果全局最大值刚好落在集合的最左或最右，就会被误杀。我们在两侧分别加上 A1 = 0 和 An = 0 充当安全护栏，组装成新序列 Q = [1, g1, g2, ..., g_k, n]。

  3. 两相邻必灭一：在新序列中，任意两个相邻的旧峰值 $g_i$ 与 $g_{i+1}$ 互相作为邻居。较小的那一个由于旁边存在更大的数，在这一轮绝对不可能再被选为峰值！

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static StreamTokenizer sz = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static int sc() throws IOException {
        sz.nextToken();
        return (int) sz.nval;
    }

    public static void main(String... args) throws IOException {
        int n = sc(), m = sc();

        if (n == 3) {
            System.out.println("! 2");
            System.out.flush();
            return;
        }

        StringBuilder out = new StringBuilder();
        out.append('?').append(" ").append(n);
        for (int i = 1; i <= n; i = -~i) out.append(" ").append(i);
        System.out.println(out);
        System.out.flush();

        int cur = sc();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < cur; i = -~i) list.add(sc());

        while (list.size() > 1) {
            int len = list.size() + 2;
            int[] q = new int[len];
            q[0] = 1;
            for (int i = 0; i < list.size(); i = -~i) q[i + 1] = list.get(i);
            q[len - 1] = n;

            out = new StringBuilder();
            out.append('?').append(" ").append(len);
            for (int i = 0; i < len; i = -~i) out.append(" ").append(q[i]);
            System.out.println(out);
            System.out.flush();

            cur = sc();
            List<Integer> next = new ArrayList<>();
            for (int i = 0; i < cur; i = -~i) {
                int pos = sc();
                next.add(q[pos - 1]);
            }
            list = next;
        }

        System.out.println("! " + list.get(0));
        System.out.flush();
    }
}

其实走了很多弯路，想了很多没有用的方法，但是对与本蒟蒻来说能写出来还是有点成就感的

KismetOI Round 7「春影赛」A题 思考与总结记录
http://blog.zheco68.asia/archives/kismetoi-round-7-chun-ying-sai-si-kao-ji-lu
作者
zheco
发布于
2026年08月25日
更新于
2026年08月25日
许可协议