阿里云笔试 - 研发 0316 题解

T1

求 $\And a_i\ge\bigoplus a_i$ 的方案数， $0\le a_i<2^k,0\le n,k\le 10^5$

考虑从高到低按位填数
考虑 $\And a=\bigoplus a$
- 对于 $\And a=\bigoplus a=1$ ，当且仅当 $n$ 是奇数且这一位全填 $1$ ，方案数即为 $[n\text{ is odd}]$ ；
- 对于 $\And a=\bigoplus a=0$ ，当且仅当这一位不全为 $1$ 且 $1$ 的个数为偶数，方案数 $\sum {n\choose 2i}-[n\text{ is even}]=2^{n-1}-[n\text{ is even}]$ ；
- 所以 $\And a=\bigoplus a$ 的方案数为 $q\overset{\rm def}=2^{n-1}+[n\text{ is odd}]-[n\text{ is even}]=2^{n-1}+(-1)^{n+1}$ 。
考虑 $\And a>\bigoplus a$ ，当且仅当二进制高位相等，且第 $i$ 位 $\And a=1,\bigoplus a=0$ ，即 $n$ 是偶数且全填 $1$ ，低位可以任意填，方案数为 $(2^i)^n=2^{ni}$ ，故总方案数为 $\sum\limits_{i=0}^{k-1} q^{k-i-1}\times[n\text{ is even}]\times2^{ni}$
综上所述
- $n$ 为奇数时答案为 $q^k$
- $n$ 为偶数时答案为
$\begin{aligned} &q^k+\sum_{i=0}^{k-1} q^{k-i-1}\times2^{ni}\\ =&q^k+2^{n(k-1)}\sum_{i=0}^{k-1}q^i \times2^{-ni}\\ =&q^k+2^{n(k-1)}\frac{q^k2^{-nk}-1}{q2^{-n}-1}\\ =&q^k+2^{n(k-1)}\frac{q^k2^{n(1-k)}-2^n}{q-2^n}\\ =&q^k+\frac{q^k-2^{nk}}{q-2^n}\\ \end{aligned}$
时间复杂度 $O(\log nk)$ ，不过题目放 $O(k)$ 的做法过。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
using ll = int64_t;
int n, k;
int fpow(ll a, ll b, ll x = 1) {
    b %= P - 1;
    for (; b; b >>= 1, a = a * a % P)
        if (b & 1)
            x = x * a % P;
    return x;
}
int main() {
    scanf("%d%d", &n, &k);
    int q = fpow(2, n - 1) + (n & 1 ? 1 : -1), qk = fpow(q, k), ans = qk;
    if (n % 2 == 0) {
        int pn = fpow(2, n);
        ans = (ans + fpow(q - pn + P, P - 2, qk - fpow(pn, k) + P)) % P;
    }
    printf("%d\n", ans);
}

T2

最大化 $\sum b_i(a_i+j),\ 1\le a_i\le 10^9,b_i=\pm1$ ，将序列 $[a_i]$ 分为不超过 $k$ 个非空段， $j$ 表示 $a_i$ 属于第几段（从 $1$ 开始）， $1\le k\le n\le 10^5$

化简式子
$\begin{aligned} \sum b_ij=&\sum j\times({s_{i_{j}}-s_{i_{j-1}}})\\ =&s_{i_1}+2(s_{i_2}-s_{i_1})+\cdots+k(s_{i_k}-s_{i_{k-1}})\\ =&-s_{i_1}-s_{i_2}-\cdots-s_{i_{k-1}}+ks_{i_{k}} \end{aligned}$
所以答案就是 $\max\limits_k\left(ks_n-{\rm top}_{k\min}{s_i}\right)$ ，求出前缀和排序或者用堆维护即可。 $O(n+k\log k)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
using ll = int64_t;
int n, k;
int main() {
    scanf("%d%d", &n, &k);
    vector<int> a(n), b(n), s(n);
    string str(n, 0);
    for (auto &x : a) scanf("%d", &x);
    scanf("%s", str.data());
    ll ans1 = 0, ans2 = 0, sn = 0, sum_s = 0;
    priority_queue<int> q;
    for (int i = 0; i < n; ++i) {
        int val = str[i] == '1' ? 1 : -1;
        ans1 += a[i] * val;
        s[i] = (i ? s[i - 1] : 0) + val;
    }
    ans2 = sn = s[n - 1];
    nth_element(s.begin(), s.begin() + k, s.end());
    sort(s.begin(), s.begin() + k);
    for (int i = 0; i < k; ++i) {
        sum_s += s[i];
        ans2 = max(ans2, i * sn - sum_s);
    }
    printf("%lld\n", ans1 + ans2);
    return 0;
}

T3

定义 $f(2^k)=k$ ，其余情况为 $0$ 。求 $\sum\limits_{l\le r}f\left(\sum\limits_{i=l}^ra_i\right),0\le a_i<2^{30},1\le n\le 3\times10^5$

求前缀和 $s$ ，统计 $s_i$ 的出现次数，求 $\sum_i k\times cnt[s_i-2^k]$ 即可。注意 $k$ 要枚举到 $48$ ， $nA<2^{49}$ 。 $O(n\log nA)$

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, M = 50;
using ll = int64_t;
ll pw[M];
void solve() {
    int n;
    scanf("%d", &n);
    unordered_map<ll, int> cnt = {{0, 1}};
    ll sum = 0, ans = 0;
    for (int i = 0, x; i < n; ++i) {
        scanf("%d", &x), ++cnt[sum += x];
        for (int j = 1; j < M; ++j)
            if (cnt.count(sum - pw[j]))
                ans += (ll)cnt[sum - pw[j]] * j;
    }
    printf("%lld\n", ans);
}
int main() {
    pw[0] = 1;
    for (ll i = 1; i < M; ++i)
        pw[i] = pw[i - 1] << 1;
    int t;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}

#阿里云笔试##阿里云##笔试##技术岗笔试题求解##牛客创作赏金赛#