链接

VP赛时 ABCD，补题EF

分数：800 - 1200 - 1400 - 1800 - 2000 - 2900

A、B、C没什么好说的。

D题赛时卡了，没想到 这个条件怎么用，技巧 +1

E题回顾了一下一个较为经典的概率dp。

F题正好复习一下前段时间刚学会的 min_25 筛（确实好用，也顺便整理了一下 min_25 的板子。

A. Find Minimum Operations

题意

给定两个整数 ，每次操作可以从 上减去 的非负整数幂，求将 变成 的最小操作次数。

题解

如果 ，显然需要 次。

否则预处理出所有小于 的 的幂，每次在二分找最大的不超过当前 的幂减去。如果最后 ，直接将答案加上剩下的 即可。

时间复杂度：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a;
    ll t = k;
    a.push_back(1);
    if (k != 1) {
        while (t <= n) {
            a.push_back(t);
            t *= k;
        }
    }
    int cnt = 0;
    while (n) {
        int l = 0, r = a.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (a[mid] <= n)
                l = mid;
            else
                r = mid - 1;
        }
        n -= a[l];
        cnt++;
        if (a[l] == 1) {
            cnt += n;
            break;
        }
    }
    cout << cnt << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

B. Brightness Begins

题意

有 个灯泡，编号为 ，最开始所有灯都是亮的，然后进行如下操作：

  • 对于 ，反转所有 灯泡。

执行完所有操作后，将会有一些灯泡是亮的。

找出最小的 使得执行完操作后恰好有 ​ 个灯泡是亮的。

题解

每个灯泡只会被自己的因数操作翻转，如果一个数的因数是偶数，则操作完后仍然是亮的。因数为奇数当且仅当这个数是完全平方数。

因为原题可以变成找出最小的 使得 中恰好有 个完全平方数。

时间复杂度：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long

