2024 年 7 月做题笔记

写在之前

算是开始归队了吧。感觉过去一年里文化课水平突飞猛进（飞升b(x)），算是找到了一点新的方向。

附上一张今天现拍的照片（x

访问这里

（图片背景经过处理）

因为 0727 才放假所以没做几个题（

（2024/7/28）「SNOI2017」炸弹

LOJ | Luogu

这道题第一眼看过去会想到一个暴力做法。建图，然后跑一堆 dfs 什么的。但是很明显时间复杂度是不行的（O(n^2) + O(n^2) \Rightarrow O(n^2)），于是想怎么优化。

根据我之前写过的 线段树优化建图，因为本题目涉及到 从点连向区间 的情况，那么可以使用这个优化技巧。之后你会发现，一个炸弹炸出来的所有点不正好是一个区间嘛（到这里其实跟「CEOI 2011」Traffic 的后面有点像，但是这里区间性质要更好想一点）！因此思路便明了了：线段树建图，然后跑 Tarjan 算 SCC 然后缩点，跑一遍拓扑，维护区间的左端点和右端点。

写过线段树优化建图的可能思维难度会低很多。

// 线段树最大节点编号
int ND_MX = 0;
// 节点 [p, p] 对应图上的点编号
int nd[4 * MAXN];
// 图和反图
vector<int> gr[4 * MAXN], reg[4 * MAXN];

inline void add_edge(int u, int v) { gr[u].push_back(v); }
struct Segt { int l, r; } tr[4 * MAXN];
struct Bomb { ll pos, rad; } bmb[MAXN];
struct Range { int l, r; /* 这里实现了一个 extend 方法 */ void extend(const Range& rhs) { l = min(l, rhs.l); r = max(r, rhs.r); } } vs[4 * MAXN];
struct Cmp { ll a, id; bool operator<(const Cmp& o) const { return a < o.a; } };


namespace SGraph {

    void build(int l, int r, int p = 1)
    {
        tr[p].l = l; tr[p].r = r;
        ND_MX = max(ND_MX, p);
        if (l == r) return nd[l] = p, void();
        int m = (l + r) / 2;
        build(l, m, p << 1), build(m + 1, r, p << 1 | 1);
        add_edge(p, p << 1), add_edge(p, p << 1 | 1);
    }

    void connect_from_range(int from, int l, int r, int p = 1)
    {
        if (tr[p].l > r || tr[p].r < l) return;
        if (l <= tr[p].l && tr[p].r <= r) return add_edge(nd[from], p);
        connect_from_range(from, l, r, p << 1);
        connect_from_range(from, l, r, p << 1 | 1);
    }
} // namespace Graph

namespace Tarjan {

    int dfn[MAXN * 4], low[MAXN * 4], cnt, ins[MAXN * 4], scc[MAXN * 4], scccnt;
    stack<int> st;

    void dfs(int u)
    {
        low[u] = dfn[u] = ++cnt; ins[u] = 1; st.push(u);
        for (auto v : gr[u]) {
            if (!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
            else if (ins[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            ++scccnt; int v;
            do {
                v = st.top(); st.pop(); ins[v] = 0; scc[v] = scccnt;
                if (vs[scccnt].l == 0) {
                    // v: 线段树区间对应的点
                    vs[scccnt] = { tr[v].l, tr[v].r };
                } else {
                    vs[scccnt].extend({ tr[v].l, tr[v].r });
                }
            } while (v != u);
        }
    }
} // namespace Tarjan

int n;

using Tarjan::scc;

namespace Topo {

    queue<int> q;
    int deg[4 * MAXN];
    using Tarjan::scccnt;

    inline void exec()
    {
        for (int i = 1; i <= scccnt; i++) {
            if (!deg[i]) q.push(i);
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto v : reg[u]) {
                vs[v].extend(vs[u]);
                if (!--deg[v]) q.push(v);
            }
        }
    }
} // namespace Topo

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n; SGraph::build(1, n);

    // 按理说这个地方应该开一个数组然后排序 但是我没有
    set<Cmp> st;
    for (int i = 1; i <= n; i++) {
        ll pos, rad; cin >> pos >> rad;
        st.insert({ pos, i });
        bmb[i] = { pos, rad };
    }
    for (int i = 1; i <= n; i++) {
        ll pos = bmb[i].pos, rad = bmb[i].rad;
        // 分成左半和右半区间 这样可以少考虑一点边界
        auto lower = st.lower_bound({ pos - rad });
        auto upper = --st.upper_bound({ pos + rad });
        if (lower != st.end() && lower->id < i) SGraph::connect_from_range(i, lower->id, i - 1);
        if (upper != st.end() && upper->id > i) SGraph::connect_from_range(i, i + 1, upper->id);
    }
    for (int i = 1; i <= ND_MX; i++) if (!Tarjan::dfn[i]) Tarjan::dfs(i);
    // 缩点（直接建反向边）
    for (int u = 1; u <= ND_MX; u++) {
        for (auto v : gr[u]) {
            if (scc[u] != scc[v]) {
                reg[scc[v]].push_back(scc[u]);
                Topo::deg[scc[u]]++;
            }
        }
    }
    // 拓扑！
    Topo::exec();
    // 答案！
    ll ans = 0;
    const ll MODN = 1e9 + 7;
    for (int i = 1; i <= n; i++) {
        Range& res = vs[scc[nd[i]]];
        (ans += 1ll * i * (res.r - res.l + 1)) %= MODN;
    }
    cout << ans << '\n';
}

（2024/7/28）「CF1991B」AND Reconstruction

题意：给你 n-1 个数字 b_i，让你构造一个有 n 个元素的序列 a 使得每个 a_i \& a_{i+1}=b_i（& = 按位与），构造不了输出 -1。

那么我们可以把这个问题拆分一下，看一看每个数字的每一位是一个什么情况。不难发现，b_i 的第 j 位为 1 的充要条件是 a_i 和 a_{i+1} 的第 j 位都为 1。所以，把 a_i、a_{i+1} 的对应位数设置成 1，最后判断是否可以满足条件即可。

inline void solve()
{
    int n; cin >> n;
    vector<int> b(n - 1), a; for (auto& x : b) cin >> x;
    const int FULL = (1 << 30) - 1;
    vector<bitset<30>> bs(n);
    for (int j = 0; j < 30; j++) {
        for (int i = 0; i < n - 1; i++) {
            if (b[i] & (1 << j)) {
                bs[i][j] = 1;
                bs[i + 1][j] = 1;
            }
        }
    }
    // check
    for (int i = 1; i < n; i++) {
        if ((bs[i].to_ulong() & bs[i - 1].to_ulong()) != b[i - 1]) {
            cout << "-1\n";
            return;
        }
    }
    for (int i = 0; i < n; i++) cout << bs[i].to_ulong() << ' ';
    cout << '\n';
}