Accoders 8.15 NOI模拟

psoet · 2022-08-15 21:30:54 · 个人记录

knapsack

根据生成前k小值的套路，我们应该从最小解出发，每次扩展出 O(1) 个新的解，每次pop堆顶。

仔细刻画一下，我们构造的扩展方式需要满足

• 每个非初始状态的状态都可以由初始状态到达，且前驱唯一。
• 状态后继的答案不小于自身的答案。
• 状态后继只有 O(1) 个。

先考虑 l = r = 1 的情况。一个想法是，我们给一个状态一个当前位表示最后一个取的不是最小值的位置，每次要么枚举下一个不是最小值的位置，要么给当前位置+1。精细实现的构造如下：

• 先将所有背包按照次小值-最小值从小到大排序。设 q_i 表示第 i 个背包选了谁，一开始 q_i = 1。设 u 是当前指针。转移有下面三种方式：
• q_u \rightarrow q_{u} + 1
• 当 q_u = 2 时，q_u \rightarrow 1, q_{u+1} \rightarrow 2, u \rightarrow u + 1

正确性容易验证，用堆即可维护。

这里并不需要保存完整每个背包选了谁，只需保存 u 的状态即可，因为 <u 的部分固定，而 >u 的部分选的都是最小值。

现在我们解决了如下问题：

有 m 个bot，每个bot的状态权值从小到大对应的状态是 1,2,3,\cdots，每个bot可以用 O(c) 的时间在 i 的基础上求出 i+1 的权值，可以在 O(k(c + \log k)) 内求权值总和的前 k 小。

现在只需对原问题的每个背包构造对应的bot即可。

最小值的状态是一个前缀。我们考虑这样的一个过程：从右往左确定元素的最终位置，每次将当前元素往右移一步，或者如果当前元素位置固定就考虑左边的下一个元素，注意此时左边的下一个元素一定是连续前缀的末尾，所以不需要移动再靠左的元素。这样我们用堆维护（左边剩余元素个数，右边界位置，当前元素位置，状态值）即可。我们询问一个bot的第 k 小值的时候，可以记忆化存下 [1,k] 的答案，总共依然是 O(k) 的。

于是总复杂度 O((n + m + k) \log (n + m + k)) 。

#include <bits/stdc++.h>
#define DEBUG

#define For(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define rFor(i, b, a) for (int i = b, i##end = a; i >= i##end; --i)
#define eFor(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].next, v = e[i].to)

typedef long long ll;

typedef std::pair<int, int> pii;
#define fi first
#define se second

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T> 
T myrand(T l, T r) {
    return std::uniform_int_distribution<T>(l, r)(rnd);
}

template<typename T, typename ...Args> 
void LOG(T str, Args ...args) {
#ifdef DEBUG
    fprintf(stderr, str, args...);
#endif
}

#define fre(s) freopen(#s ".in", "r", stdin), freopen(#s ".out", "w", stdout)

const int kN = 2e5 + 5;
const ll kInf = 0x3f3f3f3f3f3f3f3fll;

int n, m, k;

struct Bot {
    int l, r;
    ll sev;
    std::vector<int> a;
    std::vector<ll> ans;

    struct Node {
        int rem, r, cur;
        ll val;
        bool operator <(const Node &rhs) const {
            return val > rhs.val;
        }
    };
    std::priority_queue<Node> hp;

    ll query(int k) {
        while (!hp.empty() && ans.size() < k) {
            Node u = hp.top();
            hp.pop();
            // LOG("ans[%u] = %lld\n", ans.size(), u.val);
            ans.push_back(u.val);
            if (u.cur + 1 < u.r) hp.push(Node{u.rem, u.r, u.cur + 1, u.val + a[u.cur + 1] - a[u.cur]});
            if (u.rem && u.rem < u.cur) hp.push(Node{u.rem - 1, u.cur, u.rem, u.val + a[u.rem] - a[u.rem - 1]});
        }
        if (ans.size() < k) return kInf;
        // LOG("query %u %d = %lld\n", ans.size(), k, ans[k - 1]);
        return ans[k - 1];
    }
    void init() {
        if (r > a.size()) r = a.size();
        if (l == 0) {
            ans.push_back(0);
            l = 1;
        }
        std::sort(a.begin(), a.end());
        ll sum = 0;
        For(i, 1, l - 1) sum += a[i - 1];
        For(i, l, r) {
            sum += a[i - 1];
            hp.push(Node{i - 1, (int)a.size(), i - 1, sum});
        }
        sev = query(2) - query(1);
    }
} bot[kN];

