〔补题〕2025 钉耙编程春季联赛（3）

（赛中+补题记录）

不是题解，更多是做题心得与评价。

1001 数列计数

组合数 $\dbinom{n}{m}$ 是奇数 $\iff n\&m=m$ 。如果某一位 $n$ 是 0，那 $m$ 只能是 0 没得选，否则有 1 0 两种选择。

和上次 1001 类似，枚举 $\ell$ 的前缀，把其中一位 1 变成 0 之后，这一位后面的 1 就可以任意选择变成 0。

Z res = 1;
for (int i = 0; i < n; i++) {
	int L = 0;  // 前缀
	int sum = 0;
	for (int bit = 30; bit >= 0; bit--) {
		if (l[i] >> bit & 1) {  // 这一位是 1 才能把 1 变成 0
			if (((a[i] & L) == L)) {  // 前缀要满足约束
				sum += 1 << __builtin_popcount(a[i] & ((1 << bit) - 1));  // a[i] 后缀 1 的数量
			}
			L |= 1 << bit;
		}
	}
	if ((a[i] & L) == L) {
		sum++;
	}
	res *= sum;
}
cout << res << endl;

1003 拼尽全力

还算常规的拓扑排序建模。

int n, m;
cin >> n >> m;
vector<int> a(m);
for (int i = 0; i < m; i++) {
	cin >> a[i];
}
vector b(m, vector<pair<int, int>>(n));
vector w(m, vector<int>(n));
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		cin >> b[j][i].first;
		b[j][i].second = i;
	}
	for (int j = 0; j < m; j++) {
		cin >> w[j][i];
	}
}
for (int j = 0; j < m; j++) {
	sort(b[j].begin(), b[j].end());
}
vector<int> act(n, 0);
vector<int> cur(m);
vector<int> Q;
auto check = [&] {
	for (int i = 0; i < m; i++) {
		int& j = cur[i];
		while (j < n && a[i] >= b[i][j].first) {
			if (++act[b[i][j].second] == m) {
				Q.push_back(b[i][j].second);
			}
			j++;
		}
	}
};
check();
for (int qi = 0; qi < Q.size(); qi++) {
	int id = Q[qi];
	for (int i = 0; i < m; i++) {
		a[i] += w[i][id];
	}
	check();
}
if (Q.size() == n) {
	cout << "YES" << endl;
} else {
	cout << "NO" << endl;
}

1005 修复公路

并查集作为签到有点难了。

Bonus：改成有向图并不好做。

1007 宝石商店

在 01 字典树上找，但要满足所需区间。

按 ST 表或者线段树的思路，将所需区间拆成若干小区间，维护每个小区间的信息，但复杂度略高，需要建 $n\log n$ 棵树。

字典树信息可减，所以给每个 $[1,i]$ 的前缀建树（有点像主席树）就行，这样把 $[\ell,r]$ 拆成两个小区间之差。总共只有 $n$ 棵树。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using ulll = unsigned __int128;

constexpr ull B = 30;

struct Trie {
    struct Unit {
        int nxt[2]{};
        int icnt{};
    };
    vector<Unit> U;

    Trie() { new_node(); }

    int new_node() {
        int p = U.size();
        U.push_back({});
        return p;
    }

    void insert(uint x, int p = 1) {
        U[p].icnt++;
        for (int bit = B; bit >= 0; bit--) {
            bool c = x >> bit & 1;
            if (!U[p].nxt[c]) U[p].nxt[c] = new_node();
            p = U[p].nxt[c];
            U[p].icnt++;
        }
    }

    // 字典树合并 返回新树
    // int merge(int x, int y) {
    //     if (!x || !y) return x | y;
    //     int p = new_node();
    //     U[p].icnt = U[x].icnt + U[y].icnt;
    //     for (int i = 0; i < 2; i++) {
    //         U[p].nxt[i] = merge(U[x].nxt[i], U[y].nxt[i]);
    //     }    
    //     return p;
    // }

    // 字典树合并 直接合并到x上
    int merge(int x, int y) {
        if (!x || !y) return x | y;
        U[x].icnt += U[y].icnt;
        for (int i = 0; i < 2; i++) {
            U[x].nxt[i] = merge(U[x].nxt[i], U[y].nxt[i]);
        }
        return x;
    }

    uint query(int l, int r, uint x) {
        uint max = 0;
        for (int bit = B; bit >= 0; bit--) {
            int c = x >> bit & 1 ^ 1;
            if (U[U[r].nxt[c]].icnt - U[U[l].nxt[c]].icnt > 0) {
                max |= 1u << bit;
                l = U[l].nxt[c], r = U[r].nxt[c];
            } else {
                l = U[l].nxt[!c], r = U[r].nxt[!c];
            }
        }
        return max;
    }
};

int main() {
	int J;
	cin >> J;
	while (J--) {
		int n, q;
		cin >> n >> q;
		vector<int> pre(n + 1);
		Trie trie;
		pre[0] = trie.new_node();
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			int rt = trie.new_node();
			trie.insert(x, rt);
			pre[i + 1] = trie.merge(rt, pre[i]);
		}
		while (q--) {
			int l, r, x;
			cin >> l >> r >> x;
			l--;
			cout << (trie.query(pre[l], pre[r], x)) << endl;
		}
	}
    return 0;
}

本题还有一个更简单的方法，直接在每个节点上存有哪些编号经过，要判断有没有 $[L,R]$ ，二分就行。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;

constexpr ull B = 30;

struct Trie {
    struct Unit {
        int nxt[2]{};
	    vector<int> vec;
    };
    vector<Unit> U;

    Trie() { new_node(); }

    int new_node() {
        int p = U.size();
        U.push_back({});
        return p;
    }

    void insert(uint x, int id, int p = 0) {
        for (int bit = B; bit >= 0; bit--) {
            bool c = x >> bit & 1;
            if (!U[p].nxt[c]) U[p].nxt[c] = new_node();
            p = U[p].nxt[c];
            U[p].vec.push_back(id);
        }
    }

    uint query(uint x, int l, int r, int p = 0) {
        uint res = 0;
        for (int bit = B; bit >= 0; bit--) {
            bool c = x >> bit & 1 ^ 1;
            if (U[p].nxt[c]) {
                auto& vec = U[U[p].nxt[c]].vec;
                auto it = lower_bound(vec.begin(), vec.end(), l);
                if (it != vec.end() && *it >= l && *it <= r) {
                    res |= 1u << bit;
                    p = U[p].nxt[c];
                } else {
                    p = U[p].nxt[!c];
                }
            } else {
                p = U[p].nxt[!c];
            }
        }
        return res;
    }
};

int main() {
	int J;
	cin >> J;
	while (J--) {
		int n, q;
		cin >> n >> q;
        Trie trie;
        for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			trie.insert(x, i);
		}
		while (q--) {
			int l, r, x;
			cin >> l >> r >> x;
            l--;
            r--;
            cout << trie.query(x, l, r) << endl;
		}
	}
    return 0;
}