相关链接

随着阵阵花香，Debug杯来啦||计算机学院Debug杯程序设计大赛如期而至

呼~ 烧了我一下午脑细胞的比赛终于结束了

真的是累死了，比完之后眼睛痛，头也晕，腰也酸，关键是好好的睡午觉的时候要去比赛，简直要了我的命

来，来听我讲讲我今天的心路历程

中午出发前往赛场

时间来到 1:30 ，进入比赛，开始做题

T1

首先是第一题

一看就是纸老虎，前面大段大段的都是唬你的废话，直接找因子然后套公式就行了

因为找一个数的因子应该比较简单，所以我打算交给 Copliot 做，注释一写出来，代码直接就生成了，简直不要太爽

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
//
int g(ll x)
{
    if (x == 1)
        return 1;
    else
        return 0;
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    //求一个数的所有因子
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        ll n,sum=0;
        cin >> n;
        vector<ll> factors;
        for (ll i = 1; i <= sqrt(n); i++)
        {
            if (n % i == 0)
            {
                factors.push_back(i);
                if (i != n / i)
                    factors.push_back(n / i);
            }
        }
        //sort(factors.begin(), factors.end());
        // for (ll i = 0; i < factors.size(); i++)
        // {
        //     cout<<factors[i]<<" ";
        // }
        // cout<<endl;
        // for (ll i = 0; i < factors.size(); i++)
        // {
        //     //cout<<factors[i]<<" "<<n/factors[i]<<endl;
        //     // cout<<factors[i]<<endl;
        //     // cout<<g(n/factors[i])<<endl;
        //     // cout<<g(factors[i])<<endl;

        //     cout<<factors[i]*g(n/factors[i])<<endl;
        // }

        for (ll i = 0; i < factors.size(); i++)
        {
            sum+=factors[i]*g(n/factors[i]);
        }
        cout<< sum ;
         cout <<endl;
    }
}

赶紧 A 了直接下一题

T2

这道题和上一题一样是很水的，按照贪心直接排序即可，担心数据量有点大，就上了快读和 long long

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
#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll a[N];
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ll t = read();
    while (t--)
    {
        ll n, k, flag = 0;
        cin >> n >> k;
        for (ll i = 1; i <= n; i++)
            a[i] = read();

        sort(a + 1, a + n + 1);
        if (a[1] > k)
        {
            cout << "-1" << endl;
            continue;
        }
        if (a[1] == 0)
        {
            cout << n<<endl;
            continue;
        }
        ll ans = a[1];
        for (int i = 2; i <= n; i++)
        {
            ans *= a[i];
            if (ans > k)
            {
                cout << i - 1;
                flag = 1;
                break;
            }
        }
        if (!flag)
            cout << n;
        cout<<endl;
    }
}

T3

这道题居然比前面的还简单，也是一道简单的贪心 （怎么一道题比一道题水）

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>
#define ll long long
#define N 100005
using namespace std;
ll a[N];
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        if(n==1)
        {
            cout<<a[1]<<endl;
            continue;
        }
        cout << a[n] + a[n - 1]<<endl;
    }
}

T4

最小值最大，经典的二分答案模板题，套个板子手写一下 check() 函数即可

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
#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll e, m, h;
bool check(int x)
{
    if ((e >= x * 5 && m >= x * 3))return 1;
    else return 0;
}
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ll t;
    cin >> t;
    while (t--)
    {
        cin >> e >> m >> h;
        int ans = bsearch_2(0, h);
        cout << ans << endl;

    //     cin >> e >> m >> h;
    //     while (1)
    //     {
    //         if ((e >= h * 5 && m >= h * 3)&&(e >= (h+1) * 5 && m >= (h+1) * 3))
    //         {
    //             cout << h << endl;
    //             break;
    //         }
    //         h/2;
    //         while((e >= h * 5 && m >= h * 3))h=h+h/2;
    //     }
     }
}

