小白月赛 Round 122 题解，C++ version。

A 大话骰子

存一下每个点数出现的次数，查表输出即可。

void solve() {
    vector<int> a(7);
    for (int i = 0, x; i < 12; ++i) {
        cin >> x;
        a[x]++;
    }
    int x, y;
    cin >> x >> y;
    cout << (a[y] < x ? "win" : "lose") << "\n";
}

B max-mid

元素只有 和 ，如果 个数大于 ，就可以全选使得 ，或者 的数量大于等于 ，就能使取到的 。剩下的情况差为 。

void solve() {
    int n, k, c1 = 0;
    cin >> n >> k;
    for (int i = 0, x; i < n; ++i) cin >> x, c1 += x == 1;
    if (n - c1 >= k) {
        cout << 0 << "\n";
    } else if (c1 >= k / 2 + 1) {
        cout << 0 << "\n";
    } else {
        cout << 1 << "\n";
    }
}

C 糟糕的手法

• 如果非 数字个数小于等于 ，就一定无法达到。
• 可以使用负数和 ​ 使正数变少，也可以用一个负数让正数变多。
  • 如果有 或者负数，正数最少为 个。
  • 如果有至少两个负数，正数最多增加负数个数 。

void solve() {
    int n, m, neg = 0, pos = 0, z = 0;
    cin >> n >> m;
    for (int i = 0, x; i < n; ++i) cin >> x, neg += x < 0, pos += x > 0, z += x == 0;

    if (n - z < m) {
        cout << -1 << "\n";
        return;
    }

    if (m < ((neg || z) ? 0 : pos) || m > (neg ? n - z - 1 : pos)) {
        cout << -1 << "\n";
        return;
    }
    cout << abs(pos - m) << "\n";
}

D x_to_y_2

因为可以或上任意整数，所以很容易得到最优解最多或一次。

所以我们构造 右移 或 右移 的操作序列。

枚举或的位置即可。

注意剪枝。

void solve() {
    ll x, y, ans = INF;
    cin >> x >> y;
    if (x == y) {
        cout << 0 << "\n";
        return;
    }
    for (ll i = 0; i <= 60; ++i) {
        if (i >= ans) break;
        ll xx = x >> i;
        for (ll j = 0; j <= 60; ++j) {
            if (i + j >= ans) break;
            i128 l = (i128)y << j;
            i128 r = (((i128)y + 1) << j) - 1;
            if ((i128)xx > r) continue;
            if ((i128)xx >= l && (i128)xx <= r) {
                ans = min(ans, i + j);
            } else {
                i128 cand = (i128)xx | l;
                if (cand <= r) {
                    ans = min(ans, i + j + 1);
                }
            }
        }
        if (xx == 0) break;
    }
    if (ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";
}

E AsubB

实际上是串 在前缀匹配一部分，后缀匹配一部分，所以 找以第 位为开头的子串为前缀子序列的最长子串长度 ，以及第 位为结尾的子串为后缀子序列的最长子串长度 ，答案为

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    vector<vector<Z>> dp1(n + 1, vector<Z>(M));
    dp1[0][0] = 1;
    for (int x : a) {
        int v = x % M;
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j < M; ++j) {
                int nj = (j + v) % M;
                dp1[i][nj] += dp1[i - 1][j];
            }
        }
    }

    vector<vector<Z>> dp2(n + 1, vector<Z>(M));
    dp2[0][0] = 1;
    for (int x : b) {
        int v = x % M;
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j < M; ++j) {
                int nj = (j + v) % M;
                dp2[i][nj] += dp2[i - 1][j];
            }
        }
    }

    vector<vector<Z>> pre(n + 1, vector<Z>(M));
    for (int j = 0; j < M; ++j) {
        Z s = 0;
        for (int i = 0; i <= n; ++i) {
            s += dp2[i][j];
            pre[i][j] = s;
        }
    }

    vector<Z> ans(M);
    for (int i = 0; i <= n; ++i) {
        bool f1 = true, f2 = true;
        for (int j = 0; j < M; ++j) {
            if (dp1[i][j].val() != 0) {
                f1 = false;
                break;
            }
        }
        if (f1) continue;
        for (int j = 0; j < M; ++j) {
            if (pre[i][j].val() != 0) {
                f2 = false;
                break;
            }
        }
        if (f2) continue;

        for (int rA = 0; rA < M; ++rA) {
            if (dp1[i][rA].val() == 0) continue;
            for (int rB = 0; rB < M; ++rB) {
                if (pre[i][rB].val() == 0) continue;
                int t = (rA + rB) % M;
                ans[t] += dp1[i][rA] * pre[i][rB];
            }
        }
    }

    for (int i = 0; i < M; ++i) cout << ans[i] << " ";
    cout << "\n";
}

F v_calc

按位置从左到右构造序列，用 表示“目前到达位置 （下一步要决定 ）且 的有效前缀个数”。

现在要从 推 （表示位置 的取值分布）：对每个可能的前值 （即 ），枚举 的所有允许取值并把 的贡献累加到 上。

