2025年香港城市大学（东莞）新生程序设计个人排位赛正式赛（同步赛） ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛 牛客竞赛OJ

F 优香数列

观察出来了，需要将公差为 1 的等差数列的和与 n 作比较，但是没有想出来要用二分答案。

  1. 答案有序
  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
27
28
29
30
31
32
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL t, n;

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

    cin >> t;

    while (t--)
    {
        cin >> n;

        LL l = 1, r = 10000000000;
        while (l < r)
        {
            LL mid = l + r >> 1;
            if (mid * (mid + 1) / 2 >= n)
                r = mid;
            else
                l = mid + 1;
        }
        cout << l << endl;
    }
    return 0;
}

H 课后补习

大模拟题，当时没做出来很亏。

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

using namespace std;

const int N = 1e5 + 10;

int t, n;
int a[N], b[N], c[N];
string s1, s2, s3;

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

    cin >> t;

    while (t--)
    {
        cin >> n;
        cin >> s1 >> s2 >> s3;

        for (int i = 1; i <= n; i++) 
            a[i] = s1[i - 1] - 48;
        for (int i = 1; i <= n; i++)
            b[i] = s2[i - 1] - 48;
        for (int i = 1; i <= n; i++)
            c[i] = s3[i - 1] - 48;

        int k[N];
        int vis[N] = {0};
        for (int i = 1; i <= n; i++)
            k[i] = a[i] + b[i] + c[i];

        int sum = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i == 1)
            {
                if (k[i] >= 2)
                {
                    sum++;
                    vis[i] = 1;
                }
            }
            else
            {
                if (k[i] == 3)
                {
                    sum++;
                    vis[i] = 1;
                }
                else if (k[i] == 2)
                {
                    if (k[i - 1] == 3 || k[i - 1] == 1)
                    {
                        sum++;
                        vis[i] = 1;
                    }
                    else
                    {
                        if (a[i] == a[i - 1] && b[i] == b[i - 1] && c[i] == c[i - 1])
                        {
                            if (vis[i - 1] == 0)
                            {
                                sum++;
                                vis[i] = 1;
                            }
                        }
                        else
                        {
                            sum++;
                            vis[i] = 1;
                        }
                    }
                }
            }
        }
        cout << sum << endl;
    }

    return 0;
}