A 小月的开关

知识点：取模、循环状态

状态按照 $3$ 个值循环，按一次按钮就是在当前状态上加 $1$ 后对 $3$ 取模，因此直接输出

$$(x+1)\bmod 3.$$

时间复杂度 $\mathcal{O}(1)$。

void solve() {
    int x;
    cin >> x;
    cout << (x + 1) % 3 << endl;
}

B 小月的彩灯

知识点：位运算、循环移位、二进制

环的长度是 $4$，所以移动次数只需要保留 $k\bmod 4$。为了书写方便，左移 $k$ 次其实等价于右移 $4 – k$ 次（模意义下取正）：每次取出最低位，整体右移一位，再把取出的位放回第 $3$ 位。

统计 $y$ 的二进制表示中 $1$ 的个数即可。

时间复杂度 $\mathcal{O}(1)$。

void solve() {
    int x, k;
    cin >> x >> k;
    k = ((4 - k) % 4 + 4) % 4;
    while (k--) {
        bool f = x & 1;
        x >>= 1;
        if (f) x |= 1 << 3;
    }
    cout << x << " " << __builtin_popcountll(x) << endl;
}

C 小月的平方刻度

知识点：整数平方根、公式计算

令

$$r=\left\lfloor\sqrt{x}\right\rfloor.$$

那么 $r^2$ 是不超过 $x$ 的最大完全平方数，两个距离分别为

$$d_{\mathrm{low}}=x-r^2,\qquad d_{\mathrm{high}}=(r+1)^2-x.$$

用长双精度函数 $\texttt{sqrtl}$ 求出 $r$，再直接代入上式即可。展开了是因为我觉得打括号很别手。

时间复杂度 $\mathcal{O}(1)$。

void solve() {
    int x;
    cin >> x;
    int r = sqrtl(x);
    cout << r << " " << x - r * r << " " << r * r + 2 * r + 1 - x << endl;
}

D 小月的计数器

知识点：二进制进位、数位统计

不难发现，如果 $i$ 的末尾有 $k$ 个 $0$ ，那么从 $i-1$ 的末尾就有 $k$ 个 $1$ 。加 $1$ 时，末尾的 $k$ 个 $1$ 变成 $0$ ，它前面的 $0$ 变成 $1$ ，所以总共会有
$$1+\nu_2(i)$$
次翻页，其中 $\nu_2(i)$ 表示二进制末尾连续 $0$ 的个数。

所以总答案为
$$S(n) = \sum\limits_{i=1}^{n}(1+\nu_2(i)) = n + \sum_{i=1}^{n}\nu_2(i)$$
一个数的 $\nu_2(i)$ 之和，同时也可以表示为 $n$ 能被多少个 $2^k$ 整除，所以可以交换求和顺序
$$\sum_{i=1}^{n}\nu_2(i) = \sum_{k\geqq1}\lfloor\frac{n}{2^k}\rfloor$$
我们将 $n$ 写成二进制，可以表示为 $n = \sum\limits_{j\geqq 0}b_j2^j,,b_j\in{0,1}$ ，所以有
$$\begin{align}\sum_{k\geqq1}\lfloor\frac{n}{2^k}\rfloor &= \sum\limits_{j\geqq 0}b_j\sum_{k=1}^j2^{j-k}\\&=\sum_{j\geqq 0}b_j(2^j-1)\\&=n-\sum_{j\geqq 0}b_j\\&=n-\operatorname{popcount}(n)\end{align}$$
因此答案为
$$2n – \operatorname{popcount}(n)$$

时间复杂度 $\mathcal{O}(1)$。

void solve() {
    int n;
    cin >> n;
    cout << 2 * n - __builtin_popcountll(n) << endl;
}

E 小月的相交弦

知识点：区间 DP、端点配对、非相交结构

记端点总数为 $m=2n$，令 $\texttt{dp}[l][r]$ 表示只考虑端点区间 $[l,r]$ 内、且两端都在该区间中的弦时，能够取得的最大权值。处理右端点 $r$，设它配对的另一个端点为 $p$。

若不选弦 $(p,r)$，答案就是 $\texttt{dp}[l][r-1]$。若选择它且 $l\le p<r$，任何一个被选弦都不能用一个端点落在 $[l,p-1]$、另一个端点落在 $[p+1,r-1]$，否则会与 $(p,r)$ 相交；因此两侧可以独立求解，转移为

