A - 前导1的数量

这个问题要求计算具有特定数量前导1的数字个数。我们首先计算至少有i个前导1的数字数量，然后通过容斥原理减去所有f_j（j > i）。

long long n, g[20], bin[29];

int main() {
    scanf("%lld", &n);
    long long bit = 1, m = 0;
    while(bit * 10ll <= n) bin[++m] = (n / bit) % 10, bit *= 10ll;
    bin[++m] = (n / bit) % 10;
    int pos = m, fx = 0;
    while(bin[pos] == 1) pos -- ;
    fx = bin[pos];
    long long res = 0;
    for(int i = m; i >= 1; --i) {
        for(int j = 0; j < m - i; ++j) g[i] += pow(10ll, j);
        if(pos >= m - i + 1) {
            if(fx == 1) {for(int j = 1; j < m - i; ++j) g[i] += bin[j] * pow(10ll, j - 1);g[i] ++ ;}
            else if(fx) g[i] += pow(10ll, m - i);
        } else {
            long long mul = 1ll;
            for(int j = 1; j < m - i; ++j) mul += 1ll * (bin[j]) * pow(10ll, j - 1);
            g[i] += mul;
        }
        for(int j = i + 1; j <= m; ++j) g[i] -= g[j];
        res += 1ll * i * g[i];
    }
    printf("%lld\n", res);
    return 0;
}

B - 三进制字符串

构造方案是对于以2开头的数字，从小到大取出前N个三进制数；以1或0开头的数可以随意选取，但要保证没有重复串且每种数字出现次数为N。

int n, L, pw[20], stk[20];
inline void split(int k) {
    int top = 0; memset(stk, 0, sizeof stk);
    while(k) stk[++top] = k % 3, k /= 3;
}

int main() {
    scanf("%d%d", &n, &L);
    pw[0] = 1;
    for(int i = 1; i <= L; ++i) pw[i] = pw[i - 1] * 3;
    for(int i = 0; i < n; ++i) {
        split(i); putchar('2');
        for(int j = L - 1; j >= 1; --j) putchar(stk[j] + '0'); puts("");
    }
    for(int i = 0; i < n; ++i) {
        split(i); putchar('1');
        for(int j = L - 1; j >= 1; --j) putchar((stk[j] + 1) % 3 + '0'); puts("");
    }
    for(int i = 0; i < n; ++i) {
        split(i); putchar('0');
        for(int j = L - 1; j >= 1; --j) putchar((stk[j] + 2) % 3 + '0'); puts("");
    }
    return 0;
}

C - 二进制字符串

利用字典序排序的概念，可以通过DFS树来解决此问题。以下是优化后的实现：

int m, n, ept; char s[N], t[N];
inline void opt() {
    int l = n;
    do t[l--] ^= 1, ept ++ ; while(t[l + 1] & 1); ept -= 2;
}

void dfs(int d) {
    if(!ept) return Wtn('\n');
    if(t[d] & 1) Wtn('1'), ept -- , t[d] = 0, dfs(d + 1);
    else Wtn('0'), opt(), dfs(d + 1);
}

inline void solve() {
    Rdn(n), Rdn(s + 1);
    m = strlen(s + 1);
    for(int i = 1; i <= m; ++i) t[i + n - m] = s[i], ept += s[i] ^ '0';
    Wtn('1'), opt(), dfs(1);
}

D - 异或最小和

该问题需要计算两个数组A和B的所有组合的异或值之和，并找到最小值。采用分治法从高位到低位贪心处理。

long long A[N], B[N], res, bit[2]; vector<int> r[2][2];
void dfs(vector<int> v, int d) {
    int n = v.size();
    if(!n) return ;
    if(d == -1) {
        for(int j = 0; j < 18; ++j) {
            bit[0] = bit[1] = 0;
            for(int i : v) {
                res += bit[A[i] >> j & 1 ^ 1] << j;
                bit[A[i] >> j & 1] ++ ;
            }
        }
        return ;
    }
    vector<int> S[2];
    for(int o = 0; o < 2; ++o) for(int oo = 0; oo < 2; ++oo) r[o][oo].clear();
    for(int i : v) S[B[i] >> d & 1].push_back(i);
    for(int i : v) r[B[i] >> d & 1][A[i] >> d & 1].push_back(i);
    for(int o = 0; o < 2; ++o) for(int oo = 0; oo < 2; ++oo) {
        if((o ^ oo) <= (o ^ oo ^ 1)) {
            for(int j = 0; j < 18; ++j) {
                bit[0] = bit[1] = 0;
                for(int i : r[0][oo]) bit[(A[i] >> j) & 1] ++ ;
                for(int i : r[1][o]) res += bit[((A[i] >> j) & 1) ^ 1] << j;
            } 
        } else {
            for(int j = 0; j < 18; ++j) {
                bit[0] = bit[1] = 0;
                for(int i : r[0][oo]) bit[((B[i] ^ A[i]) >> j) & 1] ++ ;
                for(int i : r[1][o]) res += bit[(((B[i] ^ A[i]) >> j) & 1) ^ 1] << j;
            } 
        }
    }
    dfs(S[0], d - 1), dfs(S[1], d - 1);
}

int n; vector<int> ini;
inline void solve() {
    Rdn(n), ini.reserve(n);
    for(int i = 1; i <= n; ++i) Rdn(A[i]);
    for(int i = 1; i <= n; ++i) Rdn(B[i]), B[i] ^= A[i], ini.push_back(i);
    r[0][0].reserve(n / 2);
    r[0][1].reserve(n / 2);
    r[1][1].reserve(n / 2);
    r[1][0].reserve(n / 2);
    dfs(ini, 17);
    Wtn(res, '\n');
}