785快速排序

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 <iostream>
using namespace std;
const int N = 1e6 + 10	;//一后面6个零,应该是1e6 + 10
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    // 注意快速排序这道题目的数据已加强，划分中点取左端点或右端点时会超时，改成取中点或者随机值即可。
    //  每次交换玩指针都要往中间移动一格,
    //  因此后面循环是这样做的,
    //  每次不管三七二十一,
    //  先把指针往中间移动一格,
    //  然后再去判断,因此两个指针都要放在左右两个边界的左右一格,
    //  这样我们往中间移动一格之后才是真正的边界
    //  所以才有一个偏移量,需要往两边扩一格
    //  int x = q[(l + r) / 2];
    //  int x = q[r];
    while (i < j)
    {
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (x < q[j]);
        if (i < j)
            swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);
    return 0;
}

第一步是判断边界,如果区间里面只有一个数或者没有数的话,我们就直接return;事实上也就是递归结束的条件.

第二步是while(i < j)循环执行,每一次i,j移动和swap(q[i], q[j])算一次.

找到第一个令q[i] >= x的i,找到第一个令q[j] <= x的j,两个指针只要没有相遇(就是i >= j)的话,就交换(所以才会在swap前面加一个if语句,如果i >=j,i和j相遇了,那就不swap,同时交给下一轮的while(i<j) 来退出循环)

如果你的语言里面没有swap函数,就用

1
2
3
4
5
if(i < j){
int t  = q[i] ;
q[i]  = q[j] ;
q[j] = t ;
}

为什么边界写成下面这样呢?

1
2
quick_sort(q, l, j);
quick_sort(q, j + 1 , r);

图示:

红剪头是指针i,绿箭头是指针j

image-20241103084313121

while(i < j)这个循环结束时候,i肯定是>=j的,同时i(不包括i)的前面都是<=x的数,同时j(不包括j)的后面都是=>x的数

(根据这个结束的状态我个人认为可以判断while(i < j) 循环结束时只有两种情况:一是i == j,二是 i > j,更加具体的说,二是i > j的i和j 的中间都是等于x 的数,因此你用

1
2
quick_sort(q, l, j);
quick_sort(q, j + 1, r);

或者

1
2
quick_sort(q, l, i - 1);
quick_sort(q, i, r);

无非是i和j中间可能存在的若干个和x相同的数划分到左区间还是右区间的问题,但是无论是左区间还是右区间,都在左区间的最右段,右区间的最左段.还是不影响快排的正确性.

).可以见下面的图;

红剪头是指针i,绿箭头是指针j

不包括i指针前面所有的数都是<=x的,不包括j指针后面所有的数都是>=x的

image-20241103090100453

所以根据这个图示,边界是这样的.

1
2
quick_sort(q, l, j);
quick_sort(q, j + 1, r);

下面这段可以把j换成i,只要满足对称就行了,根据图示来

1
2
quick_sort(q, l, i - 1);
quick_sort(q, i, r);

==但用i的话绝对不能写成int x = q[l]==,会有边界问题,用int x = q[r]或者int x = q[(l + r + 1) / 2],要向上取整,一定不能取到l这个边界上面.不然会有边界问题,会有死循环.

(举个具体的例子

对于 n = 2, 输入的数字为 1 2这种情况来说,就会死循环

while(i < j)结束时,i = 0, j = 0

quick_sort(q, l, i - 1); 就是 quick_sort(q, 0, - 1);直接return返回
quick_sort(q, i, r);就是quick_sort(q, 0, 1);进入一样的循环,所以死循环.

)

==同理用 j 的话,一定不能写成int x = q[r]==

事实上,不用你都每一个都非常熟悉,,只要你会常用的经典没错的模板就行了.

==反正可以对着记忆用j就是q[l], q[(l + r )/ 2], q[随机] ,==

==(目前来看用j 的话q[(l + r )/ 2]run正确,q[(l + r + 1)/ 2]run错误)==

==用i 的话就是int x = q[r]或者int x = q[(l + r + 1) / 2],==

1103T1

第二遍写的时候,漏掉了scanf(“%d”, &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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (x < q[j]);
        if (i < j)
            swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}
int main(void)
{
    scanf("%d", n);//错误
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}

1104T2

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
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int q[], int l, int r);

