题解：CF2134E Power Boxes

SUNCHAOYI · 2025-09-08 12:53:41 · 题解

首先考虑出在什么情况下在位置 x 上进行 \texttt{throw x} 操作可以确定该位置上的值。设 f_x 表示从 x 开始扔球时会进行的次数。若 f_{x + 1} = f_{x + 2}，显然 f_x = f_{x + 1} + 1，此时无法确定 x 位置上的值。若 f_{x + 1} \neq f_{x + 2}，此时可以确定。具体来说，有：

剩下考虑形如 f_{x + 1} = f_{x + 2}，而 x 位置上值未知的情况。由于 f_x = f_{x + 1} + 1 > f_{x + 1}，因此 x - 1 位置上的值必定已知。尝试进行 \texttt{swap x} 操作，形成新的关系必定满足 f_x = f_{x + 1} + 1 = f_{x + 2} + 1，此时若 f_{x - 1} + 1 = f_{x + 1}，则说明原来 x 位置上的值为 2，否则为 1。

特别的，考虑 1 位置上未知的情况。尝试 \texttt{swap 1} 后进行 \texttt{throw 2} 操作，若 f_2 = f_3 + 1，则说明原来 1 位置上的值为 1，否则为 2。

最后来证明操作数不超过 \lceil\frac{3n}{2}\rceil。

证明
如上所述，\texttt{throw x} 在每个位置上操作有且仅有 1 次。若 f_{x + 1} \neq f_{x + 2}，则不需要进行 \texttt{swap x} 操作，否则必然有 f_{x - 1} \neq f_x。因此 \texttt{swap x} \le \lceil \frac{n}{2} \rceil。命题得证。

写的时候需要注意，在 \texttt{swap x} 以后需要更新 f_{x - 1},f_{x} 的值，防止出现错误！！！

代码如下：

#include <bits/stdc++.h>
#define pii pair <int,int>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int query (string op,int x)
{
    cout<<op<<" "<<x<<endl;fflush (stdout);
    if (op == "throw") return read ();
    else return -1;
}
void solve ()
{
    int n = read ();
    vector <int> ans (n + 1),f (n + 3,0),d (n + 1);
    for (int i = n;i;--i)
    {
        if (f[i + 1] != f[i + 2])
        {
            f[i] = query ("throw",i);
            ans[i] = d[i] = 1 + (f[i] != f[i + 1] + 1);
        }
        else f[i] = f[i + 1] + 1;
    }
    for (int i = n;i;--i)
    {
        if (ans[i])
        {
            f[i] = f[i + d[i]] + 1;
            continue;
        }
        if (f[i + 1] != f[i + 2])
        {
            f[i] = query ("throw",i);
            ans[i] = d[i] = 1 + (f[i] != f[i + 1] + 1);
            continue;
        }
        f[i] = f[i + 1] + 1;
        if (i == 1)
        {
            int x = query ("swap",1);
            if (f[2] + 1 == query ("throw",2)) ans[1] = 1;
            else ans[1] = 2;
        }
        else
        {
            int x = query ("swap",i - 1);
            f[i] = query ("throw",i - 1);
            ans[i] = d[i] = 1 + (f[i] == f[i + 1] + 1);
            swap (f[i - 1],f[i]);swap (d[i - 1],d[i]);
            f[i] = f[i + ans[i]] + 1;
        }   
    }
    cout<<"! ";
    for (int i = 1;i <= n;++i) cout<<ans[i]<<" \n"[i == n];
    fflush (stdout);
}
int main ()
{
    int t = read ();
    while (t--) solve ();
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}