头像

种花家的蒟蒻

$$\href{https://www.acwing.com/blog/content/24766/}{个人主页}$$ 种花家族 蒟蒻粉丝团




离线:9小时前


最近来访(1116)
用户头像
syon
用户头像
CyanFishhh
用户头像
玄淇
用户头像
Briefly
用户头像
垫底抽風
用户头像
HeXing
用户头像
Fatin
用户头像
太雪菜
用户头像
watermelon_Learn
用户头像
不高兴的兽奶
用户头像
1234567869
用户头像
六月的雨
用户头像
lofty
用户头像
Dec.
用户头像
Rz_Z
用户头像
救赎之道就在其中
用户头像
是一个一个一个CE自动机啊啊啊啊啊啊啊啊啊啊啊啊啊
用户头像
味同良辰
用户头像
zhyou2
用户头像
LonelyLove

新鲜事 原文

鲁迅原名李大钊,浙江周树人,是著名的法西斯音乐家,一生有2000多项发明,被称为太空步的创始 人。 他拥有一个好嗓子,小学时就凭借着90分钟跑100米的优异成绩考上了新东方烹饪学校! 毕业后 成功进入富士康苦心练习勃鸡, 他擅长110米栏,左手反打技术高超,拿手全垒打,大灌篮,“后空 翻180度右旋体360度后蹬地翻转720度”是他的经典动作, 更难得可贵的是他落地没有水花。 他还是 恶魔果实能力者,传说中的三忍之一,曾大闹天宫,后改邪归正,统一三国, 传说他有107个弟 兄,个个铜头铁臂,面目狰狞,这便是羊村的起源, 他生平淡泊名利,后遇到高人阿凡达的指点, 打死了白雪公主 与七个小矮人快乐的生活在一起! 并写了名侦探柯南的故事。 名侦探柯南讲述的是要 成为海贼王的八神太一收服了皮卡丘并登上创界山启动光能使者打败了鲨鱼辣椒, 然后跟多啦A梦一 起通过黄金十二宫收集七个葫芦娃召唤神龙复活二代火影, 但最终为了保卫M78星云而成为了羊村村 长, 同蓝精灵们一起抵抗光头强的入侵的故事。 然而,鲁迅原名李大钊,浙江周树人,曾经锻造五色神石补天,因杀死西门庆等原因,上梁山当了土 匪,后遇到高人阿凡达的指点, 收买阿童木打死了白雪公主,与七个小矮人快乐的生活在一起。!并 写了名侦探柯南的故事。 名侦探柯南讲述的是要成为海贼王的八神太一收服了皮卡丘并登上创界山启 动光能使者打败了鲨鱼辣椒, 然后跟多啦A梦一起通过黄金十二宫收集七个葫芦娃召唤神龙复活二代 火影,但最终为了保卫M78星云而成为了羊村村长,同蓝精灵们一起抵抗光头强的入侵的故事。她还写 了《时间简史》,后来因抽了龙王三太子的筋,以命偿命。 后被太乙真人救活,又送了他不少法宝。 然后又创建了‘浴谷’,‘浴谷’是一个收集变形金刚一起打小怪兽的网站。 当时正值小黄人入侵时 期,于是,她批量生产大白,成功抵御入侵,再一次拯救了人类!当她晚年时,热衷于炼丹,炼时经 常失败 ,一大堆毒丹,当最后炼出长生不老之丹时,因老花眼吃错药而死。



逆序对的数量

这题一看就可以用暴力做,但是数据量要再大一点,就会TLE。

于是,我们就要调整一下思路。

解释:在分治后的每一层合并中顺便求出逆序对数量是这个题想法的由来,归并排序分治我们求的是从小到大的顺序,我们所求的逆序对恰好是逆序数量,与归并排序不谋而合。

这种方法当然可以,这种方法有一个名字:二路归并

这种算法跟二分有点像,又跟归并排序的原理有点像,所以,我们可以用 归并排序的模版做,根据规则调整就行。

如 设有数列{6,202,100,301,38,8,1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;

第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;

第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

总的比较次数为:3+4+4=11,;

逆序数为14;

于是,我们可以写出代码了:

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100010;

int n;

int q[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 k=0;

    //归并的过程
    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++];
            res+=mid-i+1;
        }

    //扫尾
    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[i]=tmp[j];

    return res;
}

int main()
{
    cin>>n;

    for (int i=0;i<n;i++) cin>>q[i];

    cout<<merge_sort(0,n-1)<<endl;

    return 0;
}


新鲜事 原文

woc差一分!!!就差一分59分差一分晋级呜呜呜



二分之整数范围

在正式讲解之前,我们要知道二分是干啥用的