int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);
    return 0;
}
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return; // 这是一个疑点,我认为是l >= r 的原因是当l == r的时候一个元素组成的序列就是有序的,所以你不用再递归下去了,这就是最后一层递归了,直接返回上一层就行
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    // 个人记忆口诀,快排和归并排序都用到i和j来对数组q[] 的当下这一层递归的部分 也就是l 到 r这一部分进行处理
    // 同时不能改变l 和 r的值,因为要作为实参传给下一层递归,所以用借用i和j
    // 二分查找就不需要i和j,因为直接在while循环里面更新l = mid或者 r = mid来让区间缩小
    while (i < j)
    { // 个人记忆口诀,对于快拍而言,因为这个while循环条件是i < j,所以递归终止条件是if (i >= j)
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (q[j] > x);
        if (i < j)
            // 不能忘了这个if,因为很可能你找到i和j后就已经不满足i < j的条件了,
            // 我记得y总一开始举的数组序列的例子就是第一次找到的i和j之后,发现i >= j了
            swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

疑点1

1
2
if (l >= r)
    return; // 这是一个疑点,我认为是l >= r 的原因是当l == r的时候一个元素组成的序列就是有序的,所以你不用再递归下去了,这就是最后一层递归了,直接返回上一层就行

查找第一次写的代码就是if(l >= r),个人认为的原因就是我上面的注释

疑点2

1
2
3
4
5
6
int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    // 个人记忆口诀,快排和归并排序都用到i和j来对数组q[] 的当下这一层递归的部分 也就是l 到 r这一部分进行处理
    // 同时不能改变l 和 r的值,因为要作为实参传给下一层递归,所以用借用i和j
    // 二分查找就不需要i和j,因为直接在while循环里面更新l = mid或者 r = mid来让区间缩小
    while (i < j)
    { // 个人记忆口诀,对于快拍而言,因为这个while循环条件是i < j,所以递归终止条件是if (i >= j)

疑点3

1
2
3
4
if (i < j)
            // 不能忘了这个if,因为很可能你找到i和j后就已经不满足i < j的条件了,
            // 我记得y总一开始举的数组序列的例子就是第一次找到的i和j之后,发现i >= j了
            swap(q[i], q[j]);

疑点4

我要验证一波最后的情况

用j的时候

1
2
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
1
int x = q[(l + r) / 2]

结果正确

1
int x = q[l]

y总run的时候是正确的,我run的时候数据加强了,所以超时了,Time Limit Exceeded

但是并不是Memory Limit Exceeded,这就是边界条件出问题,区间出问题了.

但是Time Limit Exceeded 只是慢了点.

结果是正确的

1
int x = q[(l + r + 1) / 2]//当l = r - 1的时候,(l + r + 1) / 2 = r成为了右边界

Memory Limit Exceeded 结果错误

1
int x = q[r]

Memory Limit Exceeded 结果错误

用i的时候(将两个j都换成 i - 1就行了 )

1
2
quick_sort(q, l, i - 1);
quick_sort(q, i, r);//i - 1 + 1就是i
1
int x = q[(l + r) / 2]//当l = r - 1的时候,(l + r) / 2 = l成为了左边界

Memory Limit Exceeded 结果错误

1
int x = q[(l + r + 1) / 2]

结果正确

1
int x = q[r]

y总run的时候是对的,原因和上面我解释的一样

报错是Time Limit Exceeded ,说明只是慢了点.

结果是正确的

1
int x = q[l]

Memory Limit Exceeded 结果错误

==对于int x = q[随机]也是同理,你别让用j 的 时候 随机到 右边界上,别让用i 的 时候 随机到 左边界上.==

1105T3

==这次写的非常快,这就是前面把问题解决了,然后背的清楚的原因==

==每一次写都要总结些东西,不能这样子昏过去==

==第一点:递归结束条件if(l >= r),一定是有等于的,因为一个元素组成的序列就是有序的.同理记忆,别的地方就是小于号==

==第二点:快排的三步(找x,操作,递归快排左右区间).==

==第三点就是:q[i],q[j]和 x 的大小,很明显记忆中是保证用i找到第一个大于等于x的数,j同理==

==第四点就是快排左右区间用i还是用j,同时改正int x的取值.这里固定的左右端点一定是l和r,这两个代表了这一层递归时所占q数组的左右端点.最后presetation一定要对,加一个空格.==

1
2
3
4
5
while(i <j){
    //do sometthing
    if(i < j)
        swap(q[i], q[j])
}
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 <iostream>
using namespace std;

const int N = 100010;
int n;
int q[N];
void quick_sort(int q[], int l, int r);
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
            i++;
        while (q[i] < x);
        do
            j--;
        while (q[j] > x);
        if (i < j)
            swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

1106T4-10

在写之前,直接读一遍自己总结的东西

==这次写的非常快,这就是前面把问题解决了,然后背的清楚的原因==

==每一次写都要总结些东西,不能这样子昏过去==

==第一点:递归结束条件if(l >= r),一定是有等于的,因为一个元素组成的序列就是有序的.同理记忆,别的地方就是小于号==

==第二点:快排的三步(找x,操作,递归快排左右区间).==

==第三点就是:q[i],q[j]和 x 的大小,很明显记忆中是保证用i找到第一个大于等于x的数,j同理==

==第四点就是快排左右区间用i还是用j,同时改正int x的取值.这里固定的左右端点一定是l和r,这两个代表了这一层递归时所占q数组的左右端点.最后presetation一定要对,加一个空格.==

打卡记录

4 Accepted
5 Accepted
6 Accepted
7 Accepted
8 Accepted
9 Accepted
10 Accepted

自己今天上午有事,去医院,在等待的时候自己也回忆背诵了一下快拍和归并排序,总而言之,回忆和背诵是时时刻刻都可以利用时间的.

打卡记录

1107晚 ac
11181650 ac
1123 ac
1124 ac

1123的笔记

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 <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int q[], int l, int r);

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

    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);

    return 0;
}
void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int x = q[(l + r + 1) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
            i++;
        while (q[i] < x); // 这里推荐用快排是不稳定的排序来记忆,所以在x左边等于x的数可能被交换到x的右边
        do
            j--;
        while (q[j] > x);
        if (i < j)
            swap(q[i], q[j]);
    }
    // quick_sort(q, l, j); // j的话就不能右边界
    // quick_sort(q, j + 1, r);

    quick_sort(q, l, i - 1);
    quick_sort(q, i, r); // i的话就不能取左边界

    // 你就记住一开始自己背诵的x = q[(l + r) / 2]和j,
    // 那么对应的使用i - 1替换j的话,x就要变成q[(l + r + 1) / 2]
    // 因为q[(l + r) / 2]一定比q[(l + r + 1) / 2]更加的靠左
    // 因此j 可以偏左,记忆联想到j可以用q[l],记忆联想到j一定不能取到右边界
    // 同理i 可以偏右,记忆联想到i可以用q[r],记忆联想到i一定不能取到左边界
}

