牛客周赛 Round 29

发表于 更新于 分类于 阅读次数： 本文字数： 854 阅读时长 ≈ 3 分钟
If you don't try, you'll never know.

A. 小红大战小紫

思路：

  • 比较大小即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int a, b;
    std::cin >> a >> b;

    if (a == b) {
        std::cout << "draw\n";
        return 0;
    }

    std::cout << (a > b ? "kou\n" : "yukari\n");
    
    return 0;
}

B. 小红的白日梦

思路：

  • 按照题意模拟即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::string a, b;
    std::cin >> a >> b;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 'N' && b[i] == 'Y') {
            ans += 2;
        } else if (a[i] == 'Y' && b[i] == 'N') {
            ans += 2;
        } else if (a[i] == 'Y' && b[i] == 'Y') {
            ans += 3;
        }
    }
    std::cout << ans << "\n";

    return 0;
}

C. 小红的小小红

思路：

  • 用bool数组标记一下，只要把第一个xiao和hong的位置找到即可，未标记的就可以直接追加在xiaohong后面

时间复杂度：

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

    int n = s.size();

    bool f1 = false;
    bool f2 = false;
    std::vector<int> vis(n);
    for (int i = 0; i + 3 < n; i++) {
        if (s.substr(i, 4) == "xiao" && !f1) {
            vis[i] = vis[i + 1] = vis[i + 2] = vis[i + 3] = true;
            f1 = true;
        } 
        if (s.substr(i, 4) == "hong" && !f2) {
            vis[i] = vis[i + 1] = vis[i + 2] = vis[i + 3] = true;
            f2 = true;

        }
        if (f1 && f2) break;
    }

    std::cout << "xiaohong";
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            std::cout << s[i];
        }
    }

    return 0;
}

D. 小红的中位数

思路：

  • 存一下初始位置的下标，然后从小到大排序
  • 推理一下，可以发现每次移动中点 前后的数，中位数只会在 左右浮动
  • 为奇数时
    • 当删除 左边的数时，中位数等于
    • 当删除 时，中位数等于
    • 当删除 右边的数时，中位数等于
  • 为偶数时
    • 当删除 左边的数时，中位数等于
    • 当删除 时，中位数等于
    • 当删除 右边的数时，中位数等于 ​

时间复杂度：

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(1);

    int n;
    std::cin >> n;

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

    std::sort(a.begin(), a.end(), [&](auto i, auto j) {
        return i[0] < j[0];
    });

    std::vector<double> ans(n + 1);
    if (n % 2 == 0) {
        int mid = n / 2;
        for (int i = 1; i <= n; i++) {
            if (i <= mid) {
                ans[a[i][1]] = a[mid + 1][0];
            } else {
                ans[a[i][1]] = a[mid][0];
            }
        }
    } else {
        int mid = (n + 1) / 2;
        for (int i = 1; i <= n; i++) {
            if (i < mid) {
                ans[a[i][1]] = 1.0 * (a[mid + 1][0] + a[mid][0]) / 2;
            } else if (i == mid) {
                ans[a[i][1]] = 1.0 * (a[mid - 1][0] + a[mid + 1][0]) / 2;
            } else {
                ans[a[i][1]] = 1.0 * (a[mid][0] + a[mid - 1][0]) / 2;
            }
        }
    }

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

    return 0;
}

E. 小红构造数组

思路：

  • 将整数 分解成为 的形式，然后进行
  • 将这个数的质因子塑造成一个相邻位置的数一定不同的序列

时间复杂度：

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

    if (x == 1) {
        std::cout << "-1\n";
        return 0;
    }

    std::map<i64, int> mp;
    for (int i = 2; i <= x / i; i++) {
        while (x % i == 0) {
            mp[i]++;
            x /= i;
        }
    }

    if (x > 1) {
        mp[x] += 1;
    }

    std::vector<i64> ans;
    while (!mp.empty()) { // bfs
        i64 a = -1, b = 0;
        for (auto [x, y] : mp) {
            if (ans.size() && x == ans.back()) {
                continue ;
            }
            if (y > b) {
                std::tie(a, b) = std::pair(x, y);
            }
        }
        if (a == -1) {
            std::cout << "-1\n";
            return 0;
        }
        ans.push_back(a);
        mp[a]--;
        if (mp[a] == 0) {
            mp.erase(a);
        }
    }

    std::cout << ans.size() << "\n";
    for (auto x : ans) {
        std::cout << x << " ";
    }
    std::cout << "\n";

    return 0;
}

F. 小红又战小紫

思路：