头像

Java同学

上方山骇客协会




离线:1分钟前


最近来访(32)
用户头像
没炸了
用户头像
烛之武
用户头像
AcWing2AK
用户头像
White615
用户头像
听雨.无尘明月夜
用户头像
赤赤
用户头像
Lames
用户头像
Txoon
用户头像
Tilbur


详情看注释,最关键的问题用注释表出

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int arr[N];

// 为什么能够采用归并来计算 逆序对
// 因为归并是先分到最小 ,也就是左右两个数组分别只有一个数,那么此时下标和位置均没有变化
// 在进行 归并的时候 ,我们又同时对满足要求的逆序对数量进行添加,然后同时归并
// 归并到最后 也就是两个大的左右数组,内部均有序,而外部无序,虽然左右数组的内部位置发生了变化,但是由于递归已经把发生变化的部分计算完成了

// M 是右边数组的下界
long long res = 0;
void merge(int arr[], int L, int M, int R)
{
    int left_len = M - L;
    int right_len = R - M + 1;
    int left_arr[left_len];
    int right_arr[right_len];

    for (int i = L; i < M; i++)
    {
        left_arr[i - L] = arr[i];
    }
    for (int j = M; j < R + 1; j++)
    {
        right_arr[j - M] = arr[j];
    }

    int i = 0;
    int j = 0;
    int k = L;
    while (i < left_len && j < right_len)
    {
        if (left_arr[i] <= right_arr[j])
        {
            arr[k++] = left_arr[i++];
        }
        else
        {
            arr[k++] = right_arr[j++];
            // 设想只有两个数的情况,这也是归并最开始 分而治之 分到只有两个数
            // 前面的 if 属于 下标小于 且 数值也小于等于
            // 这个判断中 ,则符合题目要求
            // 那么根据归并排序的特点,块内有序,块间无序,所以这时候
            // 左半边数组从i位置 到 M - 1位置 均大于当前右半边数组的 j位置(注意 M是右半边数组的下界)
            // 注意 这里需要加上 L 这样才能保证下标正确 这就是对 i 进行一个下标矫正
            // 也就是说 把 i + L 之后 这样 M 和 i+L均是在数组上的下标了
            res += M - (L + i);
        }
    }

    while (i < left_len)
    {
        arr[k++] = left_arr[i++];
    }
    while (j < right_len)
    {
        arr[k++] = right_arr[j++];
    }
}

void merge_sort(int arr[], int L, int R)
{
    if (L >= R)
    {
        return;
    }
    else if (L < R)
    {
        int M = (L + R) >> 1;
        merge_sort(arr, L, M);
        merge_sort(arr, M + 1, R);
        merge(arr, L, M + 1, R);
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    merge_sort(arr, 0, n - 1);
    // for (int i = 0; i < n; i++)
    // {
    //     printf("%d ", arr[i]);
    // }
    cout << res;
    return 0;
}



哈希表的做法 具体在注释

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

// 直接暴力会超时
// vector<string> all;
// vector<string> come;

//用来表示 来参加的校友
vector<string> both;
// 1 表示出现
unordered_map<string, int> is_come;

int main()
{
    int n, m;
    string a;
    cin >> n;

    //初始化为最年轻的人
    int old = 99999999;
    // 记录来宾最年长
    string old_people;
    // 记录两者交集最年长
    string old_student;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        is_come[a] = 1;
    }

    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a;
        if (is_come[a] == 1)
        {
            both.push_back(a);
        }
        //计算来宾中最年长的
        if (stoi(a.substr(6, 8)) < old)
        {
            old = stoi(a.substr(6, 8));
            old_people = a;
        }
    }

    cout << both.size() << endl;

    // 因为要计算来的校友中最年长的 所以需要初始化年龄
    old = 99999999;
    if (both.size() > 0)
    {
        for (auto i : both)
        {
            // 若出现比他老的
            if (stoi(i.substr(6, 8)) < old)
            {
                old = stoi(i.substr(6, 8));
                old_student = i;
            }
        }
        cout << old_student << endl;
    }
    else
    {

        cout << old_people << endl;
    }

    return 0;
}


活动打卡代码 AcWing 4269. 校庆

直接暴力会超时 还是用hash表做吧

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

// 直接暴力会超时
// vector<string> all;
// vector<string> come;
//用来表示 来参加的校友
vector<string> both;
// 1 表示出现
unordered_map<string, int> is_come;

