题解 | #牛客周赛 Round 13#

A

$O(n^{2})$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            cout << a[i][j] << " \n"[j == 0];
        }
    }

    return 0;
}

B

$O(n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int n, x, y;
    cin >> n >> x >> y;
    int ans = 1;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (a >= x && b <= y) {
            ans = i64(ans) * 2 % P;
        }
    }

    cout << (ans - 1 + P) % P << '\n';
                                 
    return 0;
}

C

$O(\sum n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    vector<int> f(4);
    int a[4] = {26, 26, 10, 4};
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            f[0]++;
        } else if (s[i] >= 'a' && s[i] <= 'z') {
            f[1]++;
        } else if (s[i] >= '0' && s[i] <= '9') {
            f[2]++;
        } else {
            f[3]++;
        }
    }
                                          
    i64 ans = 0;
    for (int i = 0; i < 4; i++) {
        if (f[i] > 1) {
            ans += 65LL * f[i];
        } else {
            ans += a[i] - 1;
        }
    }
    cout << ans << '\n';
}
                   
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }                      
    return 0;
}

D

可以改变方向的边分为两种，第一种，某个点到 $1$ 的最短路径有多条，那么与该点直接相连的边可以选一些边改变方向；第二种，删除该边不影响任何一个点到 $1$ 的最短路数量和距离。

$O(n m)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 1000000007;

#define range(a) begin(a), end(a)

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

    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

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

    queue<int> q;
    vector<int> dis(n, -1);
    q.push(0);
    dis[0] = 0;
    while (!q.empty()) {
        auto x = q.front();
        q.pop();

        for (auto y : g[x]) {
            if (dis[y] == -1) {
                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }
    }

    i64 ans1 = accumulate(range(dis), 0LL) % P;

    i64 ans2 = 1;
    int cnt2 = m;

    for (int i = 1; i < n; i++) {
        int c = 0;
        for (int &j : g[i]) {
            if (dis[j] == dis[i] - 1) {
                c++;
                cnt2--;
            }
        }
        int res = 1;
        for (int i = 0; i < c; i++) {
            res = i64(res) * 2 % P;
        }
        ans2 = (ans2 * (res - 1 + P) % P) % P;
    }
  
    int res = 1;
    for (int i = 0; i < cnt2; i++) {
        res = i64(res) * 2 % P;
    }
    ans2 = (ans2 * res) % P;
                          
    cout << ans1 << ' ' << ans2 << '\n';
    
    return 0;
}

E

能翻倍的攻击一定是排序后最大的部分且连续。

$O(n\log n)$ 。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

#define range(a) begin(a), end(a)

template <class T>
T max(const vector<T> &a) {
    return *max_element(a.begin(), a.end());
}      

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> f(3);
    for (int i = 0; i < n; i++) {
        string s;

        cin >> s >> a[i];
        if (s[0] == 'i') {
            f[0]++;
        } else if (s[0] == 't') {
            f[1]++;
        } else {
            f[2]++;
        }
    }

    int k = min(n / 2, n - max(f));
    i64 ans = 0;
    sort(range(a), greater());
    for (int i = 0; i < n; i++) {
        if (i < k) {
            ans += a[i];
        }
        ans += a[i];
    }
    cout << ans << '\n';
    
    return 0;
}