void solve()
{
    ll k;
    cin >> k;

    auto check = [&](ll x) {
        ll l = 1, r = 2e9;
        while (l < r) {
            ll mid = (l + r + 1) >> 1;
            if (mid * mid <= x)
                l = mid;
            else
                r = mid - 1;
        }
        return l <= x - k;
    };

    ll l = 1, r = 4e18;
    while (l < r) {
        ll mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

C. Bitwise Balancing

题意

给定三个非负整数 ，求方程

的解，无解打印 -1。

题解

考虑拆位，如果 上某一位是1，则 上这一位必为1， 上这一位必为 0，因为不可能出现 上这一位为0， 上这一位为 1的情况。

如果 上某一位是0，则两者在这一位上必然相等。

分情况讨论即可。

时间复杂度：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long

void solve()
{
    ll b, c, d;
    cin >> b >> c >> d;
    ll ans = 0;
    for (int i = 0; i <= 62; i++) {
        if ((d >> i) & 1) {
            if (!((b >> i) & 1)) {
                if ((c >> i) & 1) {
                    cout << -1 << endl;
                    return;
                }
                else
                    ans += (1ll << i);
            }
        }
        else {
            if ((b >> i) & 1) {
                if (!((c >> i) & 1)) {
                    cout << -1 << endl;
                    return;
                }
                else {
                    ans += (1ll << i);
                }
            }
        }
    }
    // assert((ans | b) - (ans & c) == d);
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

D. Connect the Dots

题意

有 这些点，起初都是孤立点，接下来 次操作，每次操作选择三个整数 ，然后连接 这些点，使其连通。

执行完所有操作后，问这些点形成了多少个连通块。

题解

发现 很小，最大只有10，考虑维护每个点后面十个点是否与它连通，连通可以直接用并查集维护。

由于每次操作涉及多个点，为了降低时间复杂度，每次将从 开始打标记，当计算完 和他后面十个点的边之后，将 的标记传递给 ，直到序列的结尾点。

时间复杂度： 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    std::vector<int> p;
    DSU(int n)
    {
        p.resize(n + 1);
        std::iota(p.begin(), p.end(), 0);
    }

    int find(int x)
    {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    bool same(int a, int b) { return find(a) == find(b); }

    void merge(int a, int b) { p[find(a)] = find(b); }
};

void solve()
{
    int n, m;
    cin >> n >> m;
    DSU T(n);
    int a, d, k;

    vector<vector<int>> tag(n + 1, vector<int>(11));

    for (int i = 1; i <= m; i++) {
        cin >> a >> d >> k;
        tag[a][d]++;
        tag[a + k * d][d]--;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 10; j++) {
            if (tag[i][j] > 0) {
                T.merge(i, i + j);
                tag[i + j][j] += tag[i][j];
            }
        }
    }

    int ans = 0;
    unordered_set<int> st;
    for (int i = 1; i <= n; i++) st.insert(T.find(i));
    cout << st.size() << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

E. Expected Power

题意

给定一个数组 和概率数组 ，每个 有 的概率被插入到可重集 中。

求 。

其中 表示 中所有元素的异或和。

题解

观察到 范围很小，于是 的范围也一定是 ，于是 可以表示为

而 可以用经典的概率 dp 求解：

设 为考虑前 个数，选择一些数使得异或和为 的概率，于是有转移方程：

直接计算即可，注意到 只会从 转移而来，可以滚动掉一维。

时间复杂度： 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long

constexpr ll mod = 1e9 + 7;
constexpr ll mu = 285700002;

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1), p(n + 1);
    ll B = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        B = max(B, __lg(a[i]));
    }
    B++;
    for (int i = 1; i <= n; i++) cin >> p[i], p[i] = (p[i] * mu) % mod;
    vector<ll> dp(1024);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        vector<ll> nxt(1024);
        for (int j = 0; j < 1024; j++) {
            nxt[j] = (nxt[j] + (dp[j] * (1 - p[i] + mod) % mod) % mod) % mod;
            nxt[j ^ a[i]] = (nxt[j ^ a[i]] + dp[j] * p[i] % mod) % mod;
        }
        for (int j = 0; j < 1024; j++) dp[j] = nxt[j];
    }
    ll ans = 0;
    for (int i = 1; i < (1 << B); i++) {
        ans = (ans + ((1ll * i * i) % mod) * dp[i] % mod) % mod;
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

F. Count Leaves

tag ：min_25筛

题意

原题题意可化为：

求 。

其中 ，的因数个数 。

题解

首先不难发现当给定 时，如果 则 ，也就是说 满足积性函数。

考虑 中 为质数时， 的值相当于求有多少条长度为 的路径使得 中始终有 ， 为素数时，这样的路径只会有 条。

考虑 其中 为素数，则这样的路径有 种，而 是多项式形式，因此有 ​ ，考虑用 min_25 筛求前缀和。

时间复杂度：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long

constexpr ll mod = 1e9 + 7;
constexpr int N = 1e6 + 10;

ll qpow(ll aa, int bb)
{
    ll res = 1;
    while (bb) {
        if (bb & 1) res = (res * aa) % mod;
        aa = (aa * aa) % mod;
        bb >>= 1;
    }
    return res;
}

struct Combnum {
    vector<ll> fac, ifac;
    int n;
    void init(int _n)
    {
        this->n = _n;
        fac.resize(n + 1, 0), ifac.resize(n + 1, 0);
        fac[0] = 1;
        for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
        ifac[n] = qpow(fac[n], mod - 2);
        for (int i = n - 1; i >= 0; i--) {
            ifac[i] = ifac[i + 1] * (i + 1) % mod;
        }
    }
    ll C(ll i, ll j)
    {
        if (i < j) return 0;
        return (fac[i] * ifac[j] % mod) * ifac[i - j] % mod;
    }
} c;

void solve()
{
    ll n, K, d, cp, cnt = 0, tot = 0;
    cin >> n >> K >> d;
    vector<ll> primes, sum, w, id1, id2, g;
    vector<bool> st;
    cp = c.C(K + d, d);
    ll sq = sqrt(n);

    primes.assign(2 * sq + 7, 0);
    st.assign(2 * sq + 7, false);
    g.assign(2 * sq + 7, 0);
    w.assign(2 * sq + 7, 0);
    id1.assign(2 * sq + 7, 0);
    id2.assign(2 * sq + 7, 0);
    sum.assign(2 * sq + 7, 0);

    auto sieve = [&](int n) -> void {
        for (int i = 2; i <= n; i++) {
            if (!st[i]) primes[++cnt] = i, sum[cnt] = (sum[cnt - 1] + cp) % mod;
            for (int j = 1; j <= cnt && i * primes[j] <= n; j++) {
                st[i * primes[j]] = true;
                if (i % primes[j] == 0) break;
            }
        }
    };

    sieve(sq);

    for (ll l = 1, r; l <= n; l = r + 1) {
        r = min(n, n / (n / l));
        w[++tot] = n / l;
        g[tot] = cp * (w[tot] % mod - 1) % mod;
        if (w[tot] <= sq)
            id1[w[tot]] = tot;
        else
            id2[n / w[tot]] = tot;
    }
    for (int j = 1; j <= cnt; j++) {
        for (int i = 1; i <= tot && primes[j] * primes[j] <= w[i]; i++) {
            ll tmp = w[i] / primes[j];
            int p = tmp <= sq ? id1[tmp] : id2[n / tmp];
            g[i] = (g[i] - (g[p] - sum[j - 1] + mod) % mod + mod) % mod;
        }
    }

    auto S = [&](auto S, ll i, ll j) -> ll {
        if (primes[j] >= i) return 0;

        ll p = i <= sq ? id1[i] : id2[n / i];

        ll ans = (g[p] - sum[j] + mod) % mod;
        for (int k = j + 1; k <= cnt && primes[k] * primes[k] <= i; k++) {
            ll pe = primes[k];
            for (int e = 1; pe <= i; e++, pe = pe * primes[k]) {
                ans = (ans + c.C(d + e * K, d) * ((S(S, i / pe, k) + (e > 1)) % mod) % mod) % mod;
            }
        }
        return ans;
    };

    cout << (S(S, n, 0) + 1) % mod << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    c.init(N * 10);
    while (tt--) {
        solve();
    }
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。