二分,其实就是一种查找算法,一般顺序查找的时间复杂度是o(n),而二分是提升时间复杂度的,可以将o(n)提升到o(logn)级别。一般二分查找分为两类:整数二分和实数二分。整数二分非常容易错,建议多研究。实数二分比较简单,一般大家琢磨琢磨就会了。

这题就是一个整数二分。

首先,我们知道,二分有两个模版:

int search_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
int search_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;
}

我们要根据不同的题目调用不同的模版

两个模版区别具体见 among大佬的闫总“二分查找算法”两个模板本质差别

那么,此题需要用什么模版呢?

仔细研究发现,这题要用第一个模版。

那么,把模版套入代码中就行了。

代码如下:

#include <iostream>
using namespace std;
const int maxn = 100005;
int n, q, x, a[maxn];
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
    while (q--) {
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] < x)  l = mid + 1;
            else    r = mid;
        }
        if (a[l] != x) {
            printf("-1 -1\n");
            continue;
        }
        int l1 = l, r1 = n;
        while (l1 + 1 < r1) {
            int mid = l1 + r1 >> 1;
            if (a[mid] <= x)  l1 = mid;
            else    r1 = mid;
        }
        printf("%d %d\n", l, l1);
    }
    return 0;
}



归并排序正解

首先,我们要了解归并排序是怎么实现的。

应该还是_分治_思想

那它怎么实现呢?

1.确定分界点

2.递归排序left、right

3.归并——合二为一 这也是步骤最最关键的部分

于是,我们就可以写出代码了:

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r);
int main()
{
    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>>1;
    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(i=l,j=0;i<=r;i++,j++)
        q[i]=tmp[j];
    return;
}



调整一下快速排序的模版即可

代码如下:

#include <bits/stdc++.h>
using namespace std;
int n, q, a[100010];
void quick_sort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    int i = l - 1, j = r + 1, x = a[mid];
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    quick_sort(1, n);
    cout << a[q];
    return 0;
}



在此之前宣布:算法基础课第二遍已经开始

以后,我再也不会氵题解了!我再也不会摆烂了!梦想重新启航!

这里是我的算法基础课笔记

我不光是给自己看,也是给大家看!

从此之后,我再也不是一位只会摆烂的蒟蒻了!

持续更新中ing~~~

我不求赞!只求和大家一起进步!

算法基础课笔记

1.基础算法

1.1 快速排序

1.2 第k个数

1.3 归并排序

1.4 逆序对的数量

1.5 数的范围

2.数据结构

3.搜索与图论

4.数学知识

5.dp

6.贪心




快速排序正解

首先我们都知道快速排序可以用系统函数解。

于是就产生了如下的代码:

#include <iostream>
#include <algorithm>//注意sort在algorithm头文件里

using namespace std;

const int N = 100010;//定义数组长度

int n;
int a[N];

int main(){
    cin >> n;//输入,当然scanf也没毛病
    for (int i = 0; i < n; i ++ ) cin >> a[i];//循环输入,当然从1开始也没毛病
    sort(a, a + n);//调用系统函数sort
    for (int i = 0; i < n; i ++ ) cout << a[i] << ' ';//循环输出,当然printf也没毛病
    return 0;
}

这种方法虽然好,但是无法通过面试,于是,我们就要手写sort函数

怎么写呢???

我们就可以用 分治 的思想:

1.确定分界点:q[l] q[(l + r) / 2] q[r] 随机

2.调整范围:我们需要找到一个分界点x,使得它左边的数都小于等于它,右边的数都大于等于它

3.递归处理左右两段:

(1).遍历q[l~r],如果q[i] <= x,就将x插到左边去,如果q[i] >= x,就将x插到右边去

(2).还原

于是,我们就产生了这样的代码:

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + 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);
}

int main()
{
    int n;
    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;
}


新鲜事 原文

啊啊啊啊啊,我又双叒叕忘打周赛啦!!!!!!


活动打卡代码 AcWing 2770. 方格取数

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

using namespace std;

typedef long long LL;

const int N = 1010;
const LL INF = 1e18;

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

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

    memset(f, -0x3f, sizeof f);
    f[1][0] = 0;

    for (int i = 1; i <= m; i ++ )
    {
        LL s = -INF;
        for (int j = 1; j <= n; j ++ )
        {
            s = max(s, f[j][i - 1]) + w[j][i];
            f[j][i] = max(f[j][i], s);
        }
        s = -INF;
        for (int j = n; j; j -- )
        {
            s = max(s, f[j][i - 1]) + w[j][i];
            f[j][i] = max(f[j][i], s);
        }
    }

    printf("%lld\n", f[n][m]);
    return 0;
}