牛客练习赛 Round 146
|
18
|
0
|
牛客,练习赛,题解

2992 字
|
45 分钟

A 合格的机器

假设最后有 $k$​ 台机器符合要求。

由于转移操作要求源机器代币数 $\geq 2$ ，因此我们无法将一个代币数为 $1$ 的机器变成 $0$ 。这意味着所有机器的代币数始终 $\geq 1$ 。

先算上界，每个偶数机都是 $2$ ，奇数机都是 $1$ ，有
$$sum = 2k+(n-k) = n+k$$
所以有 $k\leq sum-n$ 。

整体代币之和 $sum$ 的奇偶性决定了最终奇数机器个数的奇偶性：
$$n-k\equiv sum \pmod 2 \Rightarrow k\equiv n-sum \pmod 2$$
综上，合法的 $k$ 需要满足：
$$0\leq k\leq min(n,sum-n)，\ k\equiv n-sum\pmod 2$$
因此答案就是在区间 $[0,\ \min(n,sum-n)]$ 中最大的满足上述同余的整数。

时间复杂度 $O(n)$​

需要注意 $C++$ 中负数取模会返回负数。

void solve() {
    int n, sum = 0;
    cin >> n;
    for (int i = 0, x; i < n; ++i) cin >> x, sum += x;
    ll ans = min(n, sum - n);
    if (ans % 2 != (sum - n) % 2) ans--;
    cout << ans << "\n";
}

B 小灰灰的火焰星球2

由于 $h$ 单调不增，所以满足 $h_j<x$ 的点一定是某个下标 $pos$ 到 $n$ 的后缀（或者没有符合的点）。

每天可选最多两个温度小于 $x$ 的点，并且学分每天刷新（不同天可以重复选同一位置）。因此每天的最优策略就是，在该后缀中选择值最大的两个 $v$（若不足两个则选所有）。

整体问题就变成：对每个可能的后缀位置 $i$ 预处理出后缀最大值和第二大值 mx[i]、smx[i]，然后对每天的 $x$ ：

  1. 二分找最小下标 pos 使得 h[pos] < x（若不存在则当天得 0）。
  2. 当天能得 mx[pos] + smx[pos]（若只有一个元素，则 smx[pos]=0）。

所以只需一次从后往前线性构造后缀的前两大，随后每个查询做一次二分并取表值即可。

时间复杂度 $O(n+Tlogn)$

void solve() {
    int n, t;
    cin >> n >> t;
    vector<int> h(n), v(n);
    for (int i = 0; i < n; ++i) cin >> h[i], h[i] = -h[i];
    for (int i = 0; i < n; ++i) cin >> v[i];

    vector<int> mx(n + 1), smx(n + 1);
    for (int i = n - 1; i >= 0; --i) {
        int a = v[i];
        int b1 = mx[i + 1], b2 = smx[i + 1];
        if (a >= b1) mx[i] = a, smx[i] = b1;
        else if (a >= b2) mx[i] = b1, smx[i] = a;
        else mx[i] = b1, smx[i] = b2;
    }

    ll ans = 0;
    while (t--) {
        int x;
        cin >> x;
        int pos = upper_bound(all(h), -x) - h.begin();
        if (pos == n) continue;
        ans += mx[pos] + smx[pos];
    }

    cout << ans << "\n";
}

C 盲目自大的小灰灰

令初始位置为左（记作 $0$ ），跳一次翻面并得 1 分。第 $t$ 秒开始前可以跳（即在每个秒点前可选是否跳）。

对每个机关 $(t_i, x_i)$ ，在时刻 $t_i$ 时必须不在 $x_i$（因为机关立即伸出）。令 $p_i = 1 – x_i$ ，则在 $t_i$ 时刻（做完可选跳之后）的位置 $== p_i$​ 。

把时间按机关时刻划分为若干段：第一段 $1\sim t_1$，第二段 $t_1+1\sim t_2$，……，第 $m$ 段 $t_{m-1}+1\sim t_m$ ，尾段 $t_m+1\sim n$（尾段没有被机关强制奇偶）。