$$\begin{aligned}\texttt{dp}[l][r]=\max\bigl(&\textrm{dp}[l][r-1], \textrm{dp}[l][p-1]+\textrm{dp}[p+1][r-1]+w_r\bigr).\\\end{aligned}$$

嵌套关系不会产生冲突，所以区间拆分已经覆盖所有合法选择；空区间的值取 $0$，也自然处理负权弦。

时间复杂度 $\mathcal{O}(n^2)$。

void solve() {
    int n;
    cin >> n;
    int m = 2 * n;
    vector<int> to(m + 1), w(m + 1);
    for (int i = 0; i < n; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        to[l] = r;
        to[r] = l;
        w[l] = w[r] = x;
    }

    vector<vector<int>> dp(m + 1, vector<int>(m + 1));
    auto get = [&](int l, int r) -> int {
        if (l > r) return 0;
        return dp[l][r - l];
    };

    for (int len = 1; len <= m; ++len) {
        for (int l = 1; l + len - 1 <= m; ++l) {
            int r = l + len - 1, p = to[r];
            int cur = get(l, r - 1);
            if (l <= p && p < r)
                cur = max(cur, get(l, p - 1) + get(p + 1, r - 1) + w[r]);
            dp[l][r - l] = cur;
        }
    }
    cout << get(1, m) << endl;
}

F 小月的能量带

知识点：排序、树状数组、坐标压缩、区间计数

按 $(l,r,\texttt{id})$ 排序后，设两条区间为 $A=[l_1,r_1)$、$B=[l_2,r_2)$，且 $l_1\le l_2$。并集连续的条件是 $l_2\le r_1$。

若 $r_2\le r_1$，并集长度为 $r_1-l_1$，所以必须有 $r_1-l_1=t$；这正是一个长度为 $t$ 的区间包含另一个区间的情况。逆序扫描排序后的区间，对每个长度为 $t$ 的区间统计后方且右端点不超过 $r_1$ 的区间。把所有右端点离散化后，用树状数组维护出现次数即可。排序保证后方区间的左端点不会小于 $l_1$；同左端点但更短的区间排在前面，留到下面的情况处理。

若 $r_2>r_1$，则并集长度为 $r_2-l_1$，必须满足

$$r_2=l_1+t,\qquad l_2\le r_1.$$

此时当前区间长度必小于 $t$。按右端点把区间分组，并在每组中按 $(l,\texttt{id})$ 排序；对当前区间 $i$，只需二分统计右端点为 $l_i+t$、满足 $(l_j,\texttt{id}_j)>(l_i,\texttt{id}_i)$ 且 $l_j\le r_i$ 的候选。严格的排序键保证无序区间对只被计数一次，也覆盖了两个区间左端点相同的边界。

上述两类已经穷尽了并集长度为 $t$ 的连续区间对。

时间复杂度 $\mathcal{O}(n\log n)$。

constexpr int inf = 2e18 + 9;

template <class T> struct BIT {...}; // 树状数组

void solve() {
    int n, t;
    cin >> n >> t;
    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i][0] >> a[i][1];
        a[i][2] = i;
    }
    sort(a.begin(), a.end());

    vector<int> v;
    for (auto x : a) v.push_back(x[1]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    BIT<int> tr(v.size());

    int ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        if (a[i][1] - a[i][0] == t) {
            int p = upper_bound(v.begin(), v.end(), a[i][1]) - v.begin();
            ans += tr.ask(p);
        }
        int p = lower_bound(v.begin(), v.end(), a[i][1]) - v.begin() + 1;
        tr.modify(p, 1);
    }

    map<int, vector<pii>> mp;
    for (int i = 0; i < n; ++i) mp[a[i][1]].push_back({a[i][0], i});
    for (int i = 0; i < n; ++i) {
        int l = a[i][0], r = a[i][1];
        if (r - l >= t) continue;
        auto it = mp.find(l + t);
        if (it == mp.end()) continue;
        auto &b = it->second;
        int x = upper_bound(b.begin(), b.end(), pii{l, i}) - b.begin();
        int y = upper_bound(b.begin(), b.end(), pii{r, inf}) - b.begin();
        ans += y - x;
    }
    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模板库