题解：CF1354G Find a Gift

题解：CF1354G Find a Gift

题意简述

有 n 个盒子，每个盒子要么有石头，要么有礼物，石头重量均相等，礼物重量可能不同但严格小于石头的重量。

你有一个可以使用 50 次的天平，可以称出任意两组（不一定是一个）物品哪组更重或一样重。

请你找到编号最小的礼物。

多测。

解题思路

我们先假设第一个箱子是石头，尝试找到一些可行的解法。

可以使用倍增的思想快速跳过所有第一个礼物前的石头，如图所示：

只要前 2^k 个数和第 2^k + 1 到 2^{k + 1} 的重量相等，那么就可以证明前 2^{k + 1} 都相等。反之则可以证明答案在第 2^k + 1 到 2^{k + 1} 之间。

此时，我们可以进行标准的二分查找，在前 2^k 个之中选择和 2^k + 1 到 mid 数量相等的箱子（因为前面的都是石头，后面的有可能有礼物）。如果重量相等：l \gets mid + 1，否则 r \gets mid - 1，直到 r - l \le 1 即为答案。

我们到目前总共用了 2\log n 最多 20 次操作。

可是，我们目前的所有做法都基于第一个箱子不是礼物。

为了保证这个做法成立，我们需要先判断第一个礼盒是不是礼物（如果是，直接输出 ! 1 结束）。

方式也很简单，暴力找最多 30 个位置（我找了 20 个也过了），和第一个点比较，如果出现有大于第一个点的数，那么第一个点就是礼物，否则，就认为第一个点是石头（因为如果第一个点是礼物，结合题面给出礼物数量小于 \frac{n}{2}，所以错误率也小于 (\frac{1}{2})^{30}）。

附毫秒级随机种子代码：

void seed()
{
    auto now = std::chrono::system_clock::now();
    auto ms = std::chrono::time_point_cast<std::chrono::milliseconds>(now);
    auto t = ms.time_since_epoch().count();
    srand(t);
    return;
}

参考代码

#include<bits/stdc++.h>
using namespace std;
int t , n , k , p , l , r , mid , ans;
string s;
void seed()
{
    auto now = std::chrono::system_clock::now();
    auto ms = std::chrono::time_point_cast<std::chrono::milliseconds>(now);
    auto t = ms.time_since_epoch().count();
    srand(t);
    return;
}
void ask(int as , int ae , int bs , int be)
{
    cout << "? " << ae - as + 1 << ' ' << be - bs + 1 << endl;
    for(int i = as ; i <= ae ; i++)
    {
        cout << i << ' ';
    }
    cout << endl;
    for(int i = bs ; i <= be ; i++)
    {
        cout << i << ' ';
    }
    cout << endl;
    cin >> s;
    if(s == "WASTED")
    {
        cout << "ERROR" << endl;
        exit(0); 
    }
    return;
}
bool first()
{
    for(int i = 1 ; i <= 20 ; i++)
    {
        int tmp = rand() % (n - 1) + 2;
        ask(1 , 1 , tmp , tmp);
        if(s == "SECOND")
        {
            return 1;
        }
    }
    return 0;
}
bool check(int q)
{
    ask(1 , q - p , p + 1 , q);
    if(s == "FIRST")
    {
        return 1;
    }
    return 0;
}
int main()
{
    seed();
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        if(first())
        {
            cout << "! 1" << endl;
            continue; 
        }
        p = 1;
        while(p < n)
        {
            if(p * 2 >= n)
            {
                l = p + 1;
                r = n;
                break;
            }
            ask(1 , p , p + 1 , p * 2);
            if(s == "FIRST")
            {
                l = p + 1;
                r = p * 2;
                break;
            }
            p *= 2;
        }
        while(l <= r)
        {
            mid = (l + r) / 2;
            if(check(mid))
            {
                ans = mid;
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }
        cout << "! " << ans << endl;
    }
    return 0;
}