对于每一段（除尾段外），段内跳跃次数必须满足一个固定的奇偶性（由相邻两个 $p$ 的异或给出），且段内跳数范围是 $[0, len]$ 。因此每段能取的最小值是该段的最小同奇偶数（即 $r$ ），最大值是 $len$ 或 $len-1$（使其与所需奇偶一致）。

令前 $m$ 段的最小和为 $flr$ ，最大和为 $cel$。尾段长度为 $tail$ 。

  • 若 tail == 0（没有尾段），则总跳数只能在 [flr, ceil] 且与 floor 同奇偶（步长 2）。
  • 若 tail >= 1，最后一个陷阱之后，只要时间允许，可以任意消耗偶数时间来增加分数（反复横跳），或者通过改变终点来调整奇偶性，从而可以把可达集合填成连续区间 $[flr, cel + tail]$ 。

因此对于查询的目标分 $s$ ：

  • 若无机关（ m==0 ），任何 $0\sim n$ 都可；
  • 否则按上述规则判断 s 是否落在可达集合内。

时间复杂度 $O(m+T)$

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> t(m), p(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        t[i] = u;
        p[i] = 1 - v;
    }
    bool f = 0;
    if (m == 0) {
        f = 1;
    }

    ll flr = 0, cel = 0;
    int prev = 0;
    for (int i = 0; i < m; i++) {
        int len = t[i] - prev;
        int r;
        if (i == 0) r = p[0];
        else r = p[i] ^ p[i - 1];
        int mn = r;
        int mx = (len % 2 == r) ? len : (len - 1);
        flr += mn;
        cel += mx;
        prev = t[i];
    }
    int tail = n - prev;

    int T;
    cin >> T;
    while (T--) {
        int x;
        cin >> x;
        bool ok = false;
        if (f) {
            ok = true;
        } else {
            if (tail == 0) {
                if (x >= flr && x <= cel && ((x % 2 + 2) % 2) == (flr % 2 + 2) % 2) ok = true;
            } else {
                if (x >= flr && x <= cel + tail) ok = true;
            }
        }

        cout << (ok ? "Yes" : "No") << "\n";
    }
}

D 手动机

把格子记作节点，四个方向为边。考虑两类移动：

  • 自动移动：按字符串 $s$ 中出现过的方向（记作集合 $D$ ）之一进行移动；这种移动不消耗手动次数，因为我们可以在执行该移动前通过“等待”把时间对齐到某个 $s[i]$ 等于该方向；
  • 手动移动：任意方向立即手动移动，消耗 1 次手动移动。

最小手动次数：

  • 对于每条邻边，若其方向属于 $D$ 则权重为 $0$ ，否则权重为 $1$ 。
  • 在无时间约束下，从起点到终点最少需要的手动移动数就是在该加权图上的 $0-1$ 最短路得到的最小代价 $K$ 。

在保证手动次数为最小 K 的前提下最早到达时间：

  • 我们限制只走满足 0-1 最短路结构的边：即只考虑那些从 u 到 v 满足 dist[v] == dist[u] + cost(edge) 的边（任何到达终点且手动次数为最小的路径必然只走这些边）。
  • 在这子图上计算最短到达时间时，边的时间代价会依赖到达 $u$ 时的时间模 $len$ ：
  • 若边是手动边（ $cost = 1$ ），直接花 $1$ 秒即可；
  • 若边是自动边（ $cost = 0$ ，方向为 $dir$），你需要先等待若干秒使当前时间所对应的 $s[index] == dir$ ，设最小等待为 $delta$（ $0\leq delta < len$），则总耗时为 $delta + 1$（等待 $delta$ 秒再执行一次自动移动）。
  • 于是可以在限制的子图上跑 $Dijkstra$ ，距离值表示绝对时间，在松弛某条自动边时根据当前时间 $t$ 用预处理的 $nxt[dir][t \% len]$ 得到 $delta$ 并计算权重 $delta+1$​ 。

