1 条题解

  • 0
    @ 2026-5-3 15:31:39

    1. 题目本质与陷阱

    本题是 Codeforces 愚人节比赛的典型“整活题”,核心特点如下:

    • 题目本身没有任何算法逻辑,既不需要计算,也不需要处理输入输出。
    • 题目要求输出的“测试用例数量”是一个隐藏信息,无法通过常规算法推导,只能通过特殊方式获取。
    • 题目没有样例输入输出,也没有任何提示性的数学规律,常规思路完全失效。

    2. 核心解题思路:如何找到测试用例数量

    题解中提到了两种主流方法,我们逐一拆解:

    方法一:二进制搜索法(利用提交状态筛选)

    1. 前提条件:当比赛中出现至少一份正确提交(Accepted)后,就可以利用 Codeforces 状态筛选功能获取答案。
    2. 筛选逻辑
      • 状态页面的“Test”筛选框可以根据提交通过的测试用例数过滤结果。
      • 一份通过所有测试用例的提交,会在“Test >= k”的筛选条件下显示,只要 k ≤ 测试用例总数
      • 我们可以通过二分查找来快速定位最大值:
        • 初始范围设为 [1, 200](根据经验,愚人节题的测试用例数通常在这个区间)。
        • 取中间值 mid,筛选“Test >= mid”,如果有 Accepted 提交,说明总数 ≥ mid;否则总数 < mid。
        • 不断缩小范围,直到找到最大的 mid,此时 mid 就是测试用例总数。
    3. 效率优势:二分查找仅需约 8 次筛选操作,就能快速定位答案,比暴力枚举高效得多。

    方法二:观察提交过程

    1. 当其他选手的提交在评测时,会显示 running on test x,通过观察其最终通过的最大测试用例编号,即可得到总数。
    2. 也可以通过选手的提交次数推测:如果选手从 1 开始暴力枚举答案,那么通过提交次数可以大致估算出测试用例总数约为 140 左右,与本题的实际答案 143 吻合。
    #include <iostream>
    using namespace std;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << "143\n";
        return 0;
    }
    
    • 1

    信息

    ID
    6748
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者