T5

经典的高精度取模，直接板子拿过来即可

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <bits/stdc++.h>
#define ll long long
#define len(k) (k[0])
using namespace std;
const int MAXN = 100000;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN], tmp[MAXN];
int num, res;
void scan(int x[])
{
    char str[MAXN];
    scanf("%s", &str);
    len(x) = strlen(str);
    for (int i = 0; i < len(x); i++)
        x[len(x) - i] = str[i] - '0';
}

void print(int x[])
{
    if (len(x) == 0)
    {
        printf("0\n");
        return;
    }
    for (int i = len(x); i >= 1; i--)
        printf("%d", x[i]);
    putchar('\n');
}

void init(int x[])
{
    memset(x, 0, MAXN * sizeof(int));
}

void copy(int a[], int b[], int pos)
{
    for (int i = 1; i <= len(a); i++)
        b[i + pos - 1] = a[i];
    len(b) = len(a) + pos - 1;
}

int compare(int x[], int y[])
{
    if (len(x) > len(y)) return 1;
    if (len(x) < len(y)) return -1;
    for (int i = len(x); i >= 1; i--)
    {
        if (x[i] > y[i]) return 1;
        if (x[i] < y[i]) return -1;
    }
    return 0;
}

void add(int a[], int b[], int c[])
{
    len(c) = max(len(a), len(b));
    for (int i = 1; i <= len(c); i++)
    {
        c[i] += a[i] + b[i];
        c[i + 1] = c[i] / 10;
        c[i] %= 10;
    }
    while (c[len(c) + 1])
        len(c)++;
}

void minu(int a[], int b[], int c[])
{
    len(c) = max(len(a), len(b));
    for (int i = 1; i <= len(c); i++)
    {
        c[i] += a[i] - b[i];
        if (c[i] < 0)
        {
            c[i + 1]--;
            c[i] += 10;
        }
    }
    while (c[len(c)] == 0 && len(c) > 1)
        len(c)--;
}

void selfminu(int a[], int b[])
{
    for (int i = 1; i <= len(a); i++)
    {
        if (a[i] < b[i])
        {
            a[i + 1]--;
            a[i] += 10;
        }
        a[i] -= b[i];
    }
    while (len(a) > 0 && a[len(a)] == 0)
        len(a)--;
}