时间复杂度 $O(nm+|s|log\ occ+(nm)log(nm))$

vector<char> dirs = {'U', 'D', 'L', 'R'};
int dx[] = { -1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    int len = s.size();
    vector<string> g(n);
    for (int i = 0; i < n; ++i) cin >> g[i];

    auto dir = [&](char c)->int{
        if (c == 'U') return 0;
        if (c == 'D') return 1;
        if (c == 'L') return 2;
        return 3;
    };

    vector<bool> apr(4, false);
    for (char c : s) apr[dir(c)] = true;

    int N = n * m;
    auto check = [&](int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    };
    auto encode = [&](int x, int y) {
        return x * m + y;
    };
    int st = encode(0, 0), ed = encode(n - 1, m - 1);

    vector<int> dist(N, inf);
    deque<int> dq;
    dist[st] = 0;
    dq.pb(st);
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        int x = u / m, y = u % m;
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (!check(nx, ny)) continue;
            if (g[nx][ny] == '#') continue;
            int v = encode(nx, ny);
            int w = apr[d] ? 0 : 1;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }

    if (dist[ed] == inf) {
        cout << "-1 -1" << "\n";
        return;
    }

    vector<vector<int>> pos(4);
    for (int i = 0; i < len; ++i) pos[dir(s[i])].pb(i);

    vector<vector<int>> nxt(4, vector<int>(len, -1));
    for (int d = 0; d < 4; ++d) {
        if (pos[d].empty()) continue;
        for (int r = 0; r < len; ++r) {
            auto it = lower_bound(all(pos[d]), r);
            if (it != pos[d].end()) {
                nxt[d][r] = (*it) - r;
            } else {
                nxt[d][r] = (pos[d][0] + len) - r;
            }
        }
    }

    vector<ll> dist2(N, INF);
    priority_queue<PLL> pq;
    dist2[st] = 0;
    pq.emplace(0, st);

    while (!pq.empty()) {
        auto [t, u] = pq.top();
        pq.pop();
        t = -t;
        if (t != dist2[u]) continue;
        if (u == ed) break;
        int x = u / m, y = u % m;
        int tmod = t % len;
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (!check(nx, ny)) continue;
            if (g[nx][ny] == '#') continue;
            int v = encode(nx, ny);
            int cost = apr[d] ? 0 : 1;
            if (dist[v] != dist[u] + cost) continue;
            ll add;
            if (cost == 1) {
                add = 1;
            } else {
                int delta = nxt[d][tmod];
                if (delta < 0) continue;
                add = delta + 1;
            }
            ll nt = t + add;
            if (nt < dist2[v]) {
                dist2[v] = nt;
                pq.emplace(-nt, v);
            }
        }
    }

    cout << dist[ed] << " " << dist2[ed] << "\n";
}

E 小机器人

对区间 $[L,R]$ 找最小值并 $+1$​ ，这个操作会不断填平坑。当最小值增加到等于次小值时，它们可以被看作一个整体一起增加。

在每一轮操作中，扫描区间找出最小值 $mn$、次小值 $smn$ 以及最小值的个数 $cnt$ 。

如果 $K$ 很大，我们不需要一次次加，而是计算 $step=min⁡(K/cnt,smn−mn)$ ，直接让所有最小值增加 $step$​。这样每次操作要么耗尽 $K$ ，要么将一种数值“合并”到更高阶层。由于 $N$ 较小 (8000)，且 $M$ 不大，这种“水平面上升”的模拟非常高效。

$T$​ 了就分块。

时间复杂度 $O(N(N+M))$

