SZTU Monthly 2023 Oct.

比赛链接

写在前面

题目难度：

这次比赛难度划分是四道简单题，两道中等题，两道困难题。 \(HGDF\) 简单题 ， \(EA\) 中等题， \(BC\) 困难题。

A 预测排名

考点：

  • 贪心
  • 模拟

题解：

题目给出了ACM赛制排名的说明，同时给出每个人的过题数量、每题的需要的时间和罚时次数，需要我们输出每个人的排名

AC Code

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

struct node
{
    int m;
    int t[111];
    int wa;
    int all;
    int id;
    int rank;

    void cal()
    {
        sort(t, t + m);
        int item = 0;
        for (int i = 0; i < m; i++)
        {
            item += t[i];
            all += item;
        }
        all += wa;
    }
} a[1111];

bool cmp1(node a, node b)
{
    if (a.m != b.m)
        return a.m > b.m;
    return a.all < b.all;
}

bool cmp2(node a, node b)
{
    return a.id < b.id;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i].m);
        for (int j = 0; j < a[i].m; j++)
            scanf("%d", &a[i].t[j]);
        for (int j = 0; j < a[i].m; j++)
        {
            int wa;
            scanf("%d", &wa);
            a[i].wa += wa * 20;
        }
        a[i].id = i;
        a[i].cal();
    }

    sort(a, a + n, cmp1);
    for (int i = 0; i < n; i++)
    {
        a[i].rank = i + 1;
        if (i != 0 && a[i].all == a[i - 1].all)
            a[i].rank = a[i - 1].rank;
    }

    sort(a, a + n, cmp2);
    for (int i = 0; i < n; i++)
        printf("%d ", a[i].rank);

    return 0;
}

B 三数之积

考点：

  • 枚举

题解：

根据题意，枚举每一种可能即可，注意循环的范围

AC Code

C

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5;

struct node
{
    int a, b, c;
} ans[N];
int cnt = 0;

void solve()
{
    cnt = 0;

    int n;
    scanf("%d", &n);

    for (int i = 1; i * i * i <= n; i++)
    {
        if (n % i != 0 || i % 3 == 0)
            continue;
        int t = n / i;
        for (int j = i + 1; j * j < t; j++)
        {
            if (t % j != 0 || j % 3 == 0 || t / j % 3 == 0)
                continue;

            ans[cnt].a = i;
            ans[cnt].b = j;
            ans[cnt].c = t / j;
            cnt++;
        }
    }

    if (cnt == 0)
        printf("NO\n");
    else
        printf("YES\n");

    for (int i = 0; i < cnt; i++)
        printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
        solve();

    return 0;
}

C++

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;
typedef long long ll;

struct node
{
    int a, b, c;
};

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

    vector<node> ans;
    for (int i = 1; i * i * i <= n; i++)
    {
        if (n % i != 0 || i % 3 == 0)
            continue;
        int t = n / i;
        for (int j = i + 1; j * j < t; j++)
        {
            if (t % j != 0 || j % 3 == 0 || t / j % 3 == 0)
                continue;

            ans.push_back({i, j, t / j});
        }
    }

    if (ans.empty())
        cout << "NO" << endl;
    else
        cout << "YES" << endl;

    for (auto it : ans)
        cout << it.a << ' ' << it.b << ' ' << it.c << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

C 消灭敌人

考点：

  • 枚举

题解：

在一条线上有若干敌人和若干炮台，求敌人离最近的炮台的最大值

AC Code

解法一 \(O(nm)\)：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4 + 10;

int a[N], b[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < m; i++)
        scanf("%d", &b[i]);

    sort(a, a + n);
    sort(b, b + m);

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int dis = 0x7fffffff;
        for (int j = 0; j < m; j++)
            dis = min(dis, abs(a[i] - b[j]));
        ans = max(ans, dis);
    }
    printf("%d", ans);

    return 0;
}

解法二 \(O(n\log n)\) ：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4 + 10;

