快写一首情歌雅俗共赏

妙评： 很多年后,热情总会被琐碎的生活消磨殆尽,时间像弱碱弱酸在不留神间慢慢侵蚀掉我弥足珍贵的记忆壁垒,带走脸颊的绯红和眼角的雀跃。那时候,我已半截坐进泥土里,形容枯槁;剩下的半截仍在燃起的缕缕炊烟中呼喊着岁月,肆意叫囂。

img

牛客周赛 Round 13

总体感言：A题观察样例，B题乘法公式直接计算，C题也是乘法公式，D题由于要最短路，直接跑单源，然后不要的边随便乘法公式放，要的边放一条，也是乘法公式，E题贪心，众数定理的学习，min(n/2,m-max(f))

A

观察样例，就是直接反着来一遍就可以了

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
#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

第一眼以为是dp,发现只需要找到小的然后根据乘法公式直接乘2就可以了。

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
#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

可以先统计4种字符出现的个数，然后如果这种字符只有一个，那么我们只能修改为和他相同种类数量减去1，不然就是直接改成全部再减去一，也就是65

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
#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
题目给出了n个点和m条无向边，要求调整为有向边，且使得所有点到1的最短路最短。问有几种方案。

先无脑求出最短路，然后考虑每条边的调整方案。 不在最短路上的边，两个方向都可以，乘2即可。注意不要算两次。 在最短路上的边，连接u，v，那么一定有dis[u]+1==dis[v]，那么我们从v的角度考虑。 u可能对应着p条边(点)，都可以使u的最短路最短，那么保留一条或多条都可以。 一共有\(2^p\)-1种方案。

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
64
65
66
67
68
69
70
71
72
73
74
75
#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 u = q.front();
        q.pop();

        for (auto &v : g[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
//无脑求出最短路
    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;
        //2^p-1种选择
    }
  
    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

最贪的思路一定是两种不同属性依次释放，以及尽量让大的伤害翻倍，这样子就可以了

然后的话就直接翻倍就好了

主要是领会这个众数的思路

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
#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;
}