A 小月的模块
知识点：条件判断、三目运算
选择信号 $s$ 决定取哪一路数据：当 $s=0$ 时输出 $a$，否则输出 $b$，直接按条件表达式实现即可。
时间复杂度 $\mathcal{O}(1)$。
void solve() {
int a, b, s;
cin >> a >> b >> s;
cout << (s ? b : a) << endl;
}B 小月的信号
知识点：位运算、二进制
当 $x=0$ 时不存在置位，答案直接为 $0,-1,-1$。当 $x>0$ 时，置位总数用置位计数函数得到；最低置位下标等于二进制表示末尾连续 $0$ 的数量，最高置位下标则为 $\lfloor\log_2 x\rfloor$，分别调用对应的位运算函数即可。
时间复杂度 $\mathcal{O}(1)$。
void solve() {
int x;
cin >> x;
if (x == 0) return cout << "0 -1 -1" << endl, void();
cout << __builtin_popcountll(x) << " " << __builtin_ffsll(x) - 1 << " " << __lg(x) << endl;
}C 小月的灯带
知识点：前缀和、二分查找、异或
因为 $a_i>0$，前缀和严格递增。令 $\begin{cases}s_0=0,\\s_i=\sum_{j=1}^{i}a_j,\end{cases}$
则查询位置 $p$ 所在的段编号是满足 $s_{r-1}<p\le s_r$ 的最小 $r$，在前缀和数组中二分查找第一个不小于 $p$ 的位置即可。段内编号直接由 $d=p-s_{r-1}$ 得到。
颜色只由段编号的奇偶性决定： $c=\begin{cases}b,&r\text{ 为奇数},\\ 1-b,&r\text{ 为偶数}.\end{cases}$
若输入颜色记为 $b_0$，代码令 $b=b_0\oplus1$，再输出 $b\oplus(r\bmod2)$，就能用一条表达式覆盖上面的两种情况。
时间复杂度 $\mathcal{O}(m+q\log m)$。
void solve() {
int m, q, b;
cin >> m >> q >> b;
b ^= 1;
vector<int> a(1);
for (int i = 0, x; i < m; ++i) cin >> x, a.push_back(a.back() + x);
while (q--) {
int p;
cin >> p;
int idx = lower_bound(a.begin(), a.end(), p) - a.begin();
cout << (b ^ (idx & 1)) << " " << idx << " " << p - a[idx - 1] << endl;
}
}D 小月的校验码
知识点：位运算、哈希、汉明距离
把每个长度为 $b$ 的字符串按二进制数保存为 $v$。若只改变第 $i$ 个二进制位，得到的候选码唯一为 $v\oplus 2^i.$
枚举每个 $v$ 和每个 $i$，在哈希集合中检查候选值是否存在即可。$i=0$ 对应字符串最右端的字符，而题目要求按从左到右输出，所以统计完成后将各位置计数反转。
这样统计的是有序的端点：一对单点差分码会从两个方向各被发现一次，因此总数和每个位置的计数都要除以 $2$。
时间复杂度 $\mathcal{O}(nb)$。
void solve() {
int n, b;
cin >> n >> b;
vector<int> a(n);
unordered_set<int> st;
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
for (auto v : s) a[i] = (a[i] << 1) | (v - '0');
st.insert(a[i]);
}
vector<int> pos(b);
for (auto v : a) {
for (int i = 0; i < b; ++i) {
int mask = v ^ (1LL << i);
pos[i] += st.count(mask);
}
}
reverse(pos.begin(), pos.end());
cout << accumulate(pos.begin(), pos.end(), 0LL) / 2 << endl;
for (auto v : pos) cout << v / 2 << " ";
cout << endl;
}E 小月的前缀集合
知识点：数组编码、Trie、动态维护、前缀计数
法 $1$ :
由于字符串长度至多为 $20$，可以把前缀直接编码成整数。令初始 $x=1$ 表示空前缀，读入字符 $c$ 后执行 $x\leftarrow 2x+(c-\texttt{0}).$
此时长度为 $l$ 的前缀对应二进制串 $\texttt{1}$ 加上该前缀，映射唯一且最大下标不超过 $2^{21}-1$，因此可以直接用静态数组 $cnt$ 记录经过每个前缀的活动码数量。插入时，$cnt[x]$ 从 $0$ 变为 $1$ 的位置使答案加一；删除时，计数减到 $0$ 的位置使答案减一。
时间复杂度 $\mathcal{O}(qL)$。
int cnt[1 << 21];
void solve() {
int q;
cin >> q;
int ans = 0;
char op;
string s;
while (q--) {
cin >> op >> s;
int x = 1;
if (op == '+') {
for (char c : s) {
x = (x << 1) | (c - '0');
if (cnt[x]++ == 0) ++ans;
}
} else {
for (char c : s) {
x = (x << 1) | (c - '0');
if (--cnt[x] == 0) --ans;
}
}
cout << ans << endl;
}
}法 $2$ :
把所有活动码放入一棵二叉 $\texttt{Trie}$。对节点 $u$ 维护 $ps_u$，表示当前活动码中经过该节点的字符串数量；因此一个非根节点恰好在 $ps_u>0$ 时对应一个被占用的前缀。
插入时沿路径增加计数，只有原来为 $0$ 的节点会让答案增加；删除时沿同一路径减少计数，只有减少到 $0$ 的节点会让答案减少。节点本身无需物理删除，之后再次插入可以直接复用原路径。
时间复杂度 $\mathcal{O}(qL)$。
struct Trie {
struct Node {
array<int, 2> to{};
int ps = 0, ed = 0;
};
vector<Node> tr{Node()};
int insert(const string &s) {
int u = 0, res = 0;
for (char c : s) {
int v = c - '0';
if (!tr[u].to[v]) {
tr[u].to[v] = tr.size();
tr.emplace_back();
}
u = tr[u].to[v];
if (tr[u].ps == 0) ++res;
++tr[u].ps;
}
++tr[u].ed;
return res;
}
int erase(const string &s) {
int u = 0, res = 0;
vector<int> path;
path.reserve(s.size());
for (char c : s) {
u = tr[u].to[c - '0'];
path.push_back(u);
}
--tr[u].ed;
for (int v : path)
if (--tr[v].ps == 0) ++res;
return res;
}
};
void solve() {
int q;
cin >> q;
Trie tr;
int ans = 0;
while (q--) {
char op;
string s;
cin >> op >> s;
if (op == '+')
ans += tr.insert(s);
else
ans -= tr.erase(s);
cout << ans << endl;
}
}F 小月的路径码
知识点：树上差分、欧拉序、树状数组、模运算
令节点 $u$ 的权值为 $w_u=2^{\operatorname{dep}(u)}\bmod M$，其中 $M=10^9+7$。节点 $u$ 恰好会出现在它的所有后代的根路径上，所以翻转 $u$ 等价于给整棵 $u$ 子树的路径码同时加上或减去 $w_u$。
欧拉序把每个子树映射成连续区间 $[\operatorname{in}(u),\operatorname{out}(u)]$，维护的序列满足 $f[\operatorname{in}(v)]=C(v)$。于是，翻转操作变成区间加，查询节点 $v$ 只需读取位置 $\operatorname{in}(v)$ 的值。用树状数组维护差分数组即可做到区间加、单点查询；代码使用非递归 $\texttt{DFS}$ 求欧拉序，避免深树时的递归栈开销。
预处理所有深度的 $2$ 的幂后，每次修改或查询均为 $\mathcal{O}(\log n)$。
时间复杂度 $\mathcal{O}((n+q)\log n)$。
using Z = MInt<mod>;
template <class T> struct BIT {...}; // 树状数组
void solve() {
int n, q;
string s;
cin >> n >> q >> s;
vector<vector<int>> g(n + 1);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> fa(n + 1), dep(n + 1);
vector<int> in(n + 1), sz(n + 1), ord;
vector<int> st = {1};
while (!st.empty()) {
int u = st.back();
st.pop_back();
in[u] = ord.size() + 1;
ord.push_back(u);
sz[u] = 1;
for (auto v : g[u]) {
if (v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
st.push_back(v);
}
}
for (int i = n - 1; i > 0; --i) {
int u = ord[i];
sz[fa[u]] += sz[u];
}
vector<int> out(n + 1);
for (int u = 1; u <= n; ++u) {
out[u] = in[u] + sz[u] - 1;
}
BIT<Z> bit(n);
for (int u = 1; u <= n; ++u) {
if (s[u - 1] == '1') {
bit.update(in[u], out[u], Z(2).pow(dep[u]));
}
}
while (q--) {
char op;
int u;
cin >> op >> u;
if (op == 'F') {
if (s[u - 1] == '1') {
bit.update(in[u], out[u], -Z(2).pow(dep[u]));
s[u - 1] = '0';
} else {
bit.update(in[u], out[u], Z(2).pow(dep[u]));
s[u - 1] = '1';
}
} else {
cout << bit.askSum(in[u], in[u]) << endl;
}
}
}约定
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int, 2>
#define endl "\n"
void solve() {
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}使用到的算法模板见 $\texttt{github}$ 仓库 林月的XCPC模板库