A 小月的亮灯
知识点：模拟、贡献统计
下标为 $i$ 的灯亮起时贡献 $i$ 分，熄灭时贡献 $0$ 分，因此直接累加每盏灯的贡献即可。注意下标从 $0$ 开始，第一盏灯无论是否亮起都不贡献分数。
时间复杂度 $\mathcal{O}(1)$。
void solve() {
vector<int> a(3);
for (auto &v : a) cin >> v;
int ans = 0;
for (int i = 0; i < 3; ++i) ans += i * (a[i] == 1);
cout << ans << endl;
}void solve() {
int a, b, c;
cin >> a >> b >> c;
cout << b + c + c << endl;
}B 小月的纪录点
知识点：前缀最大值、线性扫描
记录点恰好是严格刷新前缀最大值的位置，因此最后一个记录点的值就是当前前缀的最大值。从左到右扫描，将第一个元素加入 $p$，之后仅当 $a_i$ 严格大于最后一个记录点的值时，才将其值和下标加入 $p$。
于是 $p$ 的大小就是记录点数量，再枚举其中相邻元素的下标差并取最大值。答案初始为 $0$，也能处理只有一个记录点的情况。
时间复杂度 $\mathcal{O}(n)$。
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto &v : a) cin >> v;
vector<pii> p = {{a[0], 0}};
for (int i = 1; i < n; ++i) {
if (a[i] > p.back()[0]) p.push_back({a[i], i});
}
int ans = 0;
for (int i = 1; i < p.size(); ++i) ans = max(ans, p[i][1] - p[i - 1][1]);
cout << p.size() << " " << ans << endl;
}C 小月的排序
知识点：位运算、自定义排序、字典序
将每个数 $x$ 的排序关键字写成
$$\bigl(\operatorname{popcount}(x),\operatorname{low}(x),x\bigr),$$
其中 $\operatorname{popcount}(x)$ 表示二进制中 $1$ 的数量，$\operatorname{low}(x)$ 表示最低位 $1$ 的位置，并规定 $\operatorname{low}(0)=31$。按这个三元组的字典序升序排序，取下标为 $k-1$ 的元素即可。
对非零数，$\texttt{__builtin_ffsll}$ 返回的位置从 $1$ 开始，需要减去 $1$；对 $0$ 单独返回 $31$。
时间复杂度 $\mathcal{O}(n\log n)$。
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &v : a) cin >> v;
auto ppc = [&](int x) { return __builtin_popcountll(x); };
auto ffs = [&](int x) { return x ? __builtin_ffsll(x) - 1 : 31; };
sort(a.begin(), a.end(), [&](auto x, auto y) {
if (ppc(x) != ppc(y)) return ppc(x) < ppc(y);
if (ffs(x) != ffs(y)) return ffs(x) < ffs(y);
return x < y;
});
cout << a[k - 1] << endl;
}D 小月的岛屿
知识点：网格图、连通块、DFS
分别按四连通和八连通的规则求连通块即可。每遇到一个尚未访问的 $1$，就从这里搜索整个连通块，将连通块数量增加 $1$，并用本次访问的格子数更新最大面积。
先只允许上下左右四个方向，得到 $c_4,s_4$；清空访问标记后，再允许八个方向，得到 $c_8,s_8$。输出 $c_4-c_8,s_4,s_8$，初值均设为 $0$ 即可处理全为 $0$ 的网格。代码用显式栈实现 $\texttt{DFS}$，避免连通块过大时递归过深。
时间复杂度 $\mathcal{O}(nm)$。
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
void solve() {
int n, m;
cin >> n >> m;
vector<string> s(n);
for (auto &v : s) cin >> v;
auto check = [&](int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
};
vector<vector<bool>> vis(n, vector<bool>(m));
auto dfs = [&](int x, int y, int k) {
vector<pii> st = {{x, y}};
vis[x][y] = 1;
int res = 0;
while (!st.empty()) {
auto [x, y] = st.back();
st.pop_back();
++res;
for (int i = 0; i < k; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny) && !vis[nx][ny] && s[nx][ny] == '1') {
vis[nx][ny] = 1;
st.push_back({nx, ny});
}
}
}
return res;
};
int c4 = 0, c8 = 0, s4 = 0, s8 = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!vis[i][j] && s[i][j] == '1') {
++c4;
s4 = max(s4, dfs(i, j, 4));
}
}
}
vis.assign(n, vector<bool>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!vis[i][j] && s[i][j] == '1') {
++c8;
s8 = max(s8, dfs(i, j, 8));
}
}
}
cout << c4 - c8 << " " << s4 << " " << s8 << endl;
}E 小月的路线
知识点：最短路、Dijkstra、字典序
将路径权值看成二元组 $(D,R)$，按字典序比较，就恰好对应先最小化总距离，再最小化总风险。设 $dis_u$ 为从结点 $1$ 到 $u$ 的最优二元组，经过边 $(u,v,d,r)$ 时，尝试用
$$dis_u+(d,r)$$
更新 $dis_v$，其中加法按两个分量分别相加。
每条边的距离和风险都非负，所以延伸路径不会使权值变小；同时，字典序在加上同一个二元组后保持不变，因此可以直接运行 $\texttt{Dijkstra}$。优先队列和松弛判断都使用二元组的字典序，即可同时满足两个优化目标。
题目是有向图，每条输入边只加入 $u\to v$。初始化 $dis_1=(0,0)$，若 $dis_n$ 仍为无穷大则输出 $-1\ -1$；当 $n=1$ 时自然得到 $0\ 0$。记边数为 $m$，堆中保留过期状态并在弹出时跳过。
时间复杂度 $\mathcal{O}(n+m\log(m+1))$。
pii operator+(const pii &a, const pii &b) {
return {a[0] + b[0], a[1] + b[1]};
}
void solve() {
int n, m;
cin >> n >> m;
Dijkstra<pii> g(n);
for (int i = 0; i < m; ++i) {
int u, v, d, r;
cin >> u >> v >> d >> r;
g.add(u, v, {d, r});
}
auto dis = g.solve(1);
if (dis[n] == pii{inf, inf})
cout << "-1 -1" << endl;
else
cout << dis[n][0] << " " << dis[n][1] << endl;
}F 小月的筹码
知识点：折半搜索、异或、哈希计数
将筹码分成大小尽量相等的左右两半，分别枚举所有子集，只记录选择个数 $cnt$ 和异或和 $val$。若左半部分选择了 $cnt$ 个筹码，异或和为 $val$，则右半部分必须满足
$$cnt’=k-cnt,\qquad val’=x\operatorname{xor}val.$$
用哈希表统计右半部分每种 $(cnt’,val’)$ 出现的次数，再枚举左半部分的状态，累加对应状态的出现次数，并对 $10^9+7$ 取模。
每个完整选择方案都能唯一拆成左右两半的子集，因此不会遗漏或重复计数。筹码按编号区分，所以即使多个子集的状态相同，也必须保留它们的出现次数。枚举时包含空集，自然覆盖 $k=0$ 的情况。
期望时间复杂度 $\mathcal{O}(2^{\lceil n/2\rceil})$。
constexpr int mod = 1e9 + 7;
void solve() {
int n, k, x;
cin >> n >> k >> x;
vector<int> a(n);
for (auto &v : a) cin >> v;
vector<pii> L, R;
auto dfs = [&](auto &&self, int l, int r, int cnt, int sum, vector<pii> &v) -> void {
if (l > r) return v.push_back({cnt, sum}), void();
self(self, l + 1, r, cnt, sum, v);
self(self, l + 1, r, cnt + 1, sum ^ a[l], v);
};
int mid = n >> 1;
dfs(dfs, 0, mid - 1, 0, 0, L);
dfs(dfs, mid, n - 1, 0, 0, R);
unordered_map<pii, int, Hash> mp;
for (auto [cnt, val] : R) mp[{cnt, val}]++;
int ans = 0;
for (auto [cnt, val] : L) {
int nd = k - cnt, y = x ^ val;
auto it = mp.find({nd, y});
if (it != mp.end()) (ans += it->second) %= mod;
}
cout << ans << 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模板库