struct Stat {
    int cur, t;
    ll val;
    bool operator <(const Stat &rhs) const {
        return val > rhs.val;
    }
};
std::priority_queue<Stat> hp;

int main() {
    fre(knapsack);
    scanf("%d%d%d", &n, &m, &k);
    For(i, 1, n) {
        int c, w;
        scanf("%d%d", &c, &w);
        bot[c].a.push_back(w);
    }
    For(i, 1, m) {
        scanf("%d%d", &bot[i].l, &bot[i].r);
        if (bot[i].l > bot[i].a.size()) {
            For(j, 1, k) printf("-1\n");
            return 0;
        }
        bot[i].init();
    }
    std::sort(bot + 1, bot + m + 1, [](Bot x, Bot y) {
        return x.sev < y.sev;
    });
    Stat ini;
    ini.val = 0;
    For(i, 1, m) {
        ini.val += bot[i].query(1);
    }
    ini.cur = ini.t = 1;
    hp.push(ini);
    For(i, 1, k) {
        if (hp.empty()) {
            printf("-1\n");
            continue;
        }
        Stat u = hp.top();
        // LOG("%d %d %lld\n", u.cur, u.t, u.val);
        hp.pop();
        if (u.val >= kInf) {
            printf("-1\n");
            continue;
        }
        printf("%lld\n", u.val);
        Stat x = u;
        if (bot[x.cur].query(x.t + 1) < kInf) {
            x.val += bot[x.cur].query(x.t + 1) - bot[x.cur].query(x.t);
            ++x.t;
            // LOG("-> %d %d %lld\n", x.cur, x.t, x.val);
            hp.push(x);
        }
        x = u;
        if (x.t > 1 && x.cur < m && bot[x.cur + 1].query(2) < kInf) {
            x.val += bot[x.cur + 1].sev;
            ++x.cur, x.t = 2;
            // LOG("-> %d %d %lld\n", x.cur, x.t, x.val);
            hp.push(x);
        }
        x = u;
        if (x.t == 2 && x.cur < m && bot[x.cur + 1].query(2) < kInf) {
            x.val += bot[x.cur + 1].sev - bot[x.cur].sev;
            ++x.cur;
            // LOG("-> %d %d %lld\n", x.cur, x.t, x.val);
            hp.push(x);
        }
    }
    return 0;
}
/* PAY ATTENTION TO: */
/* 1. Memory Limit, Array Size */
/* 2. Integer Overflow */
/* 3. Multi-test */
/* 4. Potential Constant-speedup */
/* Stay organized and write things down. */

tree

看不出来什么动机，构造的方法就是：

分治，假设我们已经将最左边、最右边的叶子和根的父亲染成同一种颜色。

那么有如下使用元素个数 O(\log n) 的构造方法：

递归解决白色子树即可。

注意蓝色的链非常废物，我们可以换成：

这样每个颜色最多只会被用12次。

#include <bits/stdc++.h>

#define For(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define rFor(i, b, a) for (int i = b, i##end = a; i >= i##end; --i)
#define eFor(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].next, v = e[i].to)

typedef long long ll;

typedef std::pair<int, int> pii;
#define fi first
#define se second

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T> 
T myrand(T l, T r) {
    return std::uniform_int_distribution<T>(l, r)(rnd);
}

template<typename T, typename ...Args> 
void LOG(T str, Args ...args) {
#ifdef DEBUG
    fprintf(stderr, str, args...);
#endif
}

#define fre(s) freopen(#s ".in", "r", stdin), freopen(#s ".out", "w", stdout)

const int kN = 22;
const int kV = (1 << 20) + 5;