记忆点1

1
while (q[i] < x); // 这里推荐用快排是不稳定的排序来记忆,所以在x左边等于x的数可能被交换到x的右边

记忆点2

1
2
3
4
5
6
7
8
9
10
11
// quick_sort(q, l, j); // j的话就不能右边界
// quick_sort(q, j + 1, r);

quick_sort(q, l, i - 1);
quick_sort(q, i, r); // i的话就不能取左边界

// 你就记住一开始自己背诵的x = q[(l + r) / 2]和j,
// 那么对应的使用i - 1替换j的话,x就要变成q[(l + r + 1) / 2]
// 因为q[(l + r) / 2]一定比q[(l + r + 1) / 2]更加的靠左
// 因此j 可以偏左,记忆联想到j可以用q[l],记忆联想到j一定不能取到右边界
// 同理i 可以偏右,记忆联想到i可以用q[r],记忆联想到i一定不能取到左边界

787归并排序

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
#include <iostream>
using namespace std;
const int N = 1000010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 1;//这里还是写成l + r >> 1的好,能避免和y总不一致的问题,具体原因我没时间管了.
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    // k表示当前辅助数组tmp里面有多少个数了,已经合并多少个数了
    // i指向第一个序列的起点
    // j指向第二个序列的起点
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    }
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}

1103T1

犯的错误1

1
int mid = l + r >> 2;//写错了,应该是右移一位等于除以2

应该写成