constexpr int B = 65;

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int m;
    cin >> m;

    vector<int> pos;

    while (m--) {
        int L, R;
        ll K;
        cin >> L >> R >> K;
        if (L > R) continue;
        if (K == 0) continue;

        while (K > 0) {
            ll cur = INF;
            ll nxt = INF;
            pos.clear();

            int st = L;
            int ed = R;
            int i = st;
            for (; i + B - 1 <= ed; i += B) {
                for (int j = i; j < i + B; ++j) {
                    ll v = a[j];
                    if (v < cur) {
                        nxt = cur;
                        cur = v;
                        pos.clear();
                        pos.pb(j);
                    } else if (v == cur) {
                        pos.pb(j);
                    } else if (v < nxt) {
                        nxt = v;
                    }
                }
            }
            for (; i <= ed; ++i) {
                ll v = a[i];
                if (v < cur) {
                    nxt = cur;
                    cur = v;
                    pos.clear();
                    pos.pb(i);
                } else if (v == cur) {
                    pos.pb(i);
                } else if (v < nxt) {
                    nxt = v;
                }
            }

            if (cur == INF) break;

            ll cnt = pos.size();
            if (cnt == 0) break;

            if (nxt == INF) {
                ll each = K / cnt;
                if (each > 0) {
                    for (int idx : pos) a[idx] += each;
                    K -= each * cnt;
                }
                ll rem = K;
                for (int t = 0; t < rem; ++t) a[pos[t]] += 1;
                K = 0;
                break;
            } else {
                ll diff = nxt - cur;
                ll need = diff * cnt;
                if (K >= need) {
                    for (int idx : pos) a[idx] += diff;
                    K -= need;
                } else {
                    ll each = K / cnt;
                    if (each > 0) {
                        for (int idx : pos) a[idx] += each;
                        K -= each * cnt;
                    }
                    ll rem = K;
                    for (int t = 0; t < rem; ++t) a[pos[t]] += 1;
                    K = 0;
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << a[i] << " ";
    }
    cout << "\n";
}

F 独特的方格

令 $N\leq M$ ，$N\times M\leq 10^5$ ，有 $N\leq 316$ ，所以我们很自然会想到 $O(N^2M)$ 的做法

我们枚举行区间 $[r_1,r_2]$ ，将二维问题转化为一维问题：

  • 在行区间 $[r_1,r_2]$ 固定的情况下，我们要统计有多少个列区间 $[c_1,c_2]$ ，使得该子矩形内没有重复颜色。
  • 设 $prev_[j]$ 表示以第 $j$ 列为右边界时，为了不包含重复颜色，左边界必须严格大于的位置（即左边界 $L>prev_[j]$ ）。
  • 对于固定的 $j$ ，合法区间的数量为 $j−prev_[j]$（即 $L$ 可以取 $[prev_[j]+1,j]$ ）。
  • $prev_[j]$ 取决于当前行区间内，列 $j$ 的颜色 $c$ 上一次出现的列位置 $p$ ，以及 $[p+1,j−1]$ 之间其他颜色冲突的限制。实际上，我们只需要维护一个全局的 $Limit$ ，$$Limit = max(Limit, \text{该列颜色冲突位置})$$。

外层循环枚举 $r_1$ ，内层循环扩展 $r_2$ 。每当 $r_2$ 增加 1 行，我们将新的一行元素加入当前状态：

  • 对于新行中的元素 $(r_2,j)$ ，颜色为 $c$ ：
  1. 垂直：如果颜色 $c$ 在 $[r_1,r_2−1]$ 的第 $j$ 列已经出现过，则当前列直接不可用，限制变为 $j$ 。
  2. 水平：我们需要找到颜色 $c$ 在当前所有行 $[r_1,r_2]$ 中，列 $j$ 的前驱列 $prev$ 和后继列 $next$ 。
    • 限制更新：$prev_[j] = max(prev_[j], prev)$ 。
    • 反向限制：$prev_[next] = max(prev_[next], j)$ 。

当然这样会 $TLE$ ，我们考虑优化。

维护每种颜色出现的列集合：

  • 稀疏：绝大多数颜色出现的次数很少。我们用 $vector$ 维护有序的列索引。
  • 插入/查询使用 lower_bound ，复杂度 $O(log⁡K+K)$ ，其中 $K$ 是该颜色出现的次数。由于 $K$ 很小，这非常快且省内存。
  • 稠密：当某种颜色出现的列数超过阈值（如 $128$ ）时，$vector$ 操作变慢。我们将其自动转换为 $Bitset$。
  • $Bitset$ 可以在 $O(M/64)$ 的时间内利用位运算极快地找到前驱和后继。
  • 这样就能解决极端数据（如大量同色点）导致的超时。

时间复杂度 $O(n^2m/64)$ 。

constexpr int LIM = 128;

struct Clr {
    bool f = false;
    vector<int> vec;
    Bitset mask;

    void clear() {
        if (f) {
            mask = Bitset();
            f = false;
        }
        vec.clear();
    }
};

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n, vector<int>(m));
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> g[i][j];
            mx = max(mx, g[i][j]);
        }
    }

    if (n > m) {
        vector<vector<int>> tmp(m, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                tmp[j][i] = g[i][j];
            }
        }
        g = tmp;
        swap(n, m);
    }

    vector<Clr> colors(mx + 1);
    vector<int> prev_(m), dirty, ds;
    vector<bool> f1(mx + 1, false), f2(mx + 1, false);


    ll ans = 0;

    for (int r1 = 0; r1 < n; ++r1) {
        for (int c : dirty) {
            colors[c].clear();
            f1[c] = false;
        }
        dirty.clear();
        fill(all(prev_), -1);

        for (int r2 = r1; r2 < n; ++r2) {
            for (int j = 0; j < m; ++j) {
                int c = g[r2][j];
                if (!f1[c]) {
                    f1[c] = true;
                    dirty.pb(c);
                }

                Clr& cd = colors[c];
                if (cd.f) {
                    cd.vec.pb(j);
                    if (!f2[c]) {
                        f2[c] = true;
                        ds.pb(c);
                    }
                } else {
                    auto it = lower_bound(all(cd.vec), j);
                    if (it != cd.vec.end() && *it == j) {
                        prev_[j] = max(prev_[j], j);
                    } else {
                        int p = -1, nx = -1;
                        if (it != cd.vec.begin()) {
                            p = *(it - 1);
                            prev_[j] = max(prev_[j], p);
                        }
                        if (it != cd.vec.end()) {
                            nx = *it;
                            prev_[nx] = max(prev_[nx], j);
                        }
                        cd.vec.insert(it, j);

                        if (cd.vec.size() >= LIM) {
                            cd.f = true;
                            cd.mask.resize(m);
                            for (int val : cd.vec) cd.mask.set(val);
                            cd.vec.clear();
                        }
                    }
                }
            }

            for (int c : ds) {
                Clr& cd = colors[c];
                if (cd.vec.empty()) continue;

                for (int k = 0; k + 1 < cd.vec.size(); ++k) {
                    int u = cd.vec[k];
                    int v = cd.vec[k + 1];
                    prev_[v] = max(prev_[v], u);
                }

                for (int x : cd.vec) {
                    int p = cd.mask.prev_set(x);

                    if (p != cd.mask.size()) {
                        if (p == x) {
                            prev_[x] = max(prev_[x], x);
                            int real_prev = cd.mask.prev_set(x - 1);
                            if (real_prev != cd.mask.size()) {
                                prev_[x] = max(prev_[x], real_prev);
                            }
                        } else {
                            prev_[x] = max(prev_[x], p);
                        }
                    }

                    int nx = cd.mask.next_set(x + 1);
                    if (nx != cd.mask.size()) {
                        prev_[nx] = max(prev_[nx], x);
                    }
                }

                for (int x : cd.vec) cd.mask.set(x);
                cd.vec.clear();
                f2[c] = false;
            }
            ds.clear();

            int limit = -1;
            for (int j = 0; j < m; ++j) {
                limit = max(limit, prev_[j]);
                ans += j - limit;
            }
        }
    }
    cout << ans << "\n";
}