int a[N], b[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < m; i++)
        scanf("%d", &b[i]);

    sort(a, a + n);
    sort(b, b + m);

    int ans = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        if (!j && a[i] <= b[j])
            ans = max(ans, abs(a[i] - b[j]));
        else if (j == m - 1)
            ans = max(ans, min(abs(a[i] - b[j - 1]), abs(a[i] - b[j])));
        else
        {
            while (j < m - 1 && b[j] < a[i])
                j++;

            ans = max(ans, min(abs(a[i] - b[j - 1]), abs(a[i] - b[j])));
        }
    }
    printf("%d", ans);

    return 0;
}

D 括号匹配

考点：

  • 字符串

题解：

用 \(cnt\) 计数，每出现左括号 \(cnt+1\) ，出现右括号 \(cnt-1\) 。如果出现中途 \(cnt<0\) 即括号不能匹配，最后判断括号是否匹配。

AC Code

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;
typedef long long ll;
const int N = 2e5 + 10;

char s[N];

int main()
{
    scanf("%s", s);
    int len = strlen(s), cnt = 0;
    for (int i = 0; i < len; i++)
    {
        if (s[i] == '(')
            cnt++;
        else
            cnt--;
        if (cnt < 0)
        {
            printf("NO");
            return 0;
        }
    }
    if (cnt == 0)
        printf("YES");
    else
        printf("NO");

    return 0;
}

E 求第k个数位

考点：

  • 字符串

题解：

将密码本先预处理好，每次直接查询即可

AC Code

C

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;
typedef long long ll;
const int N = 2e5 + 10;

char s[N], t[N];

int main()
{
    for (int i = 1; s[100000] == '\0'; i++)
    {
        itoa(i, t, 10);
        strcat(s, t);
    }

    int n;
    scanf("%d", &n);
    while (n--)
    {
        int x;
        scanf("%d", &x);
        printf("%c ", s[x - 1]);
    }

    return 0;
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    string s;
    for (int i = 1; s.size() < 100000; i++)
        s += to_string(i);

    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        cout << s[x - 1] << ' ';
    }

    return 0;
}

F 翻转单词

考点：

  • 字符串
  • 输入？

题解：

输入每个单词后倒序输出

AC Code

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

char s[N];

int main()
{
    int n = 0;
    while (scanf("%s", s) != EOF)
    {
        if (n)
            printf(" ");

        for (int i = strlen(s) - 1; i >= 0; i--)
            printf("%c", s[i]);

        n++;
    }

    return 0;
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    string s;
    int n = 0;
    while (cin >> s)
    {
        if (n)
            cout << ' ';

        reverse(s.begin(), s.end());
        cout << s;

        n++;
    }

    return 0;
}

G 求数组里的第二大数

考点：

  • 排序

题解：

如题，排序后输出数组里的第二大数即可

AC Code

C

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[i] < a[j])
            {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }

    int ans = -1;
    for (int i = 1; i < n; i++)
    {
        if (a[i] != a[i - 1])
        {
            ans = a[i];
            break;
        }
    }
    printf("%d", ans);

    return 0;
}

C++

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;
typedef long long ll;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a.begin(), a.end(), greater<int>());

    int ans = -1;
    for (int i = 1; i < n; i++)
    {
        if (a[i] != a[i - 1])
        {
            ans = a[i];
            break;
        }
    }
    cout << ans;

    return 0;
}

H A+B Problem

考点：

  • 排序

题解：

以十六进制输出 \(a+b\) 的结果

AC Code

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%x", a + b);

    return 0;
}

解法二：

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;
typedef long long ll;

char ans[10];

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);

    int c = a + b, cnt = 0;
    while (c)
    {
        if (c % 16 < 10)
            ans[cnt] = c % 16;
        else
            ans[cnt] = c % 16 - 10 + 'a';

        c /= 16;
        cnt++;
    }

    for (int i = cnt - 1; i >= 0; i--)
        printf("%c", ans[i]);

    return 0;
}
ACM > 题解 > SZTU_ACM
#算法 #SZTU_ACM
SZTU Monthly 2023 Oct.
http://xiaowhang.github.io/archives/471967587/
作者
Xiaowhang
发布于
2023年10月29日
许可协议