牛客周赛 Round 30

A. 小红的删字符

思路：

• 删除中间的那个字符即可

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    char a, b, c;
    std::cin >> a >> b >> c;

    std::cout << a << c << "\n";
    
    return 0;
}

B. 小红的正整数

思路：

• 找到除0以外，最小的字符出现的位置，然后将其他字符排序接在最小的字符后面

时间复杂度：

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

    std::sort(x.begin(), x.end());

    char f;
    int p = -1;
    for (int i = 0; i < x.size(); i++) {
        if (x[i] != '0') {
            f = x[i];
            p = i;
            break;
        }
    }

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

    return 0;
}

C. 小红构造回文

思路：

• 分奇偶情况，然后从中间开始双指针扫描，出现不一致的相邻两个字符直接交换位置然后输出字符串，否则一定无解

时间复杂度：

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

    int n = s.size();

    if (n & 1) {
        int mid = n / 2;
        int l = mid - 1, r = mid + 1;
        while (l > 0 && r < n) {
            if (s[l] != s[l - 1] && s[r] != s[r + 1]) {
                std::swap(s[l], s[l - 1]);
                std::swap(s[r], s[r + 1]);
                std::cout << s << "\n";
                return 0;
            }
            l--, r++;
        }
    } else {
        int mid = n / 2;
        int l = mid - 1, r = mid;
        while (l > 0 && r < n) {
            if (s[l] != s[l - 1] && s[r] != s[r + 1]) {
                std::swap(s[l], s[l - 1]);
                std::swap(s[r], s[r + 1]);
                std::cout << s << "\n";
                return 0;
            }
            l--, r++;
        }
    }
    std::cout << "-1\n";

    return 0;
}

D. 小红整数操作

思路：

• 可以将x和y分别除gcd(x, y),这样等于一次性把操作2做完，然后我们分别求a的最大范围，分别求a的上界和下界

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int x, y, l, r;
    std::cin >> x >> y >> l >> r;

    int g = std::gcd(x, y);
    
    x /= g;
    y /= g;

    int mn1 = (l + x - 1) / x;
    int mx1 = r / x;

    int mn2 = (l + y - 1) / y;
    int mx2 = r / y;

    std::cout << std::min(mx1, mx2) - std::max(mn1, mn2) + 1 << "\n";

    return 0;
}

E. 小红树上染色

思路：

• 树形 ，我们维护两个状态：染色和不染色的方案数

  1. 对于叶子节点，有两种方案：染色或不染色。
  2. 对于非叶子节点，我们考虑染色和不染色两种情况：
     • 如果当前节点染色了，那么其子节点必须不染色，因此染色方案数等于子节点不染色的方案数的乘积。
     • 如果当前节点不染色，那么其子节点可以染色也可以不染色，因此不染色方案数等于子节点染色和不染色方案数之和。

  我们用 表示不染色， 表示染色，那么状态转移方程为:

  • ​

时间复杂度：

constexpr int P = 1E9 + 7;

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

    std::vector<std::vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    std::vector dp(n + 1, std::vector<i64>(2, 0));
    std::function<void(int, int)> dfs = [&](int u, int fa) {
        dp[u][0] = dp[u][1] = 1;
        for (auto x : g[u]) {
            if (x == fa) continue ;
            dfs(x, u);
            dp[u][0] = dp[u][0] * (dp[x][1] + dp[x][0]) % P;
            dp[u][1] = dp[u][1] * dp[x][0] % P;
        }
    };
    dfs(0, -1);

    std::cout << (dp[0][0] + dp[0][1]) % P << "\n";

    return 0;
}