Blog

发表于 分类于 本文字数： 2.9k 阅读时长 ≈ 11 分钟

2025菜鸟杯部分题解

A - hello

题意：

第一行输出“HELL0 WUSTACM!”，第二行输出“maintain integrity,think diligently, and challenge yourself”。

代码：

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;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e7;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n;

void solve ()
{
    cout << "HELL0 WUSTACM!" << '\n';
    cout << "maintain integrity,think diligently, and challenge yourself" << '\n';
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

C - 杨弟的电梯

题意：

输入一个整数n和0或1，0代表夏天，1代表冬天。
夏天时人数不少于10人输出hot，不到10人输出cool。
冬天时人数不少于10人输出warm，不到10人输出cold。

代码：

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 ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e7;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n, a;

void solve ()
{
    cin >> n >> a;
    if (n > 15) {
        cout << "error" << '\n';
        return;
    }
    if (a == 0) {
        if (n < 10) {
            cout << "cool" << '\n';
        }else {
            cout << "hot" << '\n';
        }
    }else {
        if (n < 10) {
            cout << "cold" << '\n';
        }else {
            cout << "warm" << '\n';
        }
    }
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

F - 猫猫

题意：

根据程序输出，程序如下：

1
2
3
4
5
6
7
miao_func(x):
    miaomiao (x < 1)
        miaomiaomiaowu 0
    miaomiaomiao (x & 1)
        miaomiaomiaowu x + miao_func(x - 2)
    miaomiaomioa
        miaomiaomiaowu miao_func(x - 2) - x

喵语：
miaomiao : if
miaomiaomiao : else if
miaomiaomioa : else
miaomiaomiaowu : return

代码：

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 ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e7;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n;

void solve ()
{
    cin >> n;

    auto func = [&] (ll x, auto self) -> ll {
        if (x < 1) {
            return 0;
        }else if (x & 1) {
            return x + self(x - 2, self);
        }else {
            return self(x - 2, self) - x;
        }
    };

    ll ans = func(n, func);

    cout << ans << '\n';
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

D - 装糖果

题意：

给定n种类型的糖果，k和每种类型糖果的数量，求至少买多少个袋子能满足以下限制条件：

  • 每个袋子最多能装下k个糖果
  • 每个袋子中同一种类的糖果至多只能有一个

思路：

贪心。考虑最后的袋子有两种可能，一种是包含多种糖果，一种是只有一种糖果。对于第一种情况，至少的袋子数量即为ceil(sum / k),对于第二种情况，至少的袋子数量即为最大的糖果数量。两种情况取最大值即可。
时间复杂度：O(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
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e7;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n, k;

void solve ()
{
    cin >> n >> k;
    vector <ll> v(n + 1);
    ll mx = 0;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        sum += v[i];
        mx = max(mx, v[i]);
    }

    ll t;
    if (sum % k == 0) {
        t = sum / k;
    }else {
        t = sum / k + 1;
    }

    cout << max(t, mx);
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

G - 礼包和scandi

题意：

给定碗的数量和每个碗中的米饭量。scandi要吃完所有米饭且想要米饭量尽量少，礼包想要scandi吃的米饭量尽量多。在开始吃饭前，两人可以轮流对米饭量进行调整，礼包先手，过程如下：

  • 任选一个满足ai != ai+1的i。
  • 将ai变为func(ai，ai+1)。
  • 当无法找到满足要求的i时，调整环节结束。
    注意：对于scandi而言，func() = min()，对于礼包而言，func() = max()。

求最终scandi需要吃掉的米饭总量

思路：

诈骗题。手模样例后发现，当所有数等于最后一个数时才不会满足题意。直接输出即可。
时间复杂度：O(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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e7;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n;

void solve ()
{
    cin >> n;
    vector <ll> v(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    cout << v[n] * n << '\n';
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

H - 凡安要当超级农民

题意：

给定矩阵的长和宽为n和m，并给定次数q。接下来的q行中，给定魔法生效点座标，延伸长度和魔法效果。
魔法效果：在生效点上，上下左右依次延伸k个点，使得每个点的产量增加s(初始产量为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
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e7;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n, m, q;

void solve ()
{
    cin >> n >> m >> q;
    vector <vector <ll> > v(n + 1, vector <ll> (m + 1, 0));

    while (q--) {
        ll x, y, k, s;
        cin >> x >> y >> k >> s;
        v[x][y] += s;
        for (int i = x - k; i <= x + k; i++) {
            if (i == x) continue;
            ll xx = (i + n - 1) % n + 1;
            v[xx][y] += s;
        }
        for (int i = y - k; i <= y + k; i++) {
            if (i == y) continue;
            ll yy = (i + m - 1) % m + 1;
            v[x][yy] += s;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << v[i][j] << ' ';
        }
        cout << '\n';
    }
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

L - 逃课计划

题意：

一周七天，每天有六节课，给定老师的具体查课时间，即第几天第几节。在两天不能逃同一节课的情况下，求出可能的逃课计划数量。

思路：

最大可能不超过3e5种情况，因此直接暴力dfs即可。

代码：

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<ll, ll>;

#define fi first
#define se second

const ll MAXN = 1e7;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

vector <vector <ll> > e(8);
ll n;
ll ans = 0;

void solve ()
{
    cin >> n;
    map <pair<ll, ll>, bool> mp;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        mp[{a, b}] = true;
    }

    for (int i = 1; i <= 7; i++) {
        for (int j = 1; j <= 6; j++) {
            if (!mp[{i, j}]) {
                e[i].push_back(j);
            }
        }
    }

    auto dfs = [&] (ll day, ll course, auto self) -> void {
        if (day == 7) {
            ans++;
            return;
        }

        for (auto x : e[day + 1]) {
            if (x == course) continue;
            self(day + 1, x, self);
        }
    };

    for (auto x : e[1]) {
        dfs(1, x, dfs);
    }

    cout << ans << '\n';
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

E - 比较A和B的大小

题意：

给定一种新的比较两数大小的方式：整数部分相同，但小数部分按整数来比较大小。例如：0.13 > 0.3, 0.50 > 0.5。
给定两个数，若新的方式与数学方式的比大小结果相同，输出”ni shi dui de”
否则，输出”ni cuo le, ying gai shi ‘正确答案’”。 “正确答案”为：<, >, =。

思路：

首先注意到若存在一个数是整数，两种比大小的结果一定相同。接下来先判断整数部分，若整数部分不同，比大小结果一定也相同。若相同再来比较小数部分。
小数部分中，分别将其根据数学方法和新的方式比较（注意前导0和后导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
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<ll, ll>;

#define fi first
#define se second

const int MAXN = 6e7;
const double eps = 1e-5;
const ll mod = 998244353;
    
string a1, a2;

void solve ()
{
    cin >> a1 >> a2;
    if (a1.find('.') == string::npos || a2.find('.') == string::npos) {
        cout << "ni shi dui de" << '\n';
        return;
    }
    string s1 = a1.substr(0, a1.find('.'));
    string s2 = a2.substr(0, a2.find('.'));

    if (s1 != s2) {
        cout << "ni shi dui de" << '\n';
        return;
    }

    string ss1 = a1.substr(a1.find('.') + 1);
    string ss2 = a2.substr(a2.find('.') + 1);

    int found2 = 0;//normal compare
    for (int i = 0; i < min(ss1.size(), ss2.size()); i++) {
        if (ss1[i] < ss2[i]) {
            found2 = 1;
            break;
        }else if (ss1[i] > ss2[i]) {
            found2 = 2;
            break;
        }
    }

    if (found2 == 0) {
        if (ss1.size() < ss2.size()) {
            bool foundd = false;
            for (int i = ss1.size(); i < ss2.size(); i++) {
                if (ss2[i] != '0') {
                    foundd = true;
                }
            }
            if (foundd) {
                found2 = 1;
            }
        }else if (ss1.size() > ss2.size()) {
            bool foundd = false;
            for (int i = ss2.size(); i < ss1.size(); i++) {
                if (ss1[i] != '0') {
                    foundd = true;
                }
            }
            if (foundd) {
                found2 = 2;
            }
        }
    }

    int found3 = 0;//require compare
    string t1; int index = 0;//remove 0 from front
    while (index < ss1.size()) {
        if (ss1[index] != '0') {
            break;
        }
        index++;
    }
    t1 = ss1.substr(index, ss1.size() - index);

    string t2; index = 0;
    while (index < ss2.size()) {
        if (ss2[index] != '0') {
            break;
        }
        index++;
    }
    t2 = ss2.substr(index, ss2.size() - index);

    if (t1.size() < t2.size()) {
        found3 = 1;
    }else if (t1.size() > t2.size()) {
        found3 = 2;
    }else {
        for (int i = 0; i < t1.size(); i++) {
            if (t1[i] < t2[i]) {
                found3 = 1;
                break;
            }else if (t1[i] > t2[i]) {
                found3 = 2;
                break;
            }
        }
    }

    if (found2 == found3) {
        cout << "ni shi dui de" << '\n';
    }else if (found2 == 0 && found3 == 1) {
        cout << "ni cuo le, ying gai shi <" << '\n';
    }else if (found2 == 0 && found3 == 2) {
        cout << "ni cuo le, ying gai shi >" << '\n';
    }else if (found2 == 1 && found3 == 0) {
        cout << "ni cuo le, ying gai shi =" << '\n';
    }else if (found2 == 1 && found3 == 2) {
        cout << "ni cuo le, ying gai shi >" << '\n';
    }else if (found2 == 2 && found3 == 0) {
        cout << "ni cuo le, ying gai shi =" << '\n';
    }else if (found2 == 2 && found3 == 1) {
        cout << "ni cuo le, ying gai shi <" << '\n';
    }
}
 
int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

K - 小白的好数组

题意：

给定一个长度为n的数组，求至少需要进行多少次对一个数加p的操作，可以使得数组至少有k个数字相同。

思路:

首先可以知道，若两个数%p的结果相同，则两个数之间一定可以通过+p的形式边成一个数。若不同，则一定不行。
因此，可以根据此条件分成p个组，在每一组中排完序后，可能的最小的答案一定是连续的。因此，只需要以滑动窗口的形式来寻找答案即可。
时间复杂度：O(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
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<ll, ll>;

#define fi first
#define se second

const int MAXN = 6e7;
const double eps = 1e-5;
const ll mod = 998244353;
    
ll n, k, p;

void solve ()
{
    cin >> n >> k >> p;
    vector <vector <ll> > a(p);
    for (int i = 0; i < n; i++) {
        ll t;
        cin >> t;
        a[t % p].push_back(t);
    }

    bool found = false;
    ll ans = LLONG_MAX;
    for (int i = 0; i < p; i++) {
        if (a[i].size() < k) continue;
        else found = true;
        sort(a[i].begin(), a[i].end());

        ll mn = 0;
        for (int j = 0; j < k - 1; j++) {
            mn += (a[i][k - 1] - a[i][j]) / p;
        }

        ans = min(ans, mn);
        ll l = 1, r = k;
        while (r < a[i].size()) {
            mn -= (a[i][r - 1] - a[i][l - 1]) / p;
            mn += (a[i][r] - a[i][r - 1]) / p * (k - 1);
            ans = min(mn, ans);
            l++;
            r++;
        } 
    }

    if (!found) {
        cout << "wuwuwu" << '\n';
    }else {
        cout << ans << '\n';
    }
}
 
int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

B - 小李吃豆子

题意：

给定一个在1e12内的n，求有多少个连续的数列相加后等于n。

思路：

对于任意n，假设其连续数列为p，p + 1, p + 2,…, p + k - 1。对其求和后即可得到：(2p + k - 1) * k / 2 = n。化简后即为：p = (2n / k - k + 1) / 2。即一个符合要求的p，一定会满足以下两个条件：

  • 2n % k == 0
  • (2n / k - k + 1) % 2 == 0

因为范围为1e12，考虑优化。2n / k - k + 1 >= 0的条件为p >= sqrt(2n)，即只需遍历sqrt(2n)内的数即可。
时间复杂度：O(sqrt(2n))。

代码：

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

#define fi first
#define se second

const ll MAXN = 1e7;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n;

void solve ()
{
    cin >> n;
    ll m = sqrtl(2 * n);

    ll ans = 0;
    for (int i = 1; i <= m; i++) {
        if ((2 * n) % i == 0 && ((2 * n) / i - i + 1) % 2 == 0) {
            ans++;
        }
    }
    cout << ans << '\n';
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

I - 攻守兼备

题意：

给定n张卡牌，每张卡牌有攻击力和防御值。想要从这n张卡牌中找到两张卡，使得这两张卡的总攻击力和总防御力的最小值达到最大，输出总攻击力和总防御力的最小值的最大值。

思路：

这里采用贪心做法。具体思路见wustacm

代码：

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<ll, ll>;

#define fi first
#define se second

const ll MAXN = 1e7;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n;

void solve ()
{
    cin >> n;
    vector <pi> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].fi >> v[i].se;
    }
    sort(v.begin(), v.end(), [] (auto a1, auto b1) {
        return abs(a1.fi - a1.se) < abs(b1.fi - b1.se);
    });

    ll ans = 0, maxfi = 0, maxse = 0;
    for (int i = 0; i < n; i++) {
        if (v[i].fi > v[i].se) {
            ans = max(ans, maxse + v[i].se);
        }else {
            ans = max(ans, maxfi + v[i].fi);
        }
        maxfi = max(maxfi, v[i].fi);
        maxse = max(maxse, v[i].se);
    }

    cout << ans << '\n';
}

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

发表于 更新于 分类于 ， 本文字数： 3.9k 阅读时长 ≈ 14 分钟

华中农业大学第十五届程序设计竞赛（新生赛）游记及部分题解

仅以此记录我的第一次程序设计线下赛

游记

第一次线下赛，不出意料的感觉晚上没睡好，但到了比赛场地后就毫无疲惫感而言了。（瑞幸的新品是真难喝）

到场签到领了伴手礼，一个ACM的笔记本和一张明信片，虽然有点不及预期，但第一次拿到周边物件还是很兴奋的。在这里还是得感谢志愿者，赛前领的小纸条一下就弄丢了，上面的帐号密码志愿者们很热情地帮我解决了，非常感谢！另外赛前统一发的小熊猫dev还是很好用的，避免了用电脑自带的devc++，好评！

比赛开始后，很幸运地快速发现了签到题L，拿了一个一血！交完显示“correct”的时候发现自己是一血还是非常兴奋的！之后看了眼D题，发现跟热身赛的题差不多一样（其实并非），写完wa了之后，看到榜上有不少人也wa了D，就觉得有点不对劲了，仔细看题发现只能删除长度大于一的字串，找了下规律后又交了一发，wa了之后就没碰D题了(赛后题解显示是一道恐怖的分类讨论)。

接下来值得说的就是C题，赛时看出来是单调栈很兴奋，快速敲完交了一发wa后，由于没读清题意，自己一直在那乱改，交了无数发，最后十分钟实在没招了，而且此时也对题目思考地比较深入，再把第一发wa去掉特判后交了一发竟然A了(真的感受到了救赎感)，但是白白在这道题浪费了一个多小时，赛后看来很有可能可以再开一题，也是很可惜了。

另外，赛中发的午饭是一个“冷”热狗，鸡腿和两根香肠，难吃。

最后还是凭借7题获得了金牌，但以993的罚时在7题尾。就本次比赛来说，一定要想清楚题目再交，下次不能 “样例过了就AC” 了。


部分题解

L - 山海之约

题意：

给定两个非负整数 a 与 b，判断它们的和是否为神秘数字 350234。

代码：
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

void solve ()
{
	ll a, b;
	cin >> a >> b;
	if (a + b == 350234) {
            cout << "YES" << '\n';
	}else {
		cout << "NO" << '\n';
	}
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

H - 对决

题意：

给定两个字符串 s 与 t，记字串“fire”出现次数是a，“water”出现次数是b， “wind”出现次数是c，定义字符串的权值为a + b * c，判断s的权值是否严格大于t的权值。

思路：

简单遍历即可。
时间复杂度：O(n + m)。

代码：
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 ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n, m;

void solve ()
{
	string a = "fire";
	string b = "water";
	string c = "wind";
	cin >> n >> m;
	string s, t;
	cin >> s >> t;
	
	ll cnta = 0;
	ll cntb = 0;
	ll cntc = 0;
	for (int i = 0; i <= n - 4; i++) {
		if (s[i] == 'f' && s[i + 1] == 'i' && s[i + 2] == 'r' && s[i + 3] == 'e') {
			cnta++;
		}
		if (s[i] == 'w' && s[i + 1] == 'i' && s[i + 2] == 'n' && s[i + 3] == 'd') {
			cntc++;
		}
	}
	for (int i = 0; i <= n - 5; i++) {
		if (s[i] == 'w' && s[i + 1] == 'a' && s[i + 2] == 't' && s[i + 3] == 'e' && s[i + 4] == 'r') {
			cntb++;
		}
	}
	
	ll cntaa = 0;
	ll cntbb = 0;
	ll cntcc = 0;
	
	for (int i = 0; i <= m - 4; i++) {
		if (t[i] == 'f' && t[i + 1] == 'i' && t[i + 2] == 'r' && t[i + 3] == 'e') {
			cntaa++;
		}
		if (t[i] == 'w' && t[i + 1] == 'i' && t[i + 2] == 'n' && t[i + 3] == 'd') {
			cntcc++;
		}
	}
	for (int i = 0; i <= m - 5; i++) {
		if (t[i] == 'w' && t[i + 1] == 'a' && t[i + 2] == 't' && t[i + 3] == 'e' && t[i + 4] == 'r') {
			cntbb++;
		}
	}
	
	if (cnta + cntb * cntc > cntaa + cntbb * cntcc) {
		cout << "YES" << '\n';
	}else {
		cout << "NO" << '\n';
	}
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

I - 学霸题

题意

给定三个点 A, B, C，找出一个点D使得这 4 个点可以连成一个平行四边形。

思路

确定两个点，求出两点间x和y座标的变化后根据第三个点推出第四个点的位置。
时间复杂度：O(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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

void solve ()
{
	ll x1, y1, x2, y2, x3, y3;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
	ll tx = x2 - x1;
	ll ty = y2 - y1;
	ll x4 = x3 + tx;
	ll y4 = y3 + ty;
	cout << x4 << ' ' << y4 << '\n';
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

B - 爱的魔法

题意

给定一个序列，对于序列中的每一个数，交换至多两个数位，最大化操作后的序列和。

思路

数据范围不是很大，直接对每一个数简单遍历，取每个数的最大值即可。
时间复杂度：O(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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n;

void solve ()
{
	cin >> n;
	vector <ll> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	
	for (int i = 0; i < n; i++) {
		string s = to_string(v[i]);
		for (int k = 0; k < (ll)s.size(); k++) {
			ll t = s[k] - '0';
			ll pos = k;
			for (ll j = k + 1; j < (ll)s.size(); j++) {
				ll a = s[j] - '0';
				if (a >= t) {
					t = a;
					pos = j;				
				}
			}
			if (pos != k && s[pos] > s[k]) {
				swap(s[pos], s[k]);
				break;
			}
		}
		v[i] = stoll(s);
	}
	
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		ans += v[i];
	}
	
	cout << ans << '\n';
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

A - 矩形游戏

题意

给定一个单调不降的序列[b1, b2, … bn]与一个k行n列的矩阵A。签到哥从矩阵的第一行第一列移动到第k行的任意一列。签到哥位于(i, j)时可以移动到(i + 1, j - 1)或(i + 1, j)或(i + 1, j + 1)。签到哥只能移动到大于等于自己的位置，且移动后签到哥的体力也会相应增加。

求签到哥到达第k行的体力最大值

思路

由于序列单调不降，只需尽量往右走就行。另外，由于k是1e9级别，而n是2e5级别，最后如果到最后一列可以直接退出单独计算。
时间复杂度：O(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
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll k, n;

void solve ()
{
	cin >> k >> n;
	vector <ll> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	
	ll sum = 0;
	ll j = 0;
	ll t = 0;
	for (int i = 0; i < k; i++) {
		if (sum >= v[j + 1] && j < n - 1) {
			j++;
		}
		sum += v[j];
		if (j == n - 1) {
			t = k - i - 1;
			break;
		}
	}
	
	sum += max(0LL, t) * v[n - 1];
	cout << sum << '\n';
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

M - 终极考验

题意

给定n个石柱高度，耗费一点能量可以使任意一个i至min(i + x - 1, n)区间内的所有石柱升高1米。

求使得石柱的高度单调不降所要耗费能量的最小值。

思路

这里给出一个另类的思路。对于任意一个vi，在（i - x + 1， i）这个区间内若存在vy需要增加，则vi一定会与vy增加相同次数。因此，在维护好一个差分数组后，我们可以考虑对于任意一个di，加上需要做区间加且区间加触及不到di的合法的di - x，最后加上所有小于0的d[i]的绝对值即可
时间复杂度：O(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
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

void solve ()
{
	ll n, x;
	cin >> n >> x;
	vector <ll> v(n + 1, 0);
	vector <ll> d(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		d[i] = v[i] - v[i - 1];
	}
	
	for (int i = x + 1; i <= n; i++) {
		if (d[i - x] < 0) {
			d[i] += d[i - x];
		}
	}
	
	ll ans = 0;
	for (int i = 2; i <= n; i++) {
		if (d[i] < 0) {
			ans += abs(d[i]);
		}
	}
	
	cout << ans << '\n';
	
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

C - 小W的计数题

题意

对于给出的每一个ai，找到元素数量最多的集合Sx, 其中对于任意的y∈S，使得[amin{x,y}, …, amax{x,y}]的最大值为ay。

思路

题意很复杂，简要地说，这一题实际上是想要找到对于每一个ai向左的单调递增区间和向右的单调递增区间的长度之和。
由此，不难想到可以利用单调栈来解决问题。可以维护从前往后的一个单调递减栈和从后往前的维护一个单调递减栈，在每一位加上栈的大小，重复两遍即是最终结果。
时间复杂度：O(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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n;

void solve ()
{
	cin >> n;
	vector <ll> v(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	
	vector <ll> ans(n + 1, 0);
	stack <ll> stk;
	
	for (int i = 1; i <= n; i++) {
		while (!stk.empty() && v[i] > stk.top()) {
			stk.pop();
		}
		stk.push(v[i]);
		ans[i] += stk.size();
	}
	
	stack <ll> stk1;
	
	for (int i = n; i >= 1; i--) {
		while (!stk1.empty() && v[i] > stk1.top()) {
			stk1.pop();
		}
		stk1.push(v[i]);
		ans[i] += stk1.size();
	}
	
	for (int i = 1; i <= n; i++) {
        cout << ans[i] - 1 << ' ';
	}
	cout << '\n';
	
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

G - 二分图判定

题意

给定一个序列[a1, a2, … an]和一个正整数k, 在一张包含n个点的图上，第i个点的权值为i，对于合法的任意两点i，j，若 |ai - aj| > k，就在i与j两点之间连接一条无向边。

求出最小的非负整数k，使得按照上述方法生成的图是二分图。

思路

读完题后不难发现，该题的目的是在给定的an序列中，将其分为两个集合，并最小化两个集合的极差的最大值。

不难想到可以利用二分答案的方法来解决这道题, 可以先对an序列进行排序，再以答案进行从前到后和从后到前的check，最后若r <= l + 1则说明check成功。
时间复杂度：O(nlogn)。

代码
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 998244353;

ll n;

void solve ()
{
    cin >> n;
    vector <ll> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    sort(v.begin() + 1, v.end());

    auto check = [&] (ll md) -> bool {
        ll l = 1;
        for (int i = 1; i <= n; i++) {
            if (v[i] - v[1] <= md) {
                l = i;
            }else {
                break;
            } 
        }
        ll r = n;
        for (int i = n - 1; i >= 1; i--) {
            if (v[n] - v[i] <= md) {
                r = i;
            }else {
                break;
            }
        }
        return r <= l + 1;
    };

    ll l = 0, r = v[n]; 
    while (l <= r) {
        ll mid = l + ((r - l) >> 1);
        if (check(mid)) {
            r = mid - 1;
        }else {
            l = mid + 1;
        }
    }
    cout << l << '\n';
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

J - 鱼骨挖矿法

题意

给定一个n行m列的二位网格，每个格子的数字代表当前格的矿物价值。首先钒钒会选择第i行作为主矿道，并将主矿道上方和下方的矿道的所有矿物全部采集。再以主矿道为中心，在每个满足j === 2 (mod 3)的j列（分矿道）分别向上向下挖，在挖到第一个矿物时停止挖掘。

挖掘规则：

  • 如果在一次挖掘操作中发现多个矿物，钒钒会将这些矿物同时挖掘。
  • 如果在当前分矿道上挖掘到矿物，钒钒会立即停止挖掘
  • 上下分矿道的挖掘情况相互独立，即：上分矿道的挖掘情况不会影响到下分矿道的挖掘情况。

求在以第i行为主矿道时(1 <= i <= n)， 所能挖到的矿物的总价值。

思路

首先，对于每一个主矿道来说，我们可以预处理每一个主矿道的结果。而对于每一个分矿道来说，对于向上的分矿道，我们可以预处理出到每一格时所能挖到的矿物价值，即sup[i][j] = v[i][j] + v[i - 1][j] + v[i][j - 1] + v[i][j + 1]。若sup[i][j] != 0，则up[i][j] = sup[i][j]，否则up[i][j] = up[i - 1][j]。向下的分矿道也是类似的。在每个i行，只需要加上所有合法的up[i - 2][j]和dw[i + 2][j]即可。
时间复杂度：O(n * m)。

代码
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 1e9 + 7;

ll n, m;

void solve ()
{
	cin >> n >> m;
    vector <vector <ll> > v(n + 3, vector <ll> (m + 3));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> v[i][j];
        }
    }

    vector <ll> ss(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ss[i] += v[i][j];
        }
    }

    vector <ll> s(n + 2, 0);//主矿道
    for (int i = 1; i <= n; i++) {
        s[i] = ss[i - 1] + ss[i] + ss[i + 1];
    }

    vector <vector <ll> > sa(n + 2, vector <ll> (m + 2));//上部分矿道
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sa[i][j] = v[i][j] + v[i - 1][j] + v[i][j - 1] + v[i][j + 1];
        }
    }
    vector <vector <ll> > up(n + 2, vector <ll> (m + 2)); 
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (sa[i][j] != 0) {
                up[i][j] = sa[i][j];
            }else {
                up[i][j] = up[i - 1][j];
            }
        }
    }

    vector <vector <ll> > sb(n + 2, vector <ll> (m + 2));//下部分矿道
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sb[i][j] = v[i][j] + v[i + 1][j] + v[i][j - 1] + v[i][j + 1];
        }
    }
    vector <vector <ll> > dw(n + 2, vector <ll> (m + 2)); 
    for (int j = 1; j <= m; j++) {
        for (int i = n; i >= 1; i--) {
            if (sb[i][j] != 0) {
                dw[i][j] = sb[i][j];
            }else {
                dw[i][j] = dw[i + 1][j];
            }
        }
    }

    vector <ll> ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (i == 1) {
            ans[i] += s[i];
            if (n <= 2) continue;
            for (int j = 2; j <= m; j += 3) {
                ans[i] += dw[i + 2][j];
            }
        }else if (i == n) {
            ans[i] += s[n];
            if (n <= 2) continue;
            for (int j = 2; j <= m; j += 3) {
                ans[i] += up[i - 2][j];
            }
        }else {
            ans[i] += s[i];
            if (n <= 2) continue;
            for (int j = 2; j <= m; j += 3) {
                ans[i] += up[i - 2][j] + dw[i + 2][j];
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

K - 大师和他的领域

题意

给定一个数组a和值k，求有多少个区间满足以下要求：

  • 区间中必须包含值k
  • 区间中大于k值的数量必须等于小于k值的数量
思路

我们可以令大于k的值为1，小于k的值为-1，等于k的值为0。维护一个前缀和数组。对于每一个的下标，都往前二分查找相同值且包含值k的最大左边界即可。
时间复杂度：O(nlogn)。

代码
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second

const ll MAXN = 1e8;
const ld eps = 1e-12;
const ll mod = 998244353;

ll n, k;
string s;

void solve ()
{
	cin >> n >> k;
    vector <ll> v(n + 1);   
    
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    vector <ll> s(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1];
        if (v[i] > k) {
            s[i]++;
        }else if (v[i] < k) {
            s[i]--;
        }
    }

    vector <vector<ll> > pos(2 * n + 2);
    pos[n].push_back(0);
    ll ans = 0; 
    ll exist = -1;

    for (int i = 1; i <= n; i++) {
        pos[s[i] + n].push_back(i);
        if (v[i] == k) {
            exist = i;
        }
        if (exist != -1) {
            ans += lower_bound(pos[s[i] + n].begin(), pos[s[i] + n].end(), exist) - pos[s[i] + n].begin();
        }
    }
    cout << ans << '\n';

}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

发表于 更新于 分类于 本文字数： 515 阅读时长 ≈ 2 分钟

CS50入门教程

预先准备

首先，在开始之前，面对全英文的cs50网站，准备一个浏览器的翻译插件是必要的。这里推荐根据AI翻译插件配置教程 | scandi-blog来设置。若不想太麻烦，可以先选择有道灵动翻译插件先体验，在之后如果感觉翻译的晦涩难懂，跟原文有偏差，可以再使用AI翻译插件。

其次，由于众所周知的原因，梯子的准备会让学习的过程更加顺畅。

另外，也需要注册一个github账号，并提前在电脑上安装VSCode。

关于CS50的环境配置

CS50的学习主要分为看课程和提交作业两大项。关于课程的观看，可以直接在B站搜索CS50的相关课程资源来学习。观看一节课程，提交一节作业。

提交作业即需要配置相关的环境了。再点击进入csdiy中的2025年课程后，下滑左侧栏，找到Week 1 C，点击进入。

点开后，下滑右侧栏至底部，找到Problem Set 1（作业集1）。

点击进入后，便可看到配置环境的一些步骤。

首先进行步骤一，点开链接后，点击Authorize cs50（授权cs50）后，可退回进行步骤2。

进入cs50.dev后，使用github账号log in后，便可看到网页版的VSCode。

但是在这个网页上做CS50的作业是非常卡顿的。若将其连接到本地VSCode，卡顿的情况将会大大改善。

将 CS50 网页端的 VSCode 环境连接到本地 VSCode

打开电脑中下载的VSCode软件，安装GitHub Codespaces扩展，成功后会发现左侧栏出现新标识（远程资源管理器），点击进入，并登录github账号，便可将网页端的VSCode连接到本地，此后可以愉快的在本地写CS50的作业啦！前提是每次连接前需要进入(cs50.dev)打开网页端。

祝大家学习愉快！

0%