int main()
{
    int n, m;
    string a;
    cin >> n;

    //初始化为最年轻的人
    int old = 99999999;
    string old_people;
    string old_student;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        is_come[a] = 1;
    }

    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a;
        if (is_come[a] == 1)
        {
            both.push_back(a);
        }
        //计算来宾中最年长的
        if (stoi(a.substr(6, 8)) < old)
        {
            old = stoi(a.substr(6, 8));
            old_people = a;
        }
    }

    cout << both.size() << endl;

    // 因为要计算来的校友中最年长的 所以需要初始化年龄
    old = 99999999;
    if (both.size() > 0)
    {
        for (auto i : both)
        {
            // 若出现比他老的
            if (stoi(i.substr(6, 8)) < old)
            {
                old = stoi(i.substr(6, 8));
                old_student = i;
            }
        }
        cout << old_student << endl;
    }
    else
    {

        cout << old_people << endl;
    }

    return 0;
}



#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
int A[N];
int B[N];
vector<int> pos;

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &A[i]);
    }
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &B[i]);
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (A[i] == B[j])
            {
                pos.push_back(i);
            }
        }
    }

    sort(pos.begin(), pos.end());

    for (int i = 0; i < pos.size(); i++)
    {
        cout << A[pos[i]] << " ";
    }

    return 0;
}


活动打卡代码 AcWing 4268. 性感素数

#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;

