情况

时间：2024年7月9日10:10
image.png

思路

A - Verify Password

题意

输入密码，字母后不能有数字，字母数字都分别非降序。

思路

实现题。

代码

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

const int N = 24;
void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    char a[N]; // number
    char b[N]; // digit
    a[0] = '0' - 1;
    b[0] = 'a' - 1;
    int aa = 1, bb = 1;
    bool flag = true;
    for (int i = 0; i < n; i++)
    {

        if (s[i] >= '0' && s[i] <= '9')
        {
            if (!flag)
            {
                cout << "NO\n";
                return;
            }
            a[aa] = s[i];
            if (a[aa] < a[aa - 1])
            {
                cout << "NO\n";
                return;
            }
            aa++;
        }
        else if (s[i] <= 'z' && s[i] >= 'a')
        {
            flag = false;

            b[bb] = s[i];
            if (b[bb] < b[bb - 1])
            {
                cout << "NO\n";
                return;
            }
            bb++;
        }
        else {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    return;
}

问题

实现的还是太慢了。
不要用isdigit，老老实实用ascii

B - Increase/Decrease/Copy

题意

两个数组a和b，b比a长一个
每次操作一个任意元素：a[i]–。a[i]++。将a中一个复制一个append末尾。
最少多少次能从a变成b

思路

贪心+实现。每一位置的a肯定要变成b，关键在最后那个元素应该什么时候给，记为last
遍历算出a和b各个位置差的绝对值之和，顺便：

  1. 只要last大小在a[i]和b[i]之间。那么a变成b的过程中就可以顺便把last给产生出来
  2. 如果不在，找一个离last最近的a[i]或b[i]。到时候移动其绝对值。

代码

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
void solve()
{
    int n;
    cin >> n;
    LL ans = 0;
    LL s = 2 * 10e9 + 1;
    vector<int> a(n, 0), b(n + 1, 0);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n + 1; ++i)
    {
        cin >> b[i];
        if (i < n)
            ans += abs(a[i] - b[i]);
    }
    LL last = b[n];
    bool flag = false;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] >= last && b[i] <= last)
        {
            flag = true;
            break;
        }
        else if (b[i] >= last && a[i] <= last)
        {
            flag = true;
            break;
        }
        else
        {
            s = min(s, min(abs(a[i] - last) ,  abs(b[i] - last)));
        }
    }
    if (flag)
    {
        cout << ans + 1 << "\n";
    }
    else
    {
        
        cout << ans + s +1<< "\n";
    }
}

问题

也实现慢了，主要就是没拿捏好该算什么的最小值

C - Job Interview

题意

n表示招收多少个programmer程序员，m表示招收多少个测试员。
有n+m+1个人面试，每个人有两个职位各自的能力值（不相等），按顺序录，只要那个位置没招满，就录能力大的一项。
算出只去掉每一个候选人，其他人面试结果（能力值之和）

思路

贪心。计算n+m的面试结果，记录什么时候哪个岗位满了（用来判断下面情况）。之后去掉某个人，判断：

  1. 如果去掉的人不是被迫进当前这个岗（pr/te)，那么找出后面第一个能力本该进这个岗但因为满员进了另一个的。那么最后一个人顺延进另一个，更新最终结果。
  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
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 200005;
int pr[N], te[N];
int zhiye[N];

void solve()
{
    int n, m;
    cin >> n >> m;
    int pr_cnt = 0, te_cnt = 0;
    int total = n + m + 1;
    int full_pr = 0, full_te = 0;
    bool isfull_pr = false, isfull_te = false;
    if (n == 0)
        isfull_pr = true;
    if (m == 0)
        isfull_te = true;
    LL as = 0;
    for (int i = 0; i < total; ++i)
    {
        cin >> pr[i];
    }
    for (int i = 0; i < total; ++i)
    {
        cin >> te[i];
    }
    for (int i = 0; i < total - 1; ++i)
    {
        if (pr[i] > te[i])
        {
            if (pr_cnt <= n && !isfull_pr)
            {
                as += pr[i];
                pr_cnt++;
                zhiye[i] = 0;
                if (pr_cnt == n)
                {
                    full_pr = i;
                    isfull_pr = true;
                }
            }
            else
            {
                as += te[i];

                te_cnt++;
                zhiye[i] = 1;
                if (te_cnt == m)
                {
                    full_te = i;
                    isfull_te = true;
                }
            }
        }
        else
        {
            if (te_cnt <= m && !isfull_te)
            {
                as += te[i];

                te_cnt++;
                zhiye[i] = 1;
                if (te_cnt == m)
                {
                    full_te = i;
                    isfull_te = true;
                }
            }
            else
            {
                as += pr[i];
                pr_cnt++;
                zhiye[i] = 0;
                if (pr_cnt == n)
                {
                    full_pr = i;
                    isfull_pr = true;
                }
            }
        }
    }
    for (int i = 0; i < total - 1; ++i)
    {
        bool flag2 = false;
        LL ans = as;
        if (zhiye[i] == 0)
        {
            ans -= pr[i];
            if (i > full_te)
            {
                ans += pr[total - 1];
            }
            else
            {
                for (int j = full_pr + 1; j < total - 1; j++)
                {
                    if (pr[j] > te[j])
                    {
                        ans = ans + pr[j] - te[j];
                        flag2 = true;
                        break;
                    }
                }
                if (flag2)
                {
                    ans += te[total - 1];
                }
                else
                {
                    ans += pr[total - 1];
                }
            }
        }
        else
        {
            ans -= te[i];
            if (i > full_pr)
            {
                ans += te[total - 1];
            }
            else
            {
                for (int j = full_te + 1; j < total - 1; j++)
                {
                    if (pr[j] < te[j])
                    {
                        ans = ans - pr[j] + te[j];
                        flag2 = true;
                        break;
                    }
                }
                if (flag2)
                {
                    ans += pr[total - 1];
                }
                else
                {
                    ans += te[total - 1];
                }
            }
        }

        cout << ans << ' ';
    }
    cout << as << endl;
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

问题

很气啊，思路其实都对的。刚开始开数组开麻烦了。后面又因为bool条件出错，最终快结束wa2。交赛后1分钟就改对了。