1
int mid = l + r >> 1;//写错了,应该是右移一位等于除以2

犯的错误2

1
2
3
4
5
while (i <= mid && j <= r)
    if (q[i] < q[j])//q[i] <= q[j]
        tmp[k++] = q[i++];
    else
        tmp[k++] = q[j++];

为了保证归并的稳定性,应该写成

1
2
3
4
5
while (i <= mid && j <= r)
    if (q[i] <= q[j])//q[i] <= q[j]
        tmp[k++] = q[i++];
    else
        tmp[k++] = q[j++];
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 <iostream>
using namespace std;
const int N = 1000010;//写错了,应该少些一个0
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 2;//写错了,应该是右移一位等于除以2
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];
    for (int i = l, j = 0; i <= r; i++, j++)//这个不能忘,是将临时数组里面的所有数都存回q里面去.
        q[i] = tmp[j];
}
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}

1104T2

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 <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r);

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

    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);
    return 0;
}
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return; // 疑点一:l == r的时候应该也是返回,因为一个数组成的序列本身就是有序的
    int mid = (l + r) / 2;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int i = l, j = mid + 1;
    int k = 0;
    while (i <= mid && j <= r)
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++) // 疑点二:我竟然迟疑了一下,这里i和j应该等于谁
    // 每一层 递归 都要用到q[]的一部分,这部分是由l 和 r来确定在整个q[]数组里面的范围的,因此将tmp拷贝到q里面的时候,q很可能只是拷贝这一层递归对应的整个q数组的一小部分,所以只用复制到q的l到r的位置里面
    // 因此i作为q拷贝时候的下标,范围是l到r
    // 而j作为tmp拷贝时候都下标,范围是0到XXX,因为tmp每一层递归时候都重新从0开始放置从下一层递归传上来的两个有序数字序列合并后的结果
    // tmp里面有r - l + 1个数字,tmp下标的范围是0到r - l,当i = r的时候,j自然等于r - l
    {
        q[i] = tmp[j]; // 很明显tmp很多时候是占不满的,是很小的.因为当层的要你合并的两个有序数字序列很小
        //而且tmp也是在和q[]的很小一部分,例如l 和 r非常近的部分拷贝
    }
}

疑点1

1
2
if (l >= r)
    return; // 疑点一:l == r的时候应该也是返回,因为一个数组成的序列本身就是有序的

查看第一次写的代码,果然是l >= r,个人认为这里就是我注释给出的原因,因为一个数组成的序列本身就是有序的

疑点2

将tmp拷贝回q的时候都疑点,看我的注释.

1
2
3
4
5
6
7
8
9
for (i = l, j = 0; i <= r; i++, j++) // 疑点二:我竟然迟疑了一下,这里i和j应该等于谁
    // 每一层 递归 都要用到q[]的一部分,这部分是由l 和 r来确定在整个q[]数组里面的范围的,因此将tmp拷贝到q里面的时候,q很可能只是拷贝这一层递归对应的整个q数组的一小部分,所以只用复制到q的l到r的位置里面
    // 因此i作为q拷贝时候的下标,范围是l到r
    // 而j作为tmp拷贝时候都下标,范围是0到XXX,因为tmp每一层递归时候都重新从0开始放置从下一层递归传上来的两个有序数字序列合并后的结果
    // tmp里面有r - l + 1个数字,tmp下标的范围是0到r - l,当i = r的时候,j自然等于r - l
    {
        q[i] = tmp[j]; // 很明显tmp很多时候是占不满的,是很小的.因为当层的要你合并的两个有序数字序列很小
        //而且tmp也是在和q[]的很小一部分,例如l 和 r非常近的部分拷贝
    }

1105T3

这次敲得也很快很熟练,背的很好.

不过我感觉应该按照y总说的,第一次就直接敲五遍,这样课上里面就没有任何疑问,不会像我一样隔了两天才做到熟练的程度

后续每天写一遍只是为了保证记忆

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 <iostream>
using namespace std;

const int N = 100010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r);
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}
void merge_sort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2, i = l, j = mid + 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j])
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];
    }
    while (i <= mid)
        tmp[k++] = q[i++];
    while (j <= r)
        tmp[k++] = q[j++];
    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = tmp[j];
}

1106T4-10

在写之前,直接读一遍自己总结的东西