void mult(int a[], int b[], int c[])
{
    len(c) = len(a) + len(b);
    for (int i = 1; i <= len(a); i++)
        for (int j = 1; j <= len(b); j++)
            c[i + j - 1] += a[i] * b[j];
    for (int i = 1; i <= len(c); i++)
        if (c[i] > 9)
        {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    while (c[len(c)] == 0 && len(c) > 1)
        len(c)--;
}

void divi(int a[], int b[], int c[], int d[])
{
    len(c) = len(a) - len(b) + 1;
    copy(a, d, 1);
    for (int i = len(c); i > 0; i--)
    {
        init(tmp);
        copy(b, tmp, i);
        while (compare(d, tmp) >= 0)
        {
            c[i]++;
            selfminu(d, tmp);
        }
    }
    while (len(c) > 0 && c[len(c)] == 0)
        len(c)--;
}

void selfDiviByLow(int a[], int b,int* res)
{
    int c[MAXN]={0};
    len(c)=len(a);
    while (a[len(c)] < b)
    {
        a[len(c) - 1] += a[len(c)] * 10;
        a[len(c)] = 0;
        len(c)--;
    }
    for (int i = len(c); i >= 1; i--)
    {
        if (a[i] >= b)
        {
            c[i] = a[i] / b;
            a[i] %= b;
        }
        a[i - 1] += a[i] * 10;
    }
    *res=a[1];
    copy(c,a,1);
}

int main()
{
    scan(a);
    scan(b);
    divi(a, b, c, d);
    print(d);

    // scan(a);
    // scan(b);
    // scanf("%d", &num);

    // add(a, b, c);
    // print(c);
    // init(c);

    // if (compare(a, b) == -1)
    // {
    //     printf("-");
    //     minu(b, a, c);
    // }
    // else minu(a, b, c);
    // print(c);
    // init(c);

    // mult(a, b, c);
    // print(c);
    // init(c);

    // divi(a, b, c, d);
    // print(c);
    // print(d);

    // selfDiviByLow(a,num,&res);
    // print(a);
    // printf("%d",res);
}

T6

开始有点难度了，这道题首先有个坑点，就是 long long ，我后面折腾了很久才发现有个 int 忘记改成 long long 了，导致我一直过不了

然后这道题的难度自然是 check() 函数，其实还是不难理解的：首先 k 的搜索范围自然是 H + mOrH ，然后就要看 mOrH 中，到底分了多少给 H ，确定之后把剩下的分给 M ，接着如果 M 还是够不着 k*3 的话要把 eOrM 中的部分分给 M ，剩下的分给 E ，如果够分的话那就 return 1 ，不够分自然就 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
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
#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll E, M, H, eOrM, mOrH;

inline bool check(ll x)
{
    ll e=E,m=M,h=H;
    if ((e >= x * 5 && m >= x * 3))
        return 1;
    if (e + eOrM < x * 5)
        return 0;
    if (m + mOrH + eOrM < x * 3)
        return 0;

    ll mOrHGiveToH, eOrMGiveToM;
    if (x > h)
    {
        mOrHGiveToH = x - h;
        m += mOrH - mOrHGiveToH;
    }
    else
    {
        mOrHGiveToH = 0;
        m += mOrH;
    }
    if (m + eOrM < x * 3)
        return 0;
    if (m < x * 3)
    {
        eOrMGiveToM = x * 3 - m;
        m += eOrMGiveToM;
        e += eOrM - eOrMGiveToM;
    }
    else
    {
        eOrMGiveToM = 0;
        e += eOrM;
    }
    if ((e >= x * 5 && m >= x * 3))
        return 1;

    return 0;
}
inline ll bsearch_2(ll l, ll r)
{
    while (l < r)
    {
        ll mid = l + r + 1 >> 1;
        //cout<<mid<<endl;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}
inline ll read()
{
    ll s = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll t;
    cin >> t;
    while (t--)
    {
        // cin >> e >> m >> h >> eOrM >> mOrH;
        E = read();
        eOrM = read();
        M = read();
        mOrH = read();
        H = read();


        ll ans = bsearch_2(0, H + mOrH);
        cout << ans << endl;

        //     cin >> e >> m >> h;
        //     while (1)
        //     {
        //         if ((e >= h * 5 && m >= h * 3)&&(e >= (h+1) * 5 && m >= (h+1) * 3))
        //         {
        //             cout << h << endl;
        //             break;
        //         }
        //         h/2;
        //         while((e >= h * 5 && m >= h * 3))h=h+h/2;
        //     }
    }
}

T7

很遗憾，这道题我最后没 A 掉，看上去可能是用 DP 做的，但是我 DP 学的本来就差，但是我后面一想也不能用DP做呀，就只能照着题目的意思乱写，最后死活 TLE，没办法，人菜还得好好学习

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
#include <bits/stdc++.h>
#define ll long long
#define N 1024
using namespace std;
ll x[N], y[N];
ll n;
ll Myabs(ll a) {
    return a < 0 ? -a : a;
}
inline ll read()
{
    ll s = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s;
}
inline ll sumWork(ll pos)
{
    ll sum = 0;
    for (ll i = 0; i < n; i++)
    {
        sum += Myabs(x[i] - pos) * y[i];
    }
    return sum;
}
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ll t = read();
    while (t--)
    {
        ll Sx = 0;
        n = read();
        for (ll i = 0; i < n; i++)
        {
            x[i] = read();
            Sx += x[i];
            y[i] = read();
        }
        printf("%d\n", sumWork(Sx / n));
        // cout << sumWork(Sx / n)<<endl;
    }
}

T8

突如其来的一道水题，也不知道为什么放这

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ll k;
    cin >> k;
    while (k--)
    {
        ll l, r, t;
        cin >> l >> r >> t;
        cout << l + t % abs(r - l + 1) << endl;
    }
}

T9

最后一题，看上去是一道很简单的搜索，但是最后还是死活 TLE ，怎么剪枝都没用

我在 copilot 的配合下很快写了个 DFS 出来，然后又是 MLE 又是 TLE 的，我心态都崩了，因为 MLE 我甚至还想重新写一个 BFS 版本的，但是做到这里我早已疲惫不堪，最后只能遗憾离场

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>
#define ll long long
#define N 1001
#define INF 0x3f3f
using namespace std;
short Move[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
short a[N][N], b[N][N], X, Y, Ax, Ay, Bx, By;
bool Map[N][N];
inline short min(short x, short y) { return x < y ? x : y; }

void staus(short x, short y, short hack, short step)
{
    if (x == Bx && y == By)
    {
        a[x][y] = min(hack, a[x][y]);
        return;
    }
    if (hack >= a[x][y])
        return;
    else
        a[x][y] = hack;
    if (step >= b[x][y])
        return;
    else
        b[x][y] = step;
    for (short i = 0; i < 4; i++)
    {
        short nx = x + Move[i][0], ny = y + Move[i][1];
        if (nx < 0 || nx >= X || ny < 0 || ny >= Y)
            continue;
        if (Map[nx][ny])
            continue;
        staus(nx, ny, hack, step + 1);
    }
    for (short dx = -2; dx <= 2; dx++)
    {
        for (short dy = -2; dy <= 2; dy++)
        {
            if ((dx == 0 && dy == 0) || (dx == 1 && dy == 0) || (dx == -1 && dy == 0) || (dx == 0 && dy == 1) || (dx == 0 && dy == -1))
                continue;
            short nx = x + dx, ny = y + dy;
            if (nx < 0 || nx >= X || ny < 0 || ny >= Y)
                continue;
            if (Map[nx][ny])
                continue;
            staus(nx, ny, hack + 1, step);
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    short n;
    cin >> n;
    while (n--)
    {

        cin >> X >> Y >> Ax >> Ay >> Bx >> By;
        Ax--;
        Ay--;
        Bx--;
        By--;
        for (short i = 0; i < X; i++)
        {
            for (short j = 0; j < Y; j++)
            {
                a[i][j] = INF;
                b[i][j] = INF;
                char tmp;
                cin >> tmp;
                if (tmp == '.')
                    Map[i][j] = 0;
                else
                    Map[i][j] = 1;
            }
        }

        staus(Ax, Ay, 0, 0);
        cout << a[Bx][By] << endl;
    }
}

成果 & 照片

比赛最后的截图（我记得最高好像冲到了13名，然后死磕最后一题狂加时间加到了17名😿）：

最后关头还在死磕的 NX

快结束时拍的一张照，人基本都跑光了（投影上轮流翻看所有考场中的排名，我在这个房间是第一）

赛后纪念品，最后插了 7 个葫芦娃（类 ACM 赛制，做对一题给你插一个）

最后拿了几等奖等正式宣布，不着急

2022年5月18日 更新

这比赛最后发放了答案，T7 有一个重要信息我没看出来，那就是答案所求的坐标必定落在某个朋友所在的位置（我还是太菜），而最后一题用的是双端队列+BFS，没有复习高中的知识，没办法

讲真

至于最后的奖项嘛…正好卡在一等的最后一名（

其实也没什么好吹嘘的，这题真的很简单，我没有全A掉都已经是很丢脸的事情了，这个比赛基本上没有什么含金量，只能说是练练手吧

img