bool is_prime(int x)
{
    if (x < 2)
    {
        return false;
    }
    else
    {
        for (int i = 2; i <= sqrt(x); i++)
        {
            if (x % i == 0)
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    if (is_prime(n))
    {

        int low_n = n - 6;
        int high_n = n + 6;
        if (is_prime(low_n))
        {
            cout << "Yes" << endl;
            cout << low_n << endl;
        }
        else if (is_prime(high_n))
        {
            cout << "Yes" << endl;
            cout << high_n << endl;
        }
        else
        {
            cout << "No" << endl;
            while (n++)
            {
                if (is_prime(n) && (is_prime(n + 6) || (is_prime(n - 6))))
                {
                    cout << n << endl;
                    break;
                }
            }
        }
    }
    else
    {
        cout << "No" << endl;
        while (n++)
        {
            if (is_prime(n))
            {
                if (is_prime(n - 6) || is_prime(n + 6))
                {
                    cout << n << endl;
                    break;
                }
            }
        }
    }
    return 0;
}



#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;

bool is_prime(int x)
{
    if (x < 2)
    {
        return false;
    }
    else
    {
        for (int i = 2; i <= sqrt(x); i++)
        {
            if (x % i == 0)
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    if (is_prime(n))
    {

        int low_n = n - 6;
        int high_n = n + 6;
        if (is_prime(low_n))
        {
            cout << "Yes" << endl;
            cout << low_n << endl;
        }
        else if (is_prime(high_n))
        {
            cout << "Yes" << endl;
            cout << high_n << endl;
        }
        else
        {
            cout << "No" << endl;
            while (n++)
            {
                if (is_prime(n) && (is_prime(n + 6) || (is_prime(n - 6))))
                {
                    cout << n << endl;
                    break;
                }
            }
        }
    }
    else
    {
        cout << "No" << endl;
        while (n++)
        {
            if (is_prime(n))
            {
                if (is_prime(n - 6) || is_prime(n + 6))
                {
                    cout << n << endl;
                    break;
                }
            }
        }
    }
    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

#include <iostream>
#include <algorithm>

// 滑动窗口 单调队列

using namespace std;

const int N = 1e6 + 10;

// 队头
int head;
// 队尾
int tail;

// 单调队列 其中存放的是 元素下标 也就是当前窗口中所有元素的下标
int queue_arr[N];

//  存放数
int arr[N];

void init()
{
    //对 队列的定义进行初始化
    head = 0;
    tail = -1;
}

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    //不要忘记初始化
    init();

    //首先计算最小值 一次输出最小值
    for (int i = 0; i < n; i++)
    {
        // 保证当前 窗口中的值个数正确
        // 也就是 queue_arr 中 队头元素的下标 不能比 当前窗口最左侧的下标小
        // 即 当前队头已经不再滑动窗口中 故需要将队头移动
        //  同时队列中有元素
        if (i - k + 1 > queue_arr[head] && head <= tail)
        {
            // 出队
            // 因为一次for循环 最多出队一个元素 故可以用if 无需用 while
            head++;
        }
        // 若当前要队尾的元素  >= 即将进来的元素
        // 表面当前的队尾 有生之年都不可能成为最小值 因为 当前队尾一定比即将进来的元素先出队
        // 故当前队尾无需考虑 直接删除即可
        while (head <= tail && arr[queue_arr[tail]] >= arr[i])
        {
            tail--;
        }
        // 将当前元素放入 如此形成单调递增队列 最小的元素在队头
        queue_arr[++tail] = i;
        // 保证至少看过 k 个元素  根据题意 到第k 个元素才输出
        if (i >= k - 1)
        {
            cout << arr[queue_arr[head]] << " ";
        }
    }

    cout << endl;

    // 重新初始化 head和 tail
    init();

    // 找最大值 只需要进行逆运算即可
    for (int i = 0; i < n; i++)
    {
        // 若队列中的队头不在滑动窗口的下届
        if (i - k + 1 > queue_arr[head] && head <= tail)
        {
            head++;
        }
        // 在这里进行逆运算 形成单调递减的队列
        while (head <= tail && arr[queue_arr[tail]] <= arr[i])
        {
            tail--;
        }
        queue_arr[++tail] = i;
        if (i >= k - 1)
        {
            cout << arr[queue_arr[head]] << " ";
        }
    }
    return 0;
}


活动打卡代码 AcWing 830. 单调栈

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int stack_arr[N];
int top = -1; //初始化为 -1

// 单调栈的做法
// 维持一个栈 保证该栈的元素 始终是递增的 那么当找到比 当前元素小的 则一定是栈顶
int main()
{
    int n;
    cin >> n;
    int x;
    for (int i = 0; i < n; i++)
    {
        // 输入当前元素 从而寻找当前元素前面第一个比其小的数
        cin >> x;
        // 当栈不为空 且当前栈顶元素比 x 大
        while (top != -1 && stack_arr[top] >= x)
        {
            // 那么当前栈顶则不符合要求 需要往下寻找更小的数
            // 并且该栈顶元素也不再需要,因为有一个更小的数 x 后面元素肯定先看到 x
            // 因为 索引上 x > 当前top 且 数值上 x < 当前top
            top--;
        }
        // 注意这里与单调队列不同
        // 因为要先找到 当前元素左边的第一个小的 故需要先进行输出top 再把当前元素放入
        if (top != -1)
        {
            cout << stack_arr[top] << " ";
        }
        else
        {
            cout << -1 << " ";
        }
        //并且将当前 x 放入单调栈 为后面所需要而使用
        top++;
        stack_arr[top] = x;
    }
    return 0;
}



可以自己画图理解 注释很详细

#include <iostream>
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <string>

using namespace std;

// 定义符号优先级
unordered_map<char, int> h{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

// 操作数栈
stack<int> num;

// 符号栈
stack<char> op;

void evaluate()
{
    // 注意这里符号的顺序 由于涉及到减法  所以先pop出来的数 应该是减数 也就是 b
    int b = num.top();
    num.pop();

    int a = num.top();
    num.pop();

    char operate = op.top();
    op.pop();

    // 用于存放本次计算结果
    int res;

    if (operate == '+')
    {
        res = a + b;
    }
    else if (operate == '-')
    {
        res = a - b;
    }
    else if (operate == '*')
    {
        res = a * b;
    }
    else
    {
        res = a / b;
    }
    num.push(res);
}

int main()
{
    string s;
    cin >> s;

    for (int i = 0; i < s.size(); i++)
    {
        //如果当前是数字
        if (isdigit(s[i]))
        {
            int x = 0; // 用于存放当前数字
            int j = i; // 看后面是否也是数字
            while (j < s.size() && isdigit(s[j]))
            {
                // 一定注意 - '0'
                x = x * 10 + s[j] - '0';
                j++;
            }
            num.push(x);
            //将i进行归为 因为for循环中 i会++ 所以这里应该归为到数字的最后一位
            i = j - 1;
        }
        //左括号无脑加入
        else if (s[i] == '(')
        {
            op.push(s[i]);
        }
        // 遇到右括号
        else if (s[i] == ')')
        {
            // 则从右往左进行计算
            //从括号 从右往左计算 因为优先级高的在栈的高处
            while (op.top() != '(')
            {
                evaluate();
            }
            //将左括号出栈
            op.pop();
        }
        else
        {
            //想象成树 优先级高的 要先算
            // 这里优先级 是指计算中应该的顺序
            // 用while 循环把优先级高的先算完
            while (op.size() && h[op.top()] >= h[s[i]])
            {
                evaluate();
            }
            op.push(s[i]);
        }
    }

    while (op.size())
    {
        evaluate();
    }

    cout << num.top() << endl;

    return 0;
}


活动打卡代码 AcWing 829. 模拟队列

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int queue_arr[N];
int head, tail;

void init()
{
    head = 0;
    tail = -1;
}

void push(int x)
{
    tail++;
    queue_arr[tail] = x;
}

void pop()
{
    head++;
}

void empty()
{
    if (head <= tail)
    {
        cout << "NO" << endl;
    }
    else
    {
        cout << "YES" << endl;
    }
}

void query_head()
{
    cout << queue_arr[head] << endl;
}

int main()
{
    int m;
    string op;
    int x;
    cin >> m;
    init();
    while (m--)
    {
        cin >> op;
        if (op == "push")
        {
            cin >> x;
            push(x);
        }
        else if (op == "pop")
        {
            pop();
        }
        else if (op == "empty")
        {
            empty();
        }
        else
        {
            query_head();
        }
    }

    return 0;
}