==这次写的非常快,这就是前面把问题解决了,然后背的清楚的原因==

==每一次写都要总结些东西,不能这样子昏过去==

==第一点:递归结束条件if(l >= r),一定是有等于的,因为一个元素组成的序列就是有序的.同理记忆,别的地方就是小于号==(快排和归并都是l >= r作为递归退出条件)

==第二点:归并的三步(==

==找mid = (l + r) / 2,不需要修正mid,==

==递归归并左右区间(把任务分给助手来做)==

==将助手给你的结果两个有序序列,自己做操作合并成一个有序序列).==

==第三点就是int mid在第二步前面,==

==int k = 0, i = l, j = mid + 1;在第二部后面,这样有层次感,接着自己做操作合并成一个有序序列放在tmp数组里面:==

==第四点就是递归将tmp里面排好的有序序列放到q的[l —r]部分里面.这里q固定的左右端点一定是l和r,这两个代表了这一层递归时所占q数组的左右端点.最后presetation一定要对,加一个空格.==

4 Accepted
5 Accepted
6 Accepted
7 Accepted
8 Accepted
9 Accepted
10 Accepted

我有一个感觉,当自己自认为熟练了.

可以等待个几分钟,中间做的什么别的事情,例如看一会Cpp视频或者做一道简单的题目

等自己记忆消失了再重新写几遍这里的模板.

打卡记录

1107晚 ac
11181708 ac
1123 ac
1124 ac

1123笔记

1
int mid = l + r >> 1;//这里还是写成l + r >> 1的好,能避免和y总不一致的问题,具体原因我没时间管了.

789数的范围

1104T1

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
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N]; // 记录自己每一次不太确定的部分,好像是N,不是n
bool checkStart(int mid, int k);
int bsearchStart(int q[], int l, int r, int k);
bool checkEnd(int mid, int k);
int bsearchEnd(int q[], int l, int r, int k);
int main(void)
{
    int m;                  // m表示询问次数
    scanf("%d %d", &n, &m); // 差点忘记给n和m加上引用符号
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
    int k; // 要查询的元素
    while (m--)
    {
        scanf("%d", &k);
        int startIndex = bsearchStart(q, 0, n - 1, k);
        int startEnd = bsearchEnd(q, 0, n - 1, k);
        cout << startIndex << " " << startEnd << endl;
    }

    return 0;
}

bool checkEnd(int mid, int k)
{
    if (q[mid] <= k)
        return true; // 红色分界点就是从右往左第一个小于等于k的数字,就是题干要我们找的答案之二,就是数字k的结束位置
    else
        return false;
}
bool checkStart(int mid, int k)
{
    if (q[mid] >= k)
        return true; // 绿色分界点就是第一个大于等于k的数字,就是题干要我们找的答案之一,就是数字k的开始位置
    else
        return false;
}
int bsearchStart(int q[], int l, int r, int k)
{

    while (l < r)
    {                         // 应该是l < r不带等号,因为要保证循环结束的时候l == r从而区间里面只有一个数,这个数就是我们要找的答案,就是红绿区间分界点
        int mid = l + r >> 1; // mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半
        if (checkStart(mid, k))
            r = mid; // 既然是r = mid就不用让mid = l + r + 1 >> 1
        else
            l = mid + 1;
    }
    if (q[l] != k) // 这是因为题干要求而在模板基础上做的改变.
        return -1; // 如果q[l] != k,说明这个数字q[]里面没有数值等于k 的数字,不存在该元素,就返回 -1
    else
        return l;
}
int bsearchEnd(int q[], int l, int r, int k)
{

    while (l < r)
    {                             // 应该是l < r不带等号,因为要保证循环结束的时候l == r从而区间里面只有一个数,这个数就是我们要找的答案,就是红绿区间分界点
        int mid = l + r + 1 >> 1; // mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半
        if (checkEnd(mid, k))
            l = mid; // 既然是l = mid就必要让mid = l + r + 1 >> 1
        else
            r = mid - 1;
    }
    if (q[l] != k) // 这是因为题干要求而在模板基础上做的改变.
        return -1; // 如果q[l] != k,说明这个数字q[]里面没有数值等于k 的数字,不存在该元素,就返回 -1
    else
        return l;
}

写的时候的疑点:

