牛客小白月赛87

发表于 更新于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 5 分钟
A laugh can be a very powerful thing.

A. 小苯的石子游戏

思路：

  • 模拟即可

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    int p = 0, A = 0, B = 0;
    for (int i = n - 1; i >= 0; i--, p++) {
        if (p % 2 == 0) {
            A += a[i];
        } else {
            B += a[i];
        }
    }

    std::cout << (A > B ? "Alice\n" : "Bob\n");
}

B. 小苯的排序疑惑

思路：

  • 因为只能操作一次，所以只需要判断首尾即可

时间复杂度：\(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<int> b = a;
    std::sort(b.begin(), b.end());

    if (b[0] == a[0] || b[n - 1] == a[n - 1]) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

C. 小苯的IDE括号问题（easy）

思路：

  • 首先定位光标，然后模拟这个两种操作
  • 注意erase的时间复杂度是logn的，n的范围是2e5，时间复杂度nlogn可以过本题

时间复杂度：\(O(nlogn)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    s = '&' + s + '&';

    n = s.size();

    int p = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'I') {
            p = i;
            break;
        }
    }

    for (int i = 0; i < k; i++) {
        std::string op;
        std::cin >> op;
        if (op == "backspace") {
            char a = s[p - 1];
            char b = s[p + 1];
            if (a == '&') continue ;
            if (a == '(' && b == ')') {
                s.erase(s.begin() + p + 1);
                s.erase(s.begin() + p - 1);
                p--;
            } else {
                s.erase(s.begin() + p - 1);
                p--;
            }
        } else {
            char a = s[p - 1];
            char b = s[p + 1];
            if (b == '&') continue ;
            s.erase(s.begin() + p + 1);
        }
    }

    for (char c : s) {
        if (c == '&') continue ;
        std::cout << c;
    }
    std::cout << "\n";

    return 0;
}

D. 小苯的IDE括号问题（hard）

思路：

  • 和简单版本的思路基本完全一样，只不过加了个光标移动的属性
  • 模拟即可

时间复杂度：\(O(nlogn)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    s = '&' + s + '&';

    n = s.size();

    int p = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'I') {
            p = i;
            break;
        }
    }

    for (int i = 0; i < k; i++) {
        std::string op;
        std::cin >> op;
        if (op == "backspace") {
            char a = s[p - 1];
            char b = s[p + 1];
            if (a == '&') continue ;
            if (a == '(' && b == ')') {
                s.erase(s.begin() + p + 1);
                s.erase(s.begin() + p - 1);
                p--;
            } else {
                s.erase(s.begin() + p - 1);
                p--;
            }
        } else if (op == "delete") {
            char a = s[p - 1];
            char b = s[p + 1];
            if (b == '&') continue ;
            s.erase(s.begin() + p + 1);
        } else if (op == "<-") {
            if (s[p - 1] == '&') continue ;
            std::swap(s[p - 1], s[p]);
            p--;
        } else if (op == "->") {
            if (s[p + 1] == '&') continue ;
            std::swap(s[p + 1], s[p]);
            p++;
        }
    }

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '&') continue ;
        std::cout << s[i];
    }
    std::cout << "\n";

    return 0;
}

E. 小苯的数组构造

思路：

  • 我们可以试一下几种情况，可以发现只要我们每次向一个方向正 or 负，那么最终的极值差一定不会改变
  • 然后我们大胆猜测，这个与取值正负无关
  • 所以我们只需要，找逆序即可，然后按规则模拟

时间复杂度：\(O(n)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    int max = *max_element(a.begin(), a.end());
    a[n] = max;

    std::vector<int> ans(n);
    for (int i = 1; i <= n; i++) {
        if (a[i] < a[i - 1]) {
            ans[i] = a[i - 1] - a[i];
            a[i] += ans[i];
        }
    }

    for (int i = 0; i < n; i++) {
        std::cout << ans[i] << " \n"[i == n - 1];
    }

    return 0;
}

F. 小苯的数组切分

思路：

  • 首先我们考虑枚举l和r两个端点，首先O(n)的枚举任意一个端点，会发现两个端点都到O(n^2)了，所以其中一个定要优化到logn才可以
  • 然后我们可以发现一个性质，在做&运算时，最多只会有logn个取值，然后我们先预处理&运算的过程，用cnt[i][j]来维护前i位中1的个数
  • 我们将那些出现进行&运算，出现递减序的位置进行存储，然后开始O(n)的枚举l端点

时间复杂度：\(O(nlogn)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    std::vector cnt(n + 1, std::vector<int>(30));
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        for (int j = 0; j < 30; j++) {
            cnt[i][j] = cnt[i - 1][j];
            if ((a[i] >> j) & 1) cnt[i][j]++;
        }
    }

    std::vector<int> f(n + 2);
    f[n + 1] = (1LL << 31) - 1;

    std::vector<int> p;
    for (int i = n; i >= 1; i--) {
        f[i] = f[i + 1] & a[i];
        if (f[i] < f[i + 1]) {
            p.emplace_back(i);
        }
    }

    i64 ans = 0, val = 0;
    for (int i = 1; i <= n; i++) {
        val ^= a[i];
        for (int j = 0; j < p.size(); j++) {
            if (i + 1 < p[j]) {
                int l = i + 1, r = p[j] - 1;

                int t = 0;
                for (int k = 0; k < 30; k++) {
                    if (cnt[r][k] - cnt[l - 1][k] > 0) {
                        t |= 1 << k;
                    }
                }
                ans = std::max(ans, val + t + f[r + 1]);
            }
        }
    }
    std::cout << ans << "\n";

    return 0;
}

G. 小苯的逆序对

思路：

  • 前置知识：树状数组求逆序对
  • 首先我们将每一个值得下标存储，

时间复杂度：\(O(n \times (logn + \sqrt{n}))\)

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
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        a[x] = i;
    }
    std::vector<i64> dp(n + 1), cnt(n + 1);
    for (int i = 1; i <= n; i++) {
        std::vector<int> b;
        for (int j = i; j <= n; j += i) {
            b.emplace_back(a[j]);
        }
        auto c = b;
        std::sort(c.begin(), c.end());

        int m = b.size();
        Fenwick<i64> fen(m);
        for (int j = m - 1; j >= 0; j--) {
            int x = std::lower_bound(c.begin(), c.end(), b[j]) - c.begin();
            cnt[i] += fen.sum(x);
            fen.add(x, 1);
        }
    }
    for (int i = n; i; i--) {
        dp[i] = cnt[i];
        for (int j = i + i; j <= n; j += i) {
            dp[i] -= dp[j];
        }
    }

    std::cout << dp[1] << "\n";
    
    return 0;
}