J. 筛子

在n行m列的网格的最左上角的格子上，有一个边长和网格格子边长相等的骰子。 初始，这个骰子1在顶面，2朝前，3朝右，i的背后是7−i，

现在你可以做任意多次操作，每次操作为以下两种：
• 若当前骰子所在的格子没有数字，在这个格子上写下骰子底面的数字；
• 选择上下左右四个方向的某一个，将骰子沿着这个方向滚一次：选择骰子底面对 应方向的棱，将骰子沿着这条棱旋转九十度。你不能将骰子滚出网格。 . 注.意： .你 .可 .以 .在 .骰 .子 .经 .过 .一 .个 .没 .有 .数 .字 .的 .格 .子 .时 .选 .择 .不 .在 .这 .个 .格 .子 .上 .写 .下 .骰 .子 .底 .面 . 的.数 .字。

你希望最大化最后网格上所有写过数字的格子的数字的和。

解

注意到只要有 2 2的空间，那么经过一系列操作后所有格子都必然可以刻上数字6， 所有只要有一个 2 2空间答案就是 6 * 格子数量， 否则就无法操作，答案定死

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
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

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

    int n, m;
    cin >> n >> m;

    vector<int> a = { 6, 3, 1, 4 }, b = { 6, 2, 1, 5 };

    i64 ans = 0;
    if (n == 1) {
        for (int i = 0; i < m; i++) {
            ans += a[i % 4];
        }
        cout << ans << '\n';
    } else if (m == 1) {
        for (int i = 0; i < n; i++) {
            ans += b[i % 4];
        }
        cout << ans << '\n';
    } else {
        cout << 1LL * 6 * n * m << '\n';
    }

    return 0;
}

K. 小 C 的神秘图形

注意到 从高位到低位，只要每一位有一个1， 就可以被三进制取模走到下一轮，所以只需要所有位置上s【i】 == ‘1’ 或者 t【i】 == ‘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
#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;

    string s, t;
    cin >> s >> t;

    bool f = 1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1' || t[i] == '1') {

        } else {
            f = 0;
            break;
        }
    }

    cout << f << '\n';

    return 0;
}

B. osu!mania

根据题意模拟即可，注意精度问题，0.5在double可能会被计算成4.9999999…，对于计算结果加上一个1e-9后加0.5转整数实现四舍五入

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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    i64 n;
    cin >> n;

    vector<i64> a(6);
    for (int i = 0; i < 6; i++) {
        cin >> a[i];
    }   

    vector<i64> b = { 300, 300, 200, 100, 50, 0 };
    vector<i64> c = { 320, 300, 200, 100, 50, 0 };

    i64 x{}, y{};
    for (int i = 0; i < 6; i++) {
        x += b[i] * a[i];
        y += c[i] * a[i];
    }
    i64 bas = accumulate(a.begin(), a.end(), 0LL);

    double res = (5.0 * n) * max<double>(0, 1.0 * y / (320 * bas) - 0.8);
    cout << fixed << setprecision(2) << 100.0 * x / (bas * 300LL) << "% ";
    cout << (i64)floor(res + 0.5 + 1e-9) << '\n';
}

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

    int t;
    cin >> t;

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

    return 0;
}

E. 合成大西瓜

小白有n个西瓜（保证n是奇数），每个西瓜有个重量ai。她在这n个西瓜之间建 立了m条无向边，使任意两个西瓜之间都至少存在一条路径能到达。 小白现在可以选择三个西瓜进行合并，具体地，她会选择三个不同的西瓜x,y,z满 足x,y之间有一条无向边，y,z之间有一条无向边。她会得到一个新的西瓜w，其重量 aw=max(ay,min(ax,az))。接下来，她对于“至少和x,y,z中某个西瓜之间有无向边” 的西瓜t，建立了一条(w,t)之间的无向边。最后，小白删去了x,y,z三个西瓜以及某 一端为x,y,z的无向边。 可以证明一定存在一种合并n−1 2 次的方案使得最后仅剩下一个西瓜，小白想知道最 后那个西瓜重量的最大值是多少？

解

画图可知，只要一个节点deg >= 2，那么可以经过一系列操作把他变成最后剩下来的节点，所以deg >= 2的节点中值最大的是可以取到的，
现在考虑deg = 1，即叶子节点，由于每次操作总是会把两个叶子取得min，所以最大的那个取不到，但是可以把最大的两个留在最后操作，所以deg = 1中第二的大的可以取到，

所以答案就是max (叶子节点第二大， 非叶子节点最大)

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
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
struct node {
    int u;
    i64 v;
    node() {}
    node(int u, i64 v) : u(u), v(v) {}
};
const i64 inf = 1e9 + 8;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> deg(n + 1);
    vector<set<int>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;

        e[x].insert(y);
        e[y].insert(x);
        deg[x]++;
        deg[y]++;
    }

    if (n == 1) {
        cout << a[1] << '\n';
        return 0;
    }
    i64 ans = 0;
    i64 r = 0, r2 = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] >= 2) {
            ans = max(ans, a[i]);
        } else {
            if (a[i] > r) {
                r2 = r;
                r = a[i];
            } else if (a[i] == r) {
                r2 = r;
            }
        }
    }
    ans = max(ans, r2);
    cout << ans << '\n';

    return 0;
}