头文件

//Anoth3r
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLLL;
typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
// typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;

constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1.0);
constexpr ld eps = 1e-10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}

void init() {

}

void solve() {

}

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

    init();

    int t = 1;
    // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}

Bitset

class Bitset {
public:
    using ull = uint64_t;
    static constexpr int WORD = 64;

private:
    vector<ull> data_;
    int nbits_;
    ull last_mask_;

    static constexpr int words_for(int bits) {
        return (bits + WORD - 1) / WORD;
    }

    void update_last_mask() {
        int r = nbits_ % WORD;
        if (r == 0) last_mask_ = ~ull(0);
        else last_mask_ = (1ull << r) - 1;
        if (!data_.empty()) data_.back() &= last_mask_;
    }

public:
    Bitset() : nbits_(0), last_mask_(~ull(0)) {}
    explicit Bitset(int n, bool val = false) : data_(words_for(n), val ? ~ull(0) : 0), nbits_(n) {
        update_last_mask();
        if (val && (nbits_ % WORD)) data_.back() &= last_mask_;
    }

    int size() const noexcept { return nbits_; }
    bool empty() const noexcept { return nbits_ == 0; }
    void reset() noexcept { fill(data_.begin(), data_.end(), 0); }
    void set() noexcept { fill(data_.begin(), data_.end(), ~ull(0)); if (!data_.empty()) data_.back() &= last_mask_; }

