本文主要是介绍很妙的思维题，CF 1270D. Strange Device，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、题目
1、题目描述
2、输入/交互
2.1输入
2.2交互
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入/交互
2.1输入
2.2交互
3、原题链接
Problem - 1270D - Codeforces
二、解题报告
1、思路分析
我们只考虑前k+1个数字的长度为k的子序列，显然有k + 1种情况，即枚举去掉哪个数字
那么当去掉的数字是第1~m小的数字，我们查询结果会是第m + 1小的数
当去掉的数字是第m + 1~k + 1小的数字，我们查询结果会是第m小的数字
可以得出：
长度为k + 1的数组的k + 1个子序列的查询结果只有两种可能
第m 小和第m + 1小
第m + 1小的数字出现m次，即去掉的数字为第1~m小时的情况
那么我们只要对k + 1次查询的返回结果计数，最大数字的出现频次就是m
---
思考：为什么取前k + 1而不是前k？
为了保证当m = k时，第m + 1小存在
而且k < n，k + 1 <= n，保证了查询的合法性
2、复杂度
时间复杂度： O(k^2)空间复杂度：O(k)
3、代码详解
import sys
from collections import Counter# sys.stdin = open('in.txt', 'r')n, k = map(int, input().split())st = Counter()for i in range(1, k + 2):print('?', *(j for j in range(1, k + 2) if j != i), flush=True)idx, val = map(int, input().split())st[val] += 1print('!', st[max(st)])这篇关于很妙的思维题，CF 1270D. Strange Device的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