一个约束涉及三项 ，所以在不同迭代步（奇/偶）我们可以把约束转换成只和 与 有关的形式：

• 把位置 当作 “决定 ” 的步骤，并把约束拆成两类处理：

  • 偶数：更新 时，允许 落在若干 闭区间上（由 和前值 导出），于是可以用区间差分把 的贡献批量加到 ndp 上（O(1) 加区间，随后做前缀得到 ndp）。

  • 奇数：允许 满足 () 在一个区间 上（因为原式可以等价转为这种形式），这就是一个按位异或的区间条件。对于固定 ，满足 的 集合可以按 位贪心分解为至多 个闭区间，我们将用这些段做差分加/减来得到 。

vector<bool> vis(m);
vector<vector<vector<PII>>> g(m);

void calc(int x) {
    if (vis[x]) return;
    g[x].assign(m, {});
    for (int y = 0; y < m; ++y) {
        vector<pair<int, int>> seg;
        if (y >= 0) {
            int p = 0;
            for (int i = b - 1; i >= 0; --i) {
                if ((y >> i) & 1) {
                    if ((x >> i) & 1) {
                        seg.eb(p | (1 << i), p | ((1 << (i + 1)) - 1) );
                    } else {
                        seg.eb(p, p | ((1 << i) - 1) );
                        p |= (1 << i);
                    }
                } else {
                    if ((x >> i) & 1) p |= (1 << i);
                }
            }
            seg.eb(p, p);
        }
        g[x][y] = move(seg);
    }
    vis[x] = 1;
}

void init() {

}

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

    if (n == 1) {
        cout << Z(a[1] + 1) << "\n";
        return;
    }

    vector<Z> dp(m);
    for (int i = 0; i <= a[1]; ++i) dp[i] += 1;

    for (int i = 2; i <= n; ++i) {
        vector<Z> ndp(m);
        for (int j = 0; j < m; ++j) {
            if (!dp[j].val()) continue;
            Z  cur = dp[j];
            if (i & 1) {
                calc(j);

                if (r[i - 1] >= 0) {
                    int yi = min(r[i - 1], m - 1);
                    const auto &segr = g[j][yi];
                    for (auto &seg : segr) {
                        int l = max(0, seg.fi);
                        int r = min(a[i], seg.se);
                        if (l > r) continue;
                        ndp[l] += cur;
                        if (r + 1 < m) ndp[r + 1] -= cur;
                    }
                }
                if (l[i - 1] - 1 >= 0) {
                    int yi = min(l[i - 1] - 1, m - 1);
                    const auto &segl = g[j][yi];
                    for (auto &seg : segl) {
                        int l = max(0, seg.fi);
                        int r = min(a[i], seg.se);
                        if (l > r) continue;
                        ndp[l] -= cur;
                        if (r + 1 < m) ndp[r + 1] += cur;
                    }
                }
            } else {
                if (j >= a[i]) {
                    int l = j - a[i];
                    ndp[l] += cur;
                    if (j + 1 < m) ndp[j + 1] -= cur;
                } else {
                    ndp[0] += cur;
                    if (j + 1 < m) ndp[j + 1] -= cur;
                    if (1 < m) ndp[1] += cur;
                    int pos = a[i] - j + 1;
                    if (pos < m) ndp[pos] -= cur;
                }
            }
        }
        for (int i = 1; i < m; ++i) ndp[i] += ndp[i - 1];
        dp.swap(ndp);
    }
    Z ans = 0;
    for (int i = 0; i < m; ++i) ans += dp[i];
    cout << ans << "\n";
}

头文件

//Another
#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); cout.tie(0);

    init();

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

自动取模

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(long long v) : x{norm(v % getMod())} {}

    static int Mod;
    constexpr static int getMod() {
        if (P > 0) return P;
        else return Mod;
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr static int norm(long long v) {
        if (v < 0) v += getMod();
        if (v >= getMod()) v -= getMod();
        return int(v);
    }

    constexpr int val() const { return x; }
    explicit constexpr operator int() const { return x; }

    constexpr MInt operator-() const {
        return MInt(norm(getMod() - x));
    }

    constexpr MInt inv() const {
        assert(x != 0);
        return pow(getMod() - 2);
    }

    constexpr MInt pow(long long e) const {
        MInt res(1), base(*this);
        while (e > 0) {
            if (e & 1) res *= base;
            base *= base;
            e >>= 1;
        }
        return res;
    }

    constexpr MInt &operator*=(MInt rhs) & {
        x = int(1LL * x * rhs.x % getMod());
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }

    friend constexpr MInt operator*(MInt lhs, MInt rhs) { return lhs *= rhs; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { return lhs += rhs; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { return lhs -= rhs; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { return lhs /= rhs; }

    friend istream &operator>>(std::istream &is, MInt &a) {
        long long v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }

    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
};

template<>
int MInt<0>::Mod = 998244353;

typedef MInt<MOD> Z;