    void resize(int n, bool val = false) {
        int old_words = data_.size();
        nbits_ = n;
        int new_words = words_for(n);
        data_.resize(new_words, val ? ~ull(0) : 0);
        update_last_mask();
        if (val && new_words > 0 && (nbits_ % WORD)) data_.back() &= last_mask_;
    }

    void set(int pos) {
        if (pos >= nbits_) throw out_of_range("bit index out of range");
        data_[pos / WORD] |= (1ull << (pos % WORD));
    }
    void reset(int pos) {
        if (pos >= nbits_) throw out_of_range("bit index out of range");
        data_[pos / WORD] &= ~(1ull << (pos % WORD));
    }
    void flip(int pos) {
        if (pos >= nbits_) throw out_of_range("bit index out of range");
        data_[pos / WORD] ^= (1ull << (pos % WORD));
    }
    bool test(int pos) const {
        if (pos >= nbits_) throw out_of_range("bit index out of range");
        return (data_[pos / WORD] >> (pos % WORD)) & 1;
    }

    bool any() const noexcept {
        for (auto x : data_) if (x) return true;
        return false;
    }
    bool none() const noexcept { return !any(); }

    int count() const noexcept {
        int s = 0;
        for (auto x : data_) s += (int)__builtin_popcountll(x);
        return s;
    }

    Bitset& operator&=(const Bitset& o) {
        assert(nbits_ == o.nbits_);
        int m = data_.size();
        for (int i = 0; i < m; ++i) data_[i] &= o.data_[i];
        return *this;
    }
    Bitset& operator|=(const Bitset& o) {
        assert(nbits_ == o.nbits_);
        int m = data_.size();
        for (int i = 0; i < m; ++i) data_[i] |= o.data_[i];
        return *this;
    }
    Bitset& operator^=(const Bitset& o) {
        assert(nbits_ == o.nbits_);
        int m = data_.size();
        for (int i = 0; i < m; ++i) data_[i] ^= o.data_[i];
        if (!data_.empty()) data_.back() &= last_mask_;
        return *this;
    }
    Bitset operator~() const {
        Bitset r(*this);
        for (auto &x : r.data_) x = ~x;
        if (!r.data_.empty()) r.data_.back() &= r.last_mask_;
        return r;
    }

    friend Bitset operator&(Bitset a, const Bitset& b) { a &= b; return a; }
    friend Bitset operator|(Bitset a, const Bitset& b) { a |= b; return a; }
    friend Bitset operator^(Bitset a, const Bitset& b) { a ^= b; return a; }

