题解：P14538 [OII 2025] 市政委员会 / Giunta comunale

· · 题解

感觉还挺有意思的。

首先遇到这种题比较容易想到的就是二分然后看看能不能缩小一半的区间。

但是由于两个数的存在，你不一定能确定这个数到底在哪边还是两边都有。

我们考虑以下过程：

假设当前我们有一段长度为 n+1 的序列 A，将其分为 L,R 两段，这里面有 n 个数，我们询问所有数是否在 L 中，是的加入 X 集合，否则加入 Y 集合。

有几种情况：

  1. 若 |X|<|L|，说明出现两次的数在 X 和 L 内，递归做即可。
  2. 否则必然 |X|=|L|，这时我们询问所有在 X 内的数是否在 R 中，如果是就说明答案就是这个数。
  3. 如果都不是，那么说明出现两次的数在 Y 和 R 内，递归做即可。

这样我们解决了问题，但是我们如何保证操作次数呢？

如果我们记按上述方法解决大小为 n 的问题最优操作次数为 f(n)，那么有 f(n)=\min\limits_{1\le x<n}\{\max\{n+f(x-1),n+x+0,n+x+f(n-x)\}\}，其中 x 即 |L|，\max 内分别对应上述三种情况。

由于 n=99 不大，写个 dp 找出来最优转移点即可，可以得知操作次数最大值为 254<260，可以获得满分。

具体实现见代码。

#include <bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout)
#define il inline
#define ll long long
#define ld long double
#define pii pair <int, int>
#define fi first
#define se second
#define ls (p << 1)
#define rs (p << 1 | 1)
#define pb push_back
#define popc __builtin_popcount
#define inf 1000000000
#define INF 1000000000000000000
const int N = 105;
int f[N], g[N]; vector <int> vec;
bool chiedi(vector <int> S, int x);
void init()
{
    memset(f, 0x3f, sizeof(f)); f[0] = f[1] = 0; 
    for (int i = 2; i <= 99; i++) for (int j = 1; j < i; j++)
    {
        int v = i + max(f[j-1], j + f[i-j]);
        if (v < f[i]) g[i] = j, f[i] = v;
    }
}
int solve(int l, int r, vector <int> o)
{
    if ((int)o.size() == 1) return o[0];
    vector <int> p, x, y; int n = o.size(), len = g[n], md = l + len - 1;
    for (int i = l; i <= md; i++) p.pb(i);
    for (int w : o) if (chiedi(p, w)) x.pb(w); else y.pb(w);
    if ((int)x.size() < len) return solve(l, md, x);
    p.clear(); for (int i = md + 1; i <= r; i++) p.pb(i);
    for (int w : x) if (chiedi(p, w)) return w;
    return solve(md + 1, r, y);
}
int delibera(int n)
{
    if (!f[n]) 
    {
        for (int i = 0; i < n; i++) vec.pb(i);
        init();
    }
    return solve(0, n, vec);
}
//------- submit above
int n = 99, a[N], cnt;
mt19937 rnd(time(0));
bool chiedi(vector <int> S, int x)
{
    cnt++; bool ok = 0;
    for (int p : S) if (a[p] == x) ok = 1;
    return ok;
}
int main()
{
    int x = rnd() % n;
    for (int i = 0; i < n; i++) a[i] = i; a[n] = x;
    shuffle(a, a + n + 1, rnd);
    if (delibera(n) == x) cout << "OK\n" << cnt << "\n";
    else cout << "WA\n";
    return 0;
}
//----- check