第一个疑点

int q[N]; // 记录自己每一次不太确定的部分,好像是N,不是n

这里就是N,N表示数组的最大空间是MAX

n是你输入的元素个数,是size

第二个疑点

int bsearchStart(int q[], int l, int r, int k);和int bsearchEnd(int q[], int l, int r, int k);不用传数组int q[]因为你已经把他定义成全局变量了.只用传入数组的开始下标0,数组的结束下标n - 1,要查询的数字k

第三个疑点

是

1
while (l < r)

还是

1
while (l <= r)

代码应该是

1
while (l < r)

这样才能保证// 应该是l < r不带等号,因为要保证循环结束的时候l == r从而区间里面只有一个数,这个数就是我们要找的答案,就是红绿区间分界点

第四个疑点

我竟然在怀疑

1
int mid = l + r >> 1; // mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半

是在while(l < r)的里面,还是在它的外面

经过一番自己的考量,发觉是在里面,因为// mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半

1105T2

这次敲得也很快, 但是应该课上第一次就把所有的问题解决的,不然时间真的不够.

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
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
bool checkStart(int mid, int k);
bool checkEnd(int mid, int k);
int bsearchStart(int l, int r, int k);
int bsearchEnd(int l, int r, int k);
int main(void)
{
    int m;

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);

    while (m--)
    {
        int k;
        cin >> k;
        int indexStart = bsearchStart(0, n - 1, k);
        int indexEnd = bsearchEnd(0, n - 1, k);
        cout << indexStart << " " << indexEnd << endl;
    }
    return 0;
}
bool checkStart(int mid, int k)
{
    if (q[mid] >= k)
        return true;
    else
        return false;
}
bool checkEnd(int mid, int k)
{
    if (q[mid] <= k)
        return true;
    else
        return false;
}
int bsearchStart(int l, int r, int k)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (checkStart(mid, k))
            r = mid;
        else
            l = mid + 1;
    }
    if (q[l] != k)
        return -1;
    else
        return l;
}
int bsearchEnd(int l, int r, int k)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (checkEnd(mid, k))
            l = mid;
        else
            r = mid - 1;
    }
    if (q[l] != k)
        return -1;
    else
        return l;
}

1106T3-5

接下来是我通过这次散步加深的整数二分的理解:

一个区间,你通过一个你制定的条件,将区间分成红绿两个区间,

(你制定的条件是有方法的,不是随便制定的,是按照题干要你求的内容制定的.一句话,你制定的条件要让红绿区间的分界点就是题干要你求的内容,就是题干让你找的答案)

接着不断的取下标为mid的点,判断下标为mid的点落在红色区间还是绿色区间里面,然后通过l = mid或者是r = mid来缩小区间

(你每次缩小区间都能保证你要找的答案,你要找的红绿区间分界点都在缩小后的区间里面)

,一直缩小区间,直到区间里面只有一个数,这个数就是我们要找到答案,就是我们的红绿区间的分界点.

==有几个易错点==

====代码应该是==

1
while (l < r)

==这样才能保证// 应该是l < r不带等号,因为要保证循环结束的时候l == r从而区间里面只有一个数,这个数就是我们要找的答案(所以对于模板来说,最后是return l),就是红绿区间分界点====

==第四个疑点==

==我竟然在怀疑==

1
int mid = l + r >> 1; // mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半

==是在while(l < r)的里面,还是在它的外面==

==经过一番自己的考量,发觉是在里面,因为// mid应该在while里面,不然每一次循环mid都一直是最开始的l和最开始的r的和的一半==

一定要注意,这里的mid是可能要加一来修正的

3 Accepted
4 Accepted
5 Accepted

打卡记录

1107晚 ac

790数的三次方根

1104T1

d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;

int main(void)
{
    double x;
    cin >> x;
    double l = 0, r = x;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid >= x)
            r = mid;
        else
            l = mid;
    }
    printf("%f", l);
    return 0;
}

d

写的时候的错误:

第一个错误

习惯性把

1
2
3
double x;
double l = 0, r = x;
    double mid = (l + r) / 2;

都写成int类型导致的错误,我说过了,每次想到int就要想到为什么不能写double呢????

看到int就想到double

1105T2

之后的次数都坐着道题目

  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