I. 算术

根据题意，发现：

  • 先把 1, 2全部加起来变3
  • 把1 全部变3
  • 把1 全部变2
  • 把剩下的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
76
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int N = 505, mod = 998244353;
int pre[20][N];

void solve() {
    vector<int> a(12);
    for (int i = 1; i <= 9; i++) {
        cin >> a[i];
    }

    int t = min(a[1], a[2]);
    a[3] += t;
    a[1] -= t;
    a[2] -= t;

    int ans = 1;
    if (a[1] == 1) {
        for (int i = 2; i <= 9; i++) {
            if (a[i]) {
                a[i]--;
                ans = i + 1;
                break;
            }
        }
    } else if (a[1] % 3 == 1) {
        a[3] += (a[1] - 4) / 3;
        a[2] += 2;
    } else if (a[1] % 3 == 2) {
        a[3] += a[1] / 3;
        a[2] += 1;
    } else {
        a[3] += a[1] / 3;
    }

    a[1] = 0;

    for (int i = 1; i <= 9; ++i) {
        ans = 1ll * ans * pre[i][a[i]] % mod;
    }
    
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int x = 1; x <= 9; x++) {
        pre[x][0] = 1;
        for (int i = 1; i <= 500; i++) {
            pre[x][i] = 1ll * pre[x][i - 1] * x % mod;
        }
    }

    int t;
    cin >> t;

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

    return 0;
}
/*
7
5 3 0 0 0 0 0 0 0
4 1 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 2
99 88 77 66 55 44 33 22 11
100 90 80 70 60 50 40 30 20
*/

C. 连方

构造：
首先第二行 全部 设置成和第一行反过来， 第6行和第7行相反
之后在第三行找一个位置，使得能斜着（相对第二行是方格的左下或者右下）第二行，但是不能和它直接连接，第五行找相同规则的和第六行相连

之后就只剩第四行，分类讨论将第三和第五相连即可

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    int n;
    cin >> n;

    string s, t;
    cin >> s >> t;
    s = " " + s;
    t = " " + t;

    vector e(8, vector<char> (n + 3, '.'));
    for (int i = 1; i <= n; i++) {
        e[1][i] = s[i];
        e[7][i] = t[i];
    }

    auto f = [&](int p, int l, int r) -> void {
        for (int i = l; i <= r; i++) {
            e[p][i] = '#';
        }
    };

    auto out = [&]() {
        for (int i = 1; i <= 7; i++) {
            for (int j = 1; j <= n; j++) {
                cout << e[i][j];
            }
            cout << '\n';
        }
    };

    bool can = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '.') can = 1;
    }

    bool can2 = 0;
    for (int i = 1; i <= n; i++) {
        if (t[i] == '.') can2 = 1;
    }

    if (can ^ can2 == 1) {
        cout << "No\n";
        return;
    }

    cout << "Yes\n";
    if ((can | can2) == 0) {
        for (int i = 2; i <= 6; i++) {
            f(i, 1, n);
        }
        out();
        return;
    }

    // can = 1;
    // for (int i = 1; i <= n; i++) {
    //     if (s[i] == '#') {
    //         can = 0;
    //     }
    // }
    // if (can) {
    //     for ()
    // }

    for (int i = 1; i <= n; i++) {
        if (e[1][i] == '.') {
            e[2][i] = '#';
        } else {
            e[2][i] = '.';
        }

        if (e[7][i] == '.') {
            e[6][i] = '#';
        } else {
            e[6][i] = '.';
        }
    }

    int shang{}, xia{};
    for (int i = 1; i <= n; i++) {
        if (e[2][i] != '#' && (e[2][i + 1] == '#' || e[2][i - 1] == '#')) {
            // int l = i, r{};
            // for (int j = i; j <= n; j++) {
            //     if (e[2][j] == '#') {
            //         r = j;
            //     } else {
            //         break;
            //     }
            // }
            shang = i;
            f(3, i, i);
            break;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (e[6][i] != '#' && (e[6][i + 1] == '#' || e[6][i - 1] == '#')) {
            // int l = i, r{};
            // for (int j = i; j <= n; j++) {
            //     if (e[6][j] == '#') {
            //         r = j;
            //     } else {
            //         break;
            //     }
            // }
            xia = i;
            f(5, i, i);
            break;
        }
    }

    if (abs(shang - xia) <= 1) {
        e[4][shang] = '#';
    }  else {
        for (int i = min(shang, xia) + 1; i <= max(min(shang, xia), max(shang, xia) - 1); i++) {
            e[4][i] = '#';
        }
    }
    out();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

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

    return 0;
}