Codeforces Round 786 (Div. 3)

发表于 更新于 分类于 阅读次数： 本文字数： 551 阅读时长 ≈ 2 分钟
Every noble work is at first impossible.

A. Number Transformation

思路：

  • 数据范围较小，可以直接枚举底数和指数

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

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

    bool f = true;
    for (int i = 1; i < 100; i++) {
        int t = x;
        for (int j = 1; j <= 10; j++) {
            t *= i;
            if (t == y) {
                std::cout << j << " " << i << "\n";
                f = false;
                return ;
            }
        }	
    }
    if (f) {
        std::cout << "0 0\n";
    }
}

B. Dictionary

思路：

  • 预处理一下所有的两个字母组成的字符串，然后枚举查找

时间复杂度：\(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
30
31
32
33
34
35
36
37
std::vector<std::string> sk;
void solve() {
    std::string s;
    std::cin >> s;

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

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

    for (char i = 'a'; i <= 'z'; i++) {
        std::string tmp = "";
        for (char j = 'a'; j <= 'z'; j++) {
            if (i == j) continue ;
            tmp += i;
            tmp += j;
            sk.push_back(tmp);
            tmp = "";
        }
    }

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }    

    return 0;
}

C. Infinite Replacement

思路：

  • 本题主要涉及组合数，可以发现，只要 \(t\) 中包含字符 \(a\)，那么一定是不可能的
  • 如果 \(t\) 等于 \(a\) 那么不可能会继续增加，所以只要原本的一个字符串 \(s\)
  • 如果 \(t\) 中不包含 \(a\) 那么数量一定是 \(\Sigma_{i=0}^{n}C_{n}^{i}\)​

时间复杂度：\(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
i64 C[60][60];

void solve() {
    std::string s, t;
    std::cin >> s >> t;

    int n = s.size();

    if (t.find("a") != -1 && t.size() != 1) {
        std::cout << "-1\n";
        return ;
    }    
    if (t == "a") {
        std::cout << "1\n";
        return ;
    }
    i64 ans = 1;
    for (int i = 1; i <= n; i++) {
        ans += C[n][i];
    }
    std::cout << ans << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
        
    for (int i = 0; i <= 52; i++) {
        for (int j = 0; j <= i; j++) {
            if (!j) C[i][j] = 1;
            else C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }    

    return 0;
}

D. A-B-C Sort

思路：

  • 感觉这题非常巧妙，它通过一个B数组来误导我们，最后可以发现，其实A中的相邻的数组元素就是B中相邻元素，只不过位置可能不相同，然后判断如果出现逆序，就互相换个位置
  • 最后判断是否有序即可

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

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

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

    for (int i = n - 2; i >= 0; i -= 2) {
        if (a[i + 1] < a[i]) {
            std::swap(a[i + 1], a[i]);
        }
    }

    if (std::is_sorted(a.begin(), a.end())) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}