35
36
37
38
#include <iostream>
using namespace std;

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

    if (n > 0)
    {
        double l = 0, r = 10010;
        while (r - l > 1e-8)
        {
            double mid = (l + r) / 2;
            if (mid * mid * mid >= n)
                r = mid;
            else
                l = mid;
        }
        printf("%.6f", l);
    }
    else
    {
        n = -n;
        double l = 0, r = 10010;
        while (r - l > 1e-8)
        {
            double mid = (l + r) / 2;
            if (mid * mid * mid >= n)
                r = mid;
            else
                l = mid;
        }
        printf("%.6f", -l);
    }

    return 0;
}

等y总讲习题课的时候我在重复写

791高精度加法

y总的写法

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
#include <iostream>
#include <vector>
using namespace std;

const int N = 100010;
vector<int> add(vector<int> &A, vector<int> &B);
int main(void)
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    }
    for (int i = b.size() - 1; i >= 0; i--)
    {
        B.push_back(b[i] - '0');
    }
    vector<int> C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i--)
    {
        printf("%d", C[i]);
    }
    return 0;
}
vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++)
    {
        if (i < A.size())
            t += A[i];
        if (i < B.size())
            t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t)
        C.push_back(1);
    return C;
}

打卡记录

1109早 ac
1109午前 ac
1109午后 ac

个人错误

总是把i < A.size() || i < B.size()写成i < A.size() || B.size(),千万记住不要犯同样的错误.

792高精度减法

y总写法

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
#include <iostream>
#include <vector>
using namespace std;
// 改题目假定 A 和B都是正整数
// 如果不是正整数,那就一定可以转换成 A的绝对值和B的绝对值想加减的问题,最后要不要加一个负号,在main里面分类讨论就行了.
const int N = 100010;
vector<int> sub(vector<int> &A, vector<int> &B);
bool cmp(vector<int> &A, vector<int> &B);
int main(void)
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        A.push_back(a[i] - '0');
    }
    for (int i = b.size() - 1; i >= 0; i--)
    {
        B.push_back(b[i] - '0');
    }
    if (cmp(A, B))
    {
        vector<int> C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i--)
        {
            printf("%d", C[i]);
        }
    }
    else
    {
        vector<int> C = sub(B, A);
        printf("-");
        for (int i = C.size() - 1; i >= 0; i--)
        {
            printf("%d", C[i]);
        }
    }

    return 0;
}
// A >= B return true
// A < B return false
bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size())
        // 是大于号不是减法,如果结果是负数那整数转换成bool类型,等于true;
        // 但此时A < B结果应该是 false
        return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--)
    {
        if (A[i] != B[i])
            return A[i] > B[i];
    }
    return true; // 最后 A == B ,我们返回true
}
vector<int> sub(vector<int> &A, vector<int> &B)
// 默认A >= B
//,如果A< B则交换的行为直接在外面调用函数传入实参的时候交换A和B 的位置,
// 包括最后要先输出"-"的话,也是在main函数里面放在printf C容器之前,
// 反正你一个函数的功能是越简单越明确越好
{
    vector<int> C;
    int t = 0;
    // 此时A的size一定是大于等于B的 size
    for (int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;
        if (i < B.size())
            t -= B[i];
        C.push_back((t + 10) % 10); // 把两种情况合二为一
        if (t < 0)
            t = 1;
        else
            t = 0;
    }
    // 从A.size() - 1位开始(包括A.size() - 1位),最前面的数往后可能是一连串的零
    // 因此要做处理,对整数高位做处理就是对vector<int> 的末尾做处理
    // 去掉前导零
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    // y总的写法确实好理解一些,以后就用y总的写法

    // 因为A >= B所以不会像加法那样出现要想最高位的上面一位进位
    // 在减法这里就是不可能向最高位的上面一位借位,不然就A< B了,矛盾
    //  所以结束循环后的t 一定是0,不用将t pushback到A.size() 位,,因此我们直接返回C
    return C;
}


打卡记录

1109早 ac
1109午前 ac
1109午后 ac

犯的错误

对于cmp函数而言,千万千万这一段for (int i = A.size() - 1; i >= 0; i--)是从数组末尾也就是大整数的最高位开始比较,千万别不过脑子不细心写成i从0开始了.

自己定义的cmp是有参数A , B的,千万不能饿忘记

