loj3041 joisc2019 矿物 交互题/分治

· · 个人记录

https://loj.ac/problem/3041

这题操作数要小于2O(nlogn).

两个优化: $1.$可以在初始的时候random_shuffle()一下,来保证复杂度不会到最差. 2.其实把所有东西从集合中取出来是不必要的.我们可以对于每个进入集合的东西打标记.具体见代码.此方法可以使得复杂度达到$2O(n)+1.5O(nlogn)$. 加上了这两个优化后,本题仍然无法通过.需要题解: https://www.ioi-jp.org/camp/2019/2019-sp-tasks/day4/minerals-review.pdf 3.我们$mid$设成$\frac{L+R}{2}$不是最优的!大抵她假设最终设成$L+\frac{R-L}{2}p$,然后计算$p$取何值的时候函数取最小值.详见其pdf的$47$页,方法是求导.不过他在推柿子的第二行写错了.应为: $tNlogN=tpNlog(pN)+t(1-p)Nlog((1-p)N)+(1+p)N

后面都是对的.最后证明当p取0.382的时候最终的操作次数大抵是1.44O(nlogn)+2O(n)可以通过本题.

#include <bits/stdc++.h>
#include "minerals.h"
#define MOD 1000000007
#define INF 1000000000
#define ll long long
#define pii pair<int, int>
#define iiii pair<int, pii>
#define rep(i, x) for (int(i) = 0; (i) < (x); (i)++)
#define mp make_pair
#define a _A
inline int getint() {
    char c = getchar();
    int x = 0, p = 1;
    while (c <= 32) c = getchar();
    if (c == 45)
        p = -p, c = getchar();
    while (c > 32) x = x * 10 + c - 48, c = getchar();
    return x * p;
}
using namespace std;
// ruogu
const int N = 43010;
const double alpha = 0.35;
int n, res, a[N], c;
vector<int> v[N << 5];
bool vis[N];
//
void solve(int l, int r, int k) {
    if (r - l <= 0)
        return;
    if (r - l == 1) {
        Answer(a[l] + 1, v[k][0] + 1);
        return;
    }
    int mid = l + (r - l) * alpha;
    if (mid == r)
        --mid;
    if (mid == l)
        ++mid;
    for (int i = l; i < mid; i++) {
        res = Query(a[i] + 1);
        vis[i] ^= 1;
    }
    int sl = mid - l, sr = r - mid;
    rep(i, v[k].size()) {
        if (v[c].size() == sl)
            v[c + 1].push_back(v[k][i]);
        else if (v[c + 1].size() == sr)
            v[c].push_back(v[k][i]);
        else {
            int tmp = Query(v[k][i] + 1);
            if ((tmp != res) ^ vis[l])
                v[c].push_back(v[k][i]);
            else
                v[c + 1].push_back(v[k][i]);
            res = tmp;
        }
    }
    int ls = c, rs = c + 1;
    c += 2;
    solve(l, mid, ls);
    solve(mid, r, rs);
}
void Solve(int NN) {
    srand(233);
    int cnt = 0;
    n = NN;
    c = 1;
    rep(i, 2 * n) {
        int tmp = Query(i + 1);
        if (tmp != res)
            a[cnt++] = i;
        else
            v[0].push_back(i);
        res = tmp;
    }
    rep(i, n) vis[i] = true;
    random_shuffle(a, a + n);
    random_shuffle(v[0].begin(), v[0].end());
    solve(0, n, 0);
}