Solution. CF1336D Yui and Mahjong Set

Description

有一个由 $n$ 个数构成的可重集 $S$，初始时每个数的出现次数不超过 $n$。

定义：

straight：一个包含三个元素的子集，三个元素的值连续，如 $\{1,2,3\}$。
triplet：一个包含三个元素的子集，三个元素的值相同，如 $\{2,2,2\}$。

给出初始状态下 straight 和 triplet 的数量。

你有 $n$ 次询问机会，每次可以往 $S$ 中添加一个元素，返回添加元素后 straight 和 triplet 的数量。

你需要回答 $S$ 的初始状态中每个数出现了多少次。

$n\le100$

Solution

一道非常神仙的交互 / 构造。

这里是兔队的 $1,2,\dots,n-1,1$ 式构造。

设初始时 $i$ 的出现次数为 $a_i$，那么我们往 $S$ 中添加一个数 $i$ 后：

straight 的变化量为 $(a_{i-2}+1)(a_{i-1}+1)+(a_{i-1}+1)a_{i+1}+a_{i+1}a_{i+2}$。
triplet 的变化量为 $\binom{a_i}{2}$。

一种简单的想法是直接从 $1$ 到 $n$ 每个询问一遍。

如果 $a_i\ge 2$，那么根据 triplet 的变化量，我们就能够直接确定 $a_i$，剩下的数我们就没有办法了。

现在我们还没有用到 straight 的条件。

对于 $a_i$，假设我们已经知道了 $a_{1\dots i-1}$，那么根据询问 $i-2$ 时 straight 的变换量，我们就能够得到 $a_i$，需要注意的是，这个过程只对 $i\ge 4$ 时有效。

现在我们只需要确定 $a_{1\dots3}$，我们还希望得到一些询问次数。

延续之前的思路，考虑询问 $n-1$ 时的 straight 变化量，我们实际上可以直接得到 $a_n$，那么 $n$ 这次询问就被省下来了。

考虑将这一次询问给 $1$，那么：

这一次询问前 $S$ 中 $1$ 的个数 $\ge 1$，我们一定能够确定 $a_1$。
straight 的变化量为 $(a_2+1)(a_3+1)$，结合上一次询问所得到的变化量 $a_2a_3$，我们能够得到 $a_2+a_3$。

令 $\Delta=a_2+a_3$。

如果我们已经确定了 $a_2$ 或 $a_3$，另一个值就也确定了，那么只需考虑 $a_2,a_3<2$ 的情况。
$\Delta=0$，$a_2=a_3=0$。
$\Delta=1$，考虑询问 $2$ 时 straight 的变化量 $(a_1+1)a_3+a_3a_4$，由于 $a_1+1$ 非零，所以如果变化量为 $0$ 则 $a_2=1,a_3=0$，否则 $a_2=0,a_3=1$。
$\Delta=2$，$a_2=a_3=1$。

接下来就可以确定 $a_{4\dots n}$ 了。

Orz 兔队

Code

namespace Main{
    const int N = 105;
    int n, ct, cs, lstt, lsts, tt[N], ts[N], val[N];
    int invC(int x){
        for(ri i = 2; ; i++)
            if(i * (i - 1) / 2 == x)
                return i;
    }
    void Main(){
        input(n, lstt, lsts);
        for(ri i = 1; i < n; i++){
            cout << "+ " << i << endl;
            input(ct, cs);
            tt[i] = ct - lstt, ts[i] = cs - lsts;
            lstt = ct, lsts = cs;
            if(tt[i]) val[i] = invC(tt[i]);
        }
        cout << "+ 1" << endl;
        input(tt[n], ts[n]);
        tt[n] -= lstt, ts[n] -= lsts;
        if(tt[n]) val[1] = invC(tt[n]) - 1;
        int delta = ts[n] - ts[1] - 1;
        if(val[2]) val[3] = delta - val[2];
        else if(val[3]) val[2] = delta - val[3];
        else if(delta == 0) val[2] = val[3] = 0;
        else if(delta == 2) val[2] = val[3] = 1;
        else if(ts[2]) val[3] = 1;
        else val[2] = 1;
        for(ri i = 4; i < n; i++){
            if(val[i]) continue;
            if(ts[i-1] - (val[i-2] + 1) * (val[i-3] + 1)) val[i] = 1;
            else val[i] = 0;
        }
        val[n] = ts[n-1] / (val[n-2] + 1) - val[n-3] - 1;
        cout << "! ";
        for(ri i = 1; i <= n; i++) cout << val[i] << ' ';
        return;
    }
} // namespace

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog

Solution. CF1336D Yui and Mahjong Set

Description

Solution

Code