题解：CF2134E Power Boxes

首先考虑出在什么情况下在位置

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}

，此时可以确定。具体来说，有：

ans_x = \begin{cases} 1 & \texttt{if}\ f_{x} = f_{x + 1} + 1\\ 2 & \texttt{if}\ f_{x} = f_{x + 2} + 1 \end{cases}

剩下考虑形如

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}

的值，防止出现错误！！！

代码如下：

CPP

#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;
}

题解：CF2134E Power Boxes

文章操作

相关推荐

评论

题解：CF2134E Power Boxes