语言月赛题解

· · 题解

前言

这题没啥难的，但是既然都来看题解了，来讲讲怎么写交互题吧（会的可以跳过）。 ::::info[交互题简介]

什么是交互题？

交互题是要求选手实现一个程序或函数与评测机进行对话，然后完成一定任务的特殊题目就是交互题。

那么你一定会问了：怎么询问呢？

交互形式一般是两种：

先来说说这两者的区别：第一种是函数式交互，对于这种题一般就是题目让你干啥你就干啥例如：【APIO2025】转杆 这题就是一个函数交互式的题。

第二种叫做IO交互式，这种题一般就是让你去输出一些东西来交互，并且限制次数，这类的思维量很小，但是有时需要你绕过题目本身去看出题人想让你干啥。

如何进行交互呢？

对于函数式我们简称为 1

对于IO式我们简称为 2

对于 1，我们需要且必须实现的函数就要严格按照题目的要求来命名你的功能函数。一般这类题目会在开头声明

请注意：本题只支持 C++ 语言提交；你不需要也不应该实现 main 函数；你需要在程序开头添加如下内容：

void the_name_of_the_problem(...);

就想之前说的，这类题一般是他让你干啥你干啥，别的不用管，更不要实现main

对于 2，我们虽然要实现的是main函数但是我们要做的是，打开思维，用你的大脑与出题人博弈，想好如何在合法的询问次数内来获取最终答案的方式。

注意：询问次数一般是个提示！ 比方说：我给你长为 10^5 的序列然后给你限制交互次数为 20\sim40 次，这说明你要在 \log n 次以内，将询问完成。

如何调试呢？

一般题目会把交互库给你，所以这个不用慌，举办方也会把怎么使用checker告诉你。

做题步骤

  1. 判断是否是交互题。
  2. 判断交互类型。
  3. 根据题目要求来选择你的交互方式。
  4. AC本题，rk++！ ::::

    本题思路

    首先我们知道这是一道IO交互题，我们该如何交互呢？首先我们看到交互次数上限：40320。然后我们注意到：n\le 8那是不是说明这题抛开交互不说至少n!能过！然后我们又注意到：8!=40320，那说明我们只需要简单的进行全排列输出交互，知道有答案我们就停止。

这一步我们用 next_permutation 就可以实现了。

:::info[ACcode]

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define pf(a) push_front(a)
#define pof pop_front
#define pob pop_back//
#define fr() front()
#define ba() back()
#define ls(x) x << 1
#define rs(x) (x << 1) | 1
#define re register
#define in(a) insert(a)
#define fi first
#define se second
#define gcd(a, b) __gcd(a, b)
#define l2(a) log(a) / log(2)
#define ui128 unsigned __int128
#define i128 __int128
#define ll long long
#define pll pair<ll, ll>
#define ull unsigned long long
#define pii pair<int, int>
#define pq1 priority_queue<int>
#define pq2 priority_queue<int, vector<int>, greater<int>>
#define ui unsigned int
#define db double
#define Add1(u,v) g[u].pb(v)
#define Add2(u,v,w) g[u].pb({v,w})
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)//一定不要关同，因为在我们交互时要同步进行，关了之后会把所有询问放到一起这样你的询问会checker RE/TLE
using namespace __gnu_pbds;
using namespace std;
const int N = 250 + 5e5;
int n;
int a[N];
signed main() {
    // freopen("test.in","r",stdin);//对拍用，这里注释掉
    // freopen("test.out","w",stdout);
    // IOS;
    cin>>n;
    for(int i = 1;i <= n;++i)a[i] = i;
    do{
        for(int i = 1;i <= n;++i)cout<<a[i]<<" ";
        cout<<"\n";
        fflush(stdout);
        bool check;
        cin>>check;
        if(check)break;
    }while(next_permutation(a + 1,a + 1 + n));
}

:::