头像

tonngw

$$\href{https://github.com/tonngw/LeetCode021}{github.com/tonngw/LeetCode021}$$




离线:3小时前


最近来访(240)
用户头像
acwing_gza2
用户头像
acwing_gza
用户头像
Ruccs
用户头像
wzy_
用户头像
封禁用户
用户头像
今天几号
用户头像
dadalalala
用户头像
ikBlue
用户头像
AcWing2AK
用户头像
南岸以南南岸哀
用户头像
Charlie0998
用户头像
SunnyYuan
用户头像
wsh_
用户头像
Viote
用户头像
破晓后的清晨
用户头像
永封用户
用户头像
冰凝
用户头像
冰之韵
用户头像
大雪莱
用户头像
2010


tonngw
2天前

AcWing-Helper 使用指南点这里

仓库地址:https://github.com/tonngw/acwing-helper

插件地址:https://greasyfork.org/zh-CN/scripts/444381-acwing-helper

2022.06.29

添加功能:

  • 添加其他页面代码复制功能:现已支持打卡、题解、分享、问答页面

2022.06.18

更新:

2022.06.04

更新:

  • 修复代码打卡页面「复制代码」功能 Bug,支持同页面多份代码复制

2022.05.28

添加功能:

  • 活动打卡页面直接跳转到题目页面(支持所有活动)

  • 在题目内容页面内打开题目

2022.05.03

AcWing-Helper 的第一个版本

功能:

  • 复制题目描述,并存入剪切板

  • 复制题目描述生成当前题目的题解模板,并存入剪切板
    大多数情况下一道题目只会写一种做法,这里提供了一套简洁的模板,模板来自 AcWing

  • 切换页面风格,AcWing <-> LeetCode

  • 复制代码(目前只支持 */code/* 目录下的代码,即从打卡页面点击题目查看相关代码)




tonngw
5天前

AcWing-Helper 分享帖已经超过 $1000$ 阅读量,插件总安装量突破 $100$ 大关,感谢大家的支持,感谢 AcWing 算法交流平台!

如果这个插件在使用的过程中对你有所帮助,请帮我在仓库 https://github.com/tonngw/acwing-helper 中点个 Star,这对我很有帮助(马上找工作多颗星星好看点),谢谢~

使用指南:https://www.acwing.com/blog/content/20319/

插件安装地址:https://greasyfork.org/zh-CN/scripts/444381-acwing-helper

从一开始只是为了方便写题解,到后来逐渐添加了一些比较实用的小功能,期间迭代了很多版本,也修复了几位同学提出的 $Bug$,不断地完善它,慢慢的也收获了不少小伙伴的支持。

自我感觉还有一件挺有意义的事情,还是想继续维护下去,由于之前做的一些功能都是我在使用 AcWing 的过程中觉得有用才去试着实现的,有些好的想法可能会浮现的比较慢,所以来征求大家的一些宝贵意见和想法,你还想要什么功能呢,可以在评论区中打出来,每一条评论我都会看。由于个人水平有限,大家提出的意见可能无法实现,也请大家谅解!

另外最近打算提供题解页面以及分享页面的「代码复制」功能,敬请期待。

感谢支持




tonngw
5天前

写题解工具

题目描述

从前有个人名叫 WNB,他有着天才般的记忆力,他珍藏了许多许多的宝藏。

在他离世之后留给后人一个难题(专门考验记忆力的啊!),如果谁能轻松回答出这个问题,便可以继承他的宝藏。

题目是这样的:给你一大串数字(编号为 $1$ 到 $N$,大小可不一定哦!),在你看过一遍之后,它便消失在你面前,随后问题就出现了,给你 $M$ 个询问,每次询问就给你两个数字 $A,B$,要求你瞬间就说出属于 $A$ 到 $B$ 这段区间内的最大数。

一天,一位美丽的姐姐从天上飞过,看到这个问题,感到很有意思(主要是据说那个宝藏里面藏着一种美容水,喝了可以让这美丽的姐姐更加迷人),于是她就竭尽全力想解决这个问题。

但是,她每次都以失败告终,因为这数字的个数是在太多了!

于是她请天才的你帮他解决。如果你帮她解决了这个问题,可是会得到很多甜头的哦!

输入格式

第一行一个整数 $N$ 表示数字的个数。

接下来一行为 $N$ 个数,表示数字序列。

第三行读入一个 $M$,表示你看完那串数后需要被提问的次数。

接下来 $M$ 行,每行都有两个整数 $A,B$。

输出格式

输出共 $M$ 行,每行输出一个数,表示对一个问题的回答。

数据范围

$1 \le N \le 2 \times 10^5$,
$1 \le M \le 10^4$,
$1 \le A \le B \le N$。

输入样例:

6
34 1 8 123 3 2
4
1 2
1 5
3 4
2 3

输出样例:

34
123
123
8

算法

(RMQ求区间最值) $O(nlogn)$

RMQ(Range Minimum/Maximum Query) 算法是用来求区间最值问题的。

首先需要预处理长度为 $2^0、2^1、…、2^M$ 的区间最大值。

对于每个查询 $[l, r]$,需要先找出最大的一个满足 $2^k < len$ 的 $k$,其中 $len = r - 1 + 1$,可以用 <cmath> 库中的 $log{10}$ 函数求解,$log_2{len} = \frac {log_{10}len} {log_{10}2}$。
最大值就是从 $[l, l + 2^k]$ 和 $[r - 2^k + 1, r]$ 中取一个 $max$,因为 $2^k < len$ 所以单纯取左边不能覆盖整个区间,所以只能左边取长度 $2^k$ 和右边往左取 $2^k$ 取一个最大值。

时间复杂度

$O(nlogn)$

空间复杂度

$O(nM)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M];

// 预处理 f 数组
void init()
{
    for (int j = 0; j < M; j ++ )  // 枚举 2^j 次方,表示长度
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ ) // 枚举区间左端点,同时右端点不能超过 n
            if (!j) f[i][j] = w[i]; // 长度为 2^0 = 1 的最大值就是自己
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]); // 计算公式
}

int query(int l, int r)
{
    int len = r - l + 1; // 区间长度
    int k = log(len) / log(2); // 这里 log 是 math 库中以 10 为底的 log,求的是最大的一个 k,log2(k)
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}


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

    init();

    scanf("%d", &m);

    while (m -- ) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }

    return 0;
}


活动打卡代码 AcWing 1273. 天才的记忆

tonngw
5天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M];

// 预处理 f 数组
void init()
{
    for (int j = 0; j < M; j ++ )  // 枚举 2^j 次方,表示长度
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ ) // 枚举区间左端点,同时右端点不能超过 n
            if (!j) f[i][j] = w[i]; // 长度为 2^0 = 1 的最大值就是自己
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]); // 计算公式
}

int query(int l, int r)
{
    int len = r - l + 1; // 区间长度
    int k = log(len) / log(2); // 这里 log 是 math 库中以 10 为底的 log,求的是最大的一个 k,log2(k)
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}


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

    init();

    scanf("%d", &m);

    while (m -- ) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }

    return 0;
}



tonngw
5天前

写题解工具

题目描述

在这个问题中,您必须分析特定的排序算法----超快速排序。

该算法通过交换两个相邻的序列元素来处理 $n$ 个不同整数的序列,直到序列按升序排序。

对于输入序列 9 1 0 5 4,超快速排序生成输出 0 1 4 5 9

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

输入格式

输入包括一些测试用例。

每个测试用例的第一行输入整数 $n$,代表该用例中输入序列的长度。

接下来 $n$ 行每行输入一个整数 $a_i$,代表用例中输入序列的具体数据,第 $i$ 行的数据代表序列中第 $i$ 个数。

当输入用例中包含的输入序列长度为 $0$ 时,输入终止,该序列无需处理。

输出格式

对于每个需要处理的输入序列,输出一个整数 $op$,代表对给定输入序列进行排序所需的最小交换操作数,每个整数占一行。

数据范围

$0 \le n < 500000$,
一个测试点中,所有 $n$ 的和不超过 $500000$。
$0 \le a_i \le 999999999$

输入样例:

5
9
1
0
5
4
3
1
2
3
0

输出样例:

6
0

算法

(归并排序求逆序对) $O(nlogn)$

如果前一个数大于后一个数,那么每次交换整体的逆序对个数就会减 1,而且它们交换之后对其他逆序对是没有影响的,当逆序对个数为 0 时整个序列就是有序的,所以将序列变为有序序列的最小操作次数就是序列中逆序对的个数。

时间复杂度

$O(nlogn)$

空间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n;
LL q[N], w[N];

LL merge_sort(int l, int r)
{
    if (l == r) return 0;

    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) w[k ++ ] = q[i ++ ];
        else {
            res += mid - i + 1; // 两个有序序列合并,如果左边区间 [l, mid] 的 q[i] 大于右边区间 [mid + 1, r] 中的 q[j],那么左边区间和 q[j] 可以构成的逆序对就是 mid - i + 1 个
            w[k ++ ] = q[j ++ ];
        }

    while (i <= mid) w[k ++ ] = q[i ++ ];
    while (j <= r) w[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = w[j];
    return res;
}

int main() 
{
    while (scanf("%d", &n), n) {
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
        printf("%lld\n", merge_sort(0, n - 1));
    }

    return 0;
}


活动打卡代码 AcWing 107. 超快速排序

tonngw
5天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n;
LL q[N], w[N];

LL merge_sort(int l, int r)
{
    if (l == r) return 0;

    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) w[k ++ ] = q[i ++ ];
        else {
            res += mid - i + 1; // 两个有序序列合并,如果左边区间 [l, mid] 的 q[i] 大于右边区间 [mid + 1, r] 中的 q[j],那么左边区间和 q[j] 可以构成的逆序对就是 mid - i + 1 个
            w[k ++ ] = q[j ++ ];
        }

    while (i <= mid) w[k ++ ] = q[i ++ ];
    while (j <= r) w[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = w[j];
    return res;
}

int main() 
{
    while (scanf("%d", &n), n) {
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
        printf("%lld\n", merge_sort(0, n - 1));
    }

    return 0;
}



tonngw
5天前

写题解工具

题目描述

依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。

输入格式

第一行输入一个整数 $P$,代表后面数据集的个数,接下来若干行输入各个数据集。

每个数据集的第一行首先输入一个代表数据集的编号的整数。

然后输入一个整数 $M$,代表数据集中包含数据的个数,$M$ 一定为奇数,数据之间用空格隔开。

数据集的剩余行由数据集的数据构成,每行包含 $10$ 个数据,最后一行数据量可能少于 $10$ 个,数据之间用空格隔开。

输出格式

对于每个数据集,第一行输出两个整数,分别代表数据集的编号以及输出中位数的个数(应为数据个数加一的二分之一),数据之间用空格隔开。

数据集的剩余行由输出的中位数构成,每行包含 $10$ 个数据,最后一行数据量可能少于 $10$ 个,数据之间用空格隔开。

输出中不应该存在空行。

数据范围

$1 \le P \le 1000$,
$1 \le M \le 99999$,
所有 $M$ 相加之和不超过 $5 \times 10^5$。

输入样例:

3 
1 9 
1 2 3 4 5 6 7 8 9 
2 9 
9 8 7 6 5 4 3 2 1 
3 23 
23 41 13 22 -3 24 -31 -11 -8 -7 
3 5 103 211 -311 -45 -67 -73 -81 -99 
-33 24 56

输出样例:

1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3 
-7 -3

算法

(对顶堆) $O(nlogn)$

用两个堆来动态维护中位数,一个大顶堆(上),一个小顶堆(下),保证小顶堆的堆顶就是中位数,每次读入一个数先放到小顶堆中,如果小顶堆的元素个数比大顶堆的元素个数加 1 还要多,那么就弹出一个元素放入大顶堆,之后再维护两个堆顶的大小,如果上面大则交换。

时间复杂度

$O(nlogn)$

空间复杂度

$O(n)$

C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int P = 1010, N = 100010;

using namespace std;

int main()
{
    int p;
    scanf("%d", &p);

    while (p -- ) {
        priority_queue<int> down;
        priority_queue<int, vector<int>, greater<int>> up;

        int id, m;
        scanf("%d%d", &id, &m);

        printf("%d %d\n", id, (m + 1) / 2);

        int cnt = 0;
        int x;
        for (int i = 1; i <= m; i ++ ) {
            scanf("%d", &x);
            // min_heap.push(x);
            // if (min_heap.size() > max_heap.size() + 1) {
            //     max_heap.push(min_heap.top()), min_heap.pop();
            // }
            // if (max_heap.size() && min_heap.top() < max_heap.top()) {
            //     int minv = min_heap.top(), maxv = max_heap.top();
            //     min_heap.pop(), max_heap.pop();
            //     max_heap.push(minv), min_heap.push(maxv);
            // }

            if (down.empty() || x <= down.top()) down.push(x);
            else up.push(x);

            if (down.size() > up.size() + 1) up.push(down.top()), down.pop();
            if (up.size() > down.size()) down.push(up.top()), up.pop();


            if (i % 2) {
                cnt ++ ;
                printf("%d ", down.top());
                if (cnt % 10 == 0 && i < m) puts("");
            }
        }
        puts("");
    }

    return 0;
}


活动打卡代码 AcWing 106. 动态中位数

tonngw
5天前
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int P = 1010, N = 100010;

using namespace std;

int main()
{
    int p;
    scanf("%d", &p);

    while (p -- ) {
        priority_queue<int> down;
        priority_queue<int, vector<int>, greater<int>> up;

        int id, m;
        scanf("%d%d", &id, &m);

        printf("%d %d\n", id, (m + 1) / 2);

        int cnt = 0;
        int x;
        for (int i = 1; i <= m; i ++ ) {
            scanf("%d", &x);
            // min_heap.push(x);
            // if (min_heap.size() > max_heap.size() + 1) {
            //     max_heap.push(min_heap.top()), min_heap.pop();
            // }
            // if (max_heap.size() && min_heap.top() < max_heap.top()) {
            //     int minv = min_heap.top(), maxv = max_heap.top();
            //     min_heap.pop(), max_heap.pop();
            //     max_heap.push(minv), min_heap.push(maxv);
            // }

            if (down.empty() || x <= down.top()) down.push(x);
            else up.push(x);

            if (down.size() > up.size() + 1) up.push(down.top()), down.pop();
            if (up.size() > down.size()) down.push(up.top()), up.pop();


            if (i % 2) {
                cnt ++ ;
                printf("%d ", down.top());
                if (cnt % 10 == 0 && i < m) puts("");
            }
        }
        puts("");
    }

    return 0;
}


活动打卡代码 AcWing 105. 七夕祭

tonngw
5天前

!

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int row[N], col[N], s[N], c[N];

LL work(int n, int a[])
{
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];

    if (s[n] % n) return -1;

    int avg = s[n] / n;

    c[1] = 0;
    for (int i = 2; i <= n; i ++ ) c[i] = s[i - 1] - (i - 1) * avg;

    sort(c + 1, c + n + 1);
    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res += abs(c[i] - c[(n + 1) / 2]);

    return res;
}

int main()
{
    int n, m, cnt;
    scanf("%d%d%d", &n, &m, &cnt);

    while (cnt -- ) {
        int x, y;
        scanf("%d%d", &x, &y);
        row[x] ++, col[y] ++ ;
    }

    LL r = work(n, row);
    LL c = work(m, col);

    if (r != -1 && c != -1) printf("both %lld\n", r + c);
    else if (r != -1) printf("row %lld\n", r);
    else if (c != -1) printf("column %lld\n", c);
    else puts("impossible");

    return 0;
}


活动打卡代码 AcWing 113. 特殊排序

tonngw
6天前

调用 STL stable_sort

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> a;
        for(int i = 1;i <= N;i ++ ) a.push_back(i);
        stable_sort(a.begin(), a.end(), compare);
        return a;
    }
};