int n, V, m, lim, c[kV * 2], rm[kV * 2][2];

void solve(int u) {
    // LOG("solve %d\n", u);
    if (u * 2 >= V) {
        c[u] = ++m;
        return;
    }
    std::vector<int> lk;
    for (int x = u; x < V; x <<= 1) lk.push_back(x);
    lk.push_back(lk.back() * 2 + 1);
    std::reverse(lk.begin(), lk.end()); 
    // for (int x : lk) LOG("%d ", x);
    // LOG("\n");
    for (int x = u * 2 + 1; x < V; x = x << 1 | 1) lk.push_back(x);
    lk.push_back(lk.back() * 2);
    // for (int x : lk) LOG("%d ", x);
    // LOG("\n");
    c[lk[0]] = c[lk.back()] = c[u] = ++m;
    int mid = (lk.size() - 1) / 2;
    for (int i = 1, j = (int)lk.size() - 2; i <= mid + 1 - i; ++i, --j) {
        if (i == 1) assert(!(c[lk[i]] || c[lk[j]])), c[lk[i]] = c[lk[j]] = c[u];
        else {
            int x = lk[i], y = lk[mid + 1 - i], w = lk[j], v = lk[mid + lk.size() - 2 - j];
            assert(!(c[x] || c[y] || c[w] || c[v]));
            c[x] = c[y] = c[w] = c[v] = ++m;
            c[rm[x << 1 | 1][0]] = c[rm[x << 1 | 1][1]] = c[x];
            solve(x << 1 | 1);
            if (x != y) {
                c[rm[y << 1 | 1][0]] = c[rm[y << 1 | 1][1]] = c[y];
                solve(y << 1 | 1);
            }
            c[rm[w << 1][0]] = c[rm[w << 1][1]] = c[w];
            solve(w << 1);
            if (v != w) {
                c[rm[v << 1][0]] = c[rm[v << 1][1]] = c[v];
                solve(v << 1);
            }
        }
    }
}

int main() {
    fre(tree);
    scanf("%d%d", &n, &lim);
    V = 1 << n;
    c[V] = c[V * 2 - 1] = ++m;
    For(u, 1, V * 2 - 1) {
        int v = u;
        while (v < V) v = v << 1;
        rm[u][0] = v;
        v = u;
        while (v < V) v = v << 1 | 1;
        rm[u][1] = v;
    }
    solve(1);
    printf("%d\n", m);
    For(i, 1, V * 2 - 1) printf("%d ", c[i]);
    return 0;
}
/* PAY ATTENTION TO: */
/* 1. Memory Limit, Array Size */
/* 2. Integer Overflow */
/* 3. Multi-test */
/* 4. Potential Constant-speedup */
/* Stay organized and write things down. */

chess

二分答案，现在先手只要走到 \leq mid 的就会退出，后手只要走到 > mid 的会退出。

排除掉起始点就 \leq mid 的情况。现在可以将图二染色变成二分图，每次走一步，走不了了就输。

将每个点拆成 10^9 份，现在每个点只能走一次。

结论：先手必胜当且仅当所有最大匹配均包含起点。

先手每一步都可以选择走向最大匹配中与其匹配的点。如果所有最大匹配均包含起点，假设我们走 s \rightarrow x_1 \rightarrow y_1 \rightarrow x_2 \rightarrow y_2 \rightarrow \cdots \rightarrow y_k 后先手走不了了。那么 (x_i,y_i) 是不包含 s 的最大匹配，矛盾。

如果存在一个最大匹配不包含 s ，那么不管怎么走 s \rightarrow u ，都有剩下来的图中任意最大匹配包含 s ，这样后手就必胜了。

这样可以发现 10^9 和 1 是等价的，因为前者的匹配总是可以调整成每层独立的结构。

于是我们就是要求原图的最大匹配和包含起点的最大匹配。

先将 a 和 b 排序。现在一定有一条从左下到右上的折线，左上方是右部点（1），右下方是左部点（0）。

我们转而求最大独立集，即每行每列要么全选1要么全选0.

两个结论：

