牛客周赛 Round 34

发表于 更新于 分类于 阅读次数： 本文字数： 457 阅读时长 ≈ 2 分钟
Fading is true while flowering is past.

D. 小红的陡峭值

思路：

  • 首先，可以发现，如果出现一个元素两边都出现另外一个元素，那么一定不行
  • 如果非0元素个数大于2，那么一定不行
  • 所以我们可以对这仅有的1到2个元素进行BFS，扩展数组元素，最后判断即可

时间复杂度：

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

    std::queue<int> q;
    std::vector<int> a(n + 1), vis(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        if (a[i]) {
            q.push(i);
            vis[i] = true;
        }
    }

    if (q.size() == 0) {
        for (int i = 0; i < n; i++) {
            if (i) {
                std::cout << 1 << " \n"[i == n - 1];
            } else {
                std::cout << 2 << " ";
            }
        }
    }

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        if (t > 1 && a[t - 1] == 0) {
            a[t - 1] = a[t];
            q.push(t - 1);
        }
        if (t < n && a[t + 1] == 0) {
            a[t + 1] = a[t];
            q.push(t + 1);
        }
    }

    int val = 0;
    for (int i = 2; i <= n; i++) {
        val += abs(a[i] - a[i - 1]);
    }
    if (val > 1) {
        std::cout << "-1\n";
    } else {
        if (val == 0) {
            if (vis[1] && vis[n]) {
                std::cout << "-1\n";
            } else {
                if (!vis[1]) ++a[1];
                else ++a[n];
            }
        }
        for (int i = 0; i < n; i++) {
            std::cout << a[i + 1] << " \n"[i == n - 1];
        }
    }

    return 0;
}

E. 小红的树形 dp

思路：

  • 官方题解是二分图
  • 这里写个DFS，如果出现一个父节点和子节点的状态相同，那么就一定无解，然后出现一个?和另一个不同的状态就修改即可

时间复杂度：

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

    std::string s;
    std::cin >> s;
    s = '&' + s;

    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bool ok = true;
    auto dfs = [&](auto self, int u, int fa) {
        if (s[u] == '?') s[u] = s[fa] == 'd' ? 'p' : 'd';
        else if (s[u] == s[fa]) {
            ok = false;
            return ;
        }
        for (auto x : adj[u]) {
            if (x == fa) continue ;
            self(self, x, u);
        }
    };
    dfs(dfs, 1, 0);

    if (ok) {
        for (int i = 1; i <= n; i++) {
            std::cout << s[i];
        }
        std::cout << "\n";
    } else {
        std::cout << "-1\n";
    }

    return 0;
}