1 条题解
-
0
1. 题目本质与陷阱
本题是 Codeforces 愚人节比赛的典型“整活题”,核心特点如下:
- 题目本身没有任何算法逻辑,既不需要计算,也不需要处理输入输出。
- 题目要求输出的“测试用例数量”是一个隐藏信息,无法通过常规算法推导,只能通过特殊方式获取。
- 题目没有样例输入输出,也没有任何提示性的数学规律,常规思路完全失效。
2. 核心解题思路:如何找到测试用例数量
题解中提到了两种主流方法,我们逐一拆解:
方法一:二进制搜索法(利用提交状态筛选)
- 前提条件:当比赛中出现至少一份正确提交(Accepted)后,就可以利用 Codeforces 状态筛选功能获取答案。
- 筛选逻辑:
- 状态页面的“Test”筛选框可以根据提交通过的测试用例数过滤结果。
- 一份通过所有测试用例的提交,会在“Test >= k”的筛选条件下显示,只要
k ≤ 测试用例总数。 - 我们可以通过二分查找来快速定位最大值:
- 初始范围设为
[1, 200](根据经验,愚人节题的测试用例数通常在这个区间)。 - 取中间值
mid,筛选“Test >= mid”,如果有 Accepted 提交,说明总数 ≥ mid;否则总数 < mid。 - 不断缩小范围,直到找到最大的
mid,此时mid就是测试用例总数。
- 初始范围设为
- 效率优势:二分查找仅需约 8 次筛选操作,就能快速定位答案,比暴力枚举高效得多。
方法二:观察提交过程
- 当其他选手的提交在评测时,会显示
running on test x,通过观察其最终通过的最大测试用例编号,即可得到总数。 - 也可以通过选手的提交次数推测:如果选手从 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
- 上传者