• 一定存在 (x,y)，最中方案是选所有 (x_i \leq x, y_i \leq y) 的1和 (x_i > x, y_i > y) 的0.
• 当 x 增大时，对应最优的 y 随之增大。

证明待补。这样双指针即可。总复杂度 O((n + m) \log A) 。

#include <bits/stdc++.h>
#define DEBUG

#define For(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define rFor(i, b, a) for (int i = b, i##end = a; i >= i##end; --i)
#define eFor(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].next, v = e[i].to)

typedef long long ll;

typedef std::pair<int, int> pii;
#define fi first
#define se second

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T> 
T myrand(T l, T r) {
    return std::uniform_int_distribution<T>(l, r)(rnd);
}

template<typename T, typename ...Args> 
void LOG(T str, Args ...args) {
#ifdef DEBUG
    fprintf(stderr, str, args...);
#endif
}

#define fre(s) freopen(#s ".in", "r", stdin), freopen(#s ".out", "w", stdout)

const int kN = 2e5 + 5;

int n, m, a[kN], b[kN], sa, sb, pa, pb;
int rm[kN], cm[kN], px, py, sr[kN], sc[kN];
ll pre[kN];

inline ll calc(int i, int j, bool ex) {
    ll res = pre[i];
    if (sr[j + 1]) res -= pre[std::min(sr[j + 1], i)] - (ll)std::min(sr[j + 1], i) * j;
    res += (ll)(n - i) * (m - j);
    if (sr[j + 1] > i) {
        res -= pre[sr[j + 1]] - pre[i] - (ll)(sr[j + 1] - i) * j;
    }
    if (ex && pa > i && pb > j) --res;
    // LOG("calc %d %d %d = %lld\n", i, j, ex, res);
    return res;
}

bool check(int mid) {
    if (sa + sb <= mid) return true;
    rm[0] = m;
    For(i, 1, n) {
        rm[i] = rm[i - 1];
        while (rm[i] && a[i] + b[rm[i]] > mid) --rm[i];
        pre[i] = pre[i - 1] + rm[i];
        // LOG("rm[%d] = %d\n", i, rm[i]);
    }
    cm[0] = n;
    For(i, 1, m) {
        cm[i] = cm[i - 1];
        while (cm[i] && a[cm[i]] + b[i] > mid) --cm[i];
    }
    memset(sr, 0, sizeof(sr));
    For(i, 1, n) ++sr[rm[i]];
    rFor(i, m, 1) sr[i] += sr[i + 1];
    ll id0 = 0, id1 = 0;
    for (int i = 0, j = 0; i <= n; ++i) {
        while (j < m && calc(i, j + 1, 0) > calc(i, j, 0)) ++j;
        id0 = std::max(id0, calc(i, j, 0));
    }
    for (int i = 0, j = 0; i <= n; ++i) {
        while (j < m && calc(i, j + 1, 1) > calc(i, j, 1)) ++j;
        id1 = std::max(id1, calc(i, j, 1));
    }
    // LOG("id0 = %lld id1 = %lld\n", id0, id1);
    assert(id0 >= id1 && id0 <= id1 + 1);
    return id0 < id1 + 1;
}

int main() {
    // freopen("in", "r", stdin);
    fre(chess);
    scanf("%d%d", &n, &m);
    For(i, 1, n) scanf("%d", &a[i]);
    For(i, 1, m) scanf("%d", &b[i]);
    sa = a[1], sb = b[1];
    std::sort(a + 1, a + n + 1);
    std::sort(b + 1, b + m + 1);
    pa = std::lower_bound(a + 1, a + n + 1, sa) - a;
    pb = std::lower_bound(b + 1, b + m + 1, sb) - b;
    int l = 0, r = 1e9;
    // LOG("res %d\n", check(3));
    // return 0;
    while (l < r) {
        // LOG("%d %d\n", l, r);
        int mid = (l + r) >> 1;
        // LOG("%d\n", mid);
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d", l);
    return 0;
}
/* PAY ATTENTION TO: */
/* 1. Memory Limit, Array Size */
/* 2. Integer Overflow */
/* 3. Multi-test */
/* 4. Potential Constant-speedup */
/* Stay organized and write things down. */