if (cmp(A, B))写成 if (cmp)

在外面处理交换A , B就是实参改变位置,千万不能忘记

1
2
3
else
    {
        auto C = sub(B, A);

写成

1
2
3
else
    {
        auto C = sub(A, B);//这里是要换的,不粗心的复制粘贴就了事.

数字字符要 - ‘0’才能等于数字

1
2
for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');

总是写成

1
2
for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i]);

793高精度乘法

y总的写法

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 <iostream>
#include <vector>
using namespace std;

const int N = 100010;
vector<int> mul(vector<int> &A, int b);
int main(void)
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');

    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i--)
        printf("%d", C[i]);
    return 0;
}
vector<int> mul(vector<int> &A, int b)
{
    // 先尝试自己写
    vector<int> C;
    int t = 0;
    // 这里i < A.size() || t你用我之前的true和false分别分四种情况看一看就能理解了
    for (int i = 0; i < A.size() || t; i++)
    {
        if (i < A.size())
            t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    // 这里新的题目是不是有去除前导零,所以我这里写一遍
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

打卡记录

1109早 ac
1109午前 ac
1109午后 ac

794高精度除法

y总的写法

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
vector<int> div(vector<int> &A, int b, int &r); // 余数用引用类型返回,在函数内修改余数会影响main函数内的余数大小
int main(void)
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    int r;
    auto C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i--)
        printf("%d", C[i]);
    cout << endl;
    cout << r << endl;
    return 0;
}
// 计算 A / b,商是C,余数是r
vector<int> div(vector<int> &A, int b, int &r) // 余数用引用类型返回,在函数内修改余数会影响main函数内的余数大小
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i--)
    { // 除法从最高位开始除,前面加减乘都是从最低位开始
        r = r * 10 + A[i];
        C.push_back(r / b); // 可能会有前导零
        r %= b;
    }
    // 逆转C
    reverse(C.begin(), C.end());
    // 去除前导零
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

打卡记录

1109下午 ac
ac
ac

个人错误

被y总带偏了,把

1
2
C.push_back(r / b); // 可能会有前导零
r %= b;

写成

1
2
C.push_back(r / 10); // 可能会有前导零
r %= 10;

千万不能记错了.

795前缀和

y总的写法

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 <iostream>

using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main(void)
{

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    // 前缀和的初始化
    s[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + a[i];
    }
    while (m--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

打卡记录

1109下午 ac
ac
ac

796. 子矩阵的和

y总的写法

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
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
int main(void)
{
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
        }
    // 初始化前缀和数组
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) // 这里吧m写成n了
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    while (q--)
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}

打卡记录

1109下午 ac
ac
ac

797. 差分

y总的写法

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
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N]; // 全局变量默认为零,好像是:????
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}
int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++)
        insert(i, i, a[i]); // 其实也就是让b[i] = a[i] - a[i - 1];
    while (m--)
    {
        int l, r, c;
        scanf("%d %d %d", &l, &r, &c);
        insert(l, r, c);
    }
    // 对差分数组求一遍前缀和就是原来的数组a
    for (int i = 1; i <= n; i++)
    {
        b[i] += b[i - 1];
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", b[i]);

    return 0;
}

打卡记录

1109晚 ac
ac
ac

798. 差分矩阵

y总的写法

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
#include <iostream>
using namespace std;

const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main(void)
{
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            insert(i, j, i, j, a[i][j]);

    while (q--)
    {
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            b[i][j] = b[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            printf("%d ", b[i][j]);
        printf("\n");
    }
    return 0;
}

打卡记录

1109晚 ac
ac
ac

799最长连续不重复子序列

800数组元素的目标和

2816判断子序列

801二进制中1的个数

802区间和

803区间合并

830单调栈

1107T1-7

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
#include <iostream>
using namespace std;

const int N = 100010;
int n;
int stk[N], tt = 0;
// 初始为空栈,空栈个人设置栈顶指针tt = 0
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x)
            tt--;
        if (tt)
            printf("%d ", stk[tt]);
        else
            printf("-1 ");

        stk[++tt] = x;
    }
    return 0;
}

结果是Accepted

1 Accepted
2 Accepted
3 Accepted
4 Accepted
5 Ac
6 ac
7 ac