    Bitset& operator<<=(int shift) {
        if (shift == 0 || nbits_ == 0) return *this;
        int word_shift = shift / WORD;
        int bit_shift = shift % WORD;
        int m = data_.size();
        if (word_shift >= m) {
            reset();
            return *this;
        }
        if (bit_shift == 0) {
            for (int i = m; i-- > word_shift; ) data_[i] = data_[i - word_shift];
        } else {
            for (int i = m; i-- > word_shift; ) {
                ull high = data_[i - word_shift] << bit_shift;
                ull low = 0;
                if (i - word_shift > 0) low = data_[i - word_shift - 1] >> (WORD - bit_shift);
                data_[i] = high | low;
            }
        }
        for (int i = 0; i < word_shift; ++i) data_[i] = 0;
        if (!data_.empty()) data_.back() &= last_mask_;
        return *this;
    }

    Bitset& operator>>=(int shift) {
        if (shift == 0 || nbits_ == 0) return *this;
        int word_shift = shift / WORD;
        int bit_shift = shift % WORD;
        int m = data_.size();
        if (word_shift >= m) {
            reset();
            return *this;
        }
        if (bit_shift == 0) {
            for (int i = 0; i + word_shift < m; ++i) data_[i] = data_[i + word_shift];
        } else {
            for (int i = 0; i + word_shift < m; ++i) {
                ull low = data_[i + word_shift] >> bit_shift;
                ull high = 0;
                if (i + word_shift + 1 < m) high = data_[i + word_shift + 1] << (WORD - bit_shift);
                data_[i] = low | high;
            }
        }
        for (int i = m - word_shift; i < m; ++i) data_[i] = 0;
        if (!data_.empty()) data_.back() &= last_mask_;
        return *this;
    }

    friend Bitset operator<<(Bitset a, int s) { a <<= s; return a; }
    friend Bitset operator>>(Bitset a, int s) { a >>= s; return a; }

    int next_set(int pos) const noexcept {
        if (pos >= nbits_) return nbits_;
        int idx = pos / WORD;
        unsigned offset = pos % WORD;
        ull w = data_[idx] & (~ull(0) << offset);
        if (w) return idx * WORD + __builtin_ctzll(w);
        ++idx;
        while (idx < data_.size()) {
            if (data_[idx]) return idx * WORD + __builtin_ctzll(data_[idx]);
            ++idx;
        }
        return nbits_;
    }

    int prev_set(int pos) const noexcept {
        if (nbits_ == 0) return nbits_;
        if (pos >= nbits_) pos = nbits_ - 1;
        int idx = pos / WORD;
        unsigned offset = pos % WORD;
        ull w = data_[idx] & ((offset == 63) ? ~ull(0) : ((1ull << (offset + 1)) - 1));
        if (w) return idx * WORD + (63 - __builtin_clzll(w));
        if (idx == 0) return nbits_;
        do {
            --idx;
            if (data_[idx]) return idx * WORD + (63 - __builtin_clzll(data_[idx]));
        } while (idx > 0);
        return nbits_;
    }

    template<typename F>
    void for_each_set(F f) const {
        int base = 0;
        for (int i = 0; i < data_.size(); ++i) {
            ull w = data_[i];
            while (w) {
                unsigned t = __builtin_ctzll(w);
                f(base + t);
                w &= w - 1;
            }
            base += WORD;
        }
    }

    string to_string() const {
        string s;
        s.reserve(nbits_);
        for (int i = 0; i < nbits_; ++i) s.push_back(test(nbits_ - 1 - i) ? '1' : '0');
        return s;
    }

    const ull* data() const noexcept { return data_.empty() ? nullptr : data_.data(); }
    ull* data() noexcept { return data_.empty() ? nullptr : data_.data(); }

    static Bitset from_string(const string& s) {
        Bitset bs(s.size());
        for (int i = 0; i < s.size(); ++i) {
            char c = s[s.size() - 1 - i];
            if (c == '1') bs.set(i);
            else if (c != '0') throw invalid_argument("invalid char in bitstring");
        }
        return bs;
    }
};
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