头像

Immelon




离线:1天前


最近来访(4)
用户头像
.lml.
用户头像
codecloud
用户头像
小郑同学
用户头像
khalil

活动打卡代码 AcWing 790. 数的三次方根

Immelon
5天前

思路:二分

#include <iostream>

using namespace std;

const double eps=1e-8;
double n;

int main(void)
{
    cin>>n;
    double l=-10000.0, r=10000.0;
    while(r-l >=eps)
    {
        double mid=(l+r)/2;
        if((mid*mid*mid)<=n) l=mid;
        else r=mid;
    }
    printf("%6f", l);
    return 0;
}

需要注意的地方
1. 各处都应当用浮点数
2. 浮点数除以二不能用>>1
3. 输出格式用稍微简单些的



活动打卡代码 AcWing 788. 逆序对的数量

Immelon
5天前

思路:归并排序在归并时,mid 的左右两侧都是有序的,如果左侧j位置元素先加入了辅助数组,则左侧[i, mid]的元素都与当前 j 位置的元素构成逆序对(个数为 mid-i+1 ),将逆序对个数加到本次合并的总逆序对数 上,直至归并结束。
递归的思路是一个区间的逆序对数量等于左右两个区间的逆序对数量之和再加上此次合并的逆序对数

#include <iostream>

using namespace std;

typedef long long LL;
const int N=1000010;
int n;
int q[N], tmp[N];

LL merge_sort(int q[], int l, int r)
{
    if(l>=r) return 0;
    int mid= (l+r) >> 1;
    LL res = merge_sort(q, l, mid)+merge_sort(q, mid+1, r);

    int i=l, j=mid+1, k=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else
        {
            res+=mid-i+1;
            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 res;
}
int main(void)
{
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &q[i]);
    cout<<merge_sort(q, 0, n-1)<<endl;
    return 0;
}

需要注意的地方
1. res 是由三部分组成
2. 合并时 j 位置先加入到辅助数组意味着当前 i 位置的值比 j 位置的值大,又因为左侧和右侧都是升序的,则左侧总共有 mid-i+1 个数与q[j]组成逆序对



活动打卡代码 AcWing 786. 第k个数

Immelon
6天前

思想:快速选择,每次对区间进行排序,并停留到一个中间位置(非严格意义“中间”),判断第k个小的值在其左侧还是右侧,然后对这半个区间进行排序(如果是右侧,则k减去左侧区间长度sl,因为它是右侧第k-sl个最小的),最终返回l==r的这个长度为1的区间,这个数就是整体上第k小的值。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;
int n, m;
int q[N];

int quick_sort(int l, int r, int k)
{
    if(l>=r) return q[l];
    int x=q[(l+r) >> 1];
    int 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]);
    }
    int sl=j-l+1;
    if(k<=sl) quick_sort(l, j, k);
    else quick_sort(j+1, r, k-sl);
}
int main(void)
{
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++) scanf("%d", &q[i]);
    cout<<quick_sort(0, n-1, m);
    return 0;
}

需要注意的地方
1. 快排中是while(i<j)q[i]<x、和if(i<j)
2. sl=j-l+1,j是前后指针相遇的位置
3. 如果结果在右侧,则其是第k-sl个最小的



活动打卡代码 AcWing 787. 归并排序

Immelon
6天前

模板做法

#include <iostream>

const int N=1e6+10;
int n;
int q[N],tmp[N];

using namespace std;

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


活动打卡代码 AcWing 789. 数的范围

Immelon
6天前

先用二分找左边界,再用二分找右边界

#include <iostream>

using namespace std;

const int N=1000010;
int n, m;
int q[N];

int main(void)
{
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++) scanf("%d", &q[i]);
    while(m--)
    {
        int x;
        scanf("%d", &x);
        // 先二分寻找左边界
        int l=0, r=n-1;
        while(l<r)
        {
            int mid= l+r >> 1;
            if(q[mid]>=x) r=mid;
            else l=mid+1;
        }
        if(q[l]!=x) cout<<"-1 -1"<<endl;
        else
        {
            cout<<l<<" ";
            int l=0, r=n-1;
            while(l<r)
            {
                int mid=l+r+1 >> 1;
                if(q[mid]<=x) l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}



Immelon
6天前

主要讲了三个基础算法的思想和模板,以及一些例题

基础算法思想和模板

快速排序

思想:对于所要排序的区间,设置两个指针为 i(初始值为 l-1 ) 和 j(初始值为 r+1 ),以及一个枢纽值(一般取中间位置的值),将 i 和 j 移动到可以进行交换的地方(i 位置的值大于枢纽值时可交换,j 位置的值小于枢纽值时可交换),进行交换,直至 i 与 j 相遇( 满足i>=j )。
然后对由i(或者 j )分割开的左右两个区间分别进行快速排序。

#include <iostream>
#include <algorithm>

const int N = 1000010;
int n;
int q[n];

using namespace std;

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, i);
    quick_sort(q, i+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=-; i<n; i++) printf("%d ", q[i]);

    return 0;
}

模板中需要注意的几个边界问题
1. 循环的大条件是while(i<j),而不是while(i<=j)
2. 判断左移和右移是<>而不是<=>=
以上两个地方从思路上来考虑没有问题,但是在实际数据中运行可能会导致无限循环,所以要记得这两个地方。

归并排序

思想:对于所要排序的区间,设置两个指针 i(初始值为区间左边界 l)和 j(初始值为区间中间位置 l+r>>1),两者后移时将所指向的较小值放入 tmp[] 数组,直至 i==mid 或者 j==r,然后把左半边或者右半边剩余的全部移进 tmp[] 数组,实现排序,最后把 tmp[] 数组中的元素拷贝到原数组的[l, r]区间。
注意,递归的位置在排序之前。

#include <iostream>

const int N=1e6+10;
int n;
int q[N],tmp[N];

using namespace std;

void merge_sort(int q[], int l, int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    int i=l, j=mid+1, k=0;
    merge_sprt(q, l, mid);
    merge_sort(q, mid+1, r);
    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=-; i<n; i++) printf("%d ", q[i]);

    return 0;
}

模板中需要注意的几个问题
1. 递归在排序之前
2. i=l, j=mid+1
3. tmp[] 数组从0开始存放和拷贝

二分查找

思想:对于一个区间,如果某种性质能够将区间分为前后两个部分(check()为True和False),那么可以用递归的方式找到满足与不满足的分界点,递归的方式是逐步地缩小查找的区间,并且每次只check此区间中间位置的值是否满足,注意这里“递归”的实现是循环。

bool check(int x) // 检查是否满足某种性质
{
    /* ... */
}

int bsearch_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 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;
}

bool check(double x)// 检查是否满足某种性质
{
    /* ... */
}

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;
    while(r-l>eps)
    {
        double mid = (l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    return l;
}

需要注意的问题
1. 如果所写的check()函数为 True 时,需要将 l 更新为 mid,那么 mid 应该用 l+r+1 >> 1(原因可能是正整数移位取整是向下取整,不+1 可能会导致 l=l,从而导致无无限循环)



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

Immelon
8天前

快速排序

思想:对于所要排序的区间,设置两个指针为 i(初始值为 l-1 ) 和 j(初始值为 r+1 ),以及一个枢纽值(一般取中间位置的值),将 i 和 j 移动到可以进行交换的地方(i 位置的值大于枢纽值时可交换,j 位置的值小于枢纽值时可交换),进行交换,直至 i 与 j 相遇( 满足i>=j )。
然后对由i(或者 j )分割开的左右两个区间分别进行快速排序。

#include <iostream>
#include <algorithm>

const int N = 1000010;
int n;
int q[n];

using namespace std;

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, i);
    quick_sort(q, i+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=-; i<n; i++) printf("%d ", q[i]);

    return 0;
}

模板中需要注意的几个边界问题
1. 循环的大条件是while(i<j),而不是while(i<=j)
2. 判断左移和右移是<>而不是<=>=
以上两个地方从思路上来考虑没有问题,但是在实际数据中运行可能会导致无限循环,所以要记得这两个地方。



新鲜事 原文

Immelon
8天前
# 第一章 基础算法(一) 笔记 ``` # ```


新鲜事 原文

Immelon
17天前
AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/79592/


活动打卡代码 AcWing 4276. 擅长C

Immelon
1个月前

这个题目对于输入输出格式的处理要求比较多
考虑的解法:用7行5列的矩阵存储各个字母,对于输入的句子,用分隔符分割出单词,存储到数组字符串中。对于打印,使用一个大的二维数组作为输出板子,依次填入字母板子和空格,最后打印即可。

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

using namespace std;

char letters[26][7][6]; // 存储大写字母;
bool is_first = true;

void output(string word){
    if(word.empty()) return;
    if(is_first) is_first=false;
    else cout<<endl;

    // 每个单词需要 7 行 60 列(5列*10单词+9个空列+1个\0列)的输出板子;
    char str[7][60] = {0};
    // 把 word 对应的单词板子放进输出板子;
    for(int i=0; i<word.size(); i++){
        for(int j=0; j<7; j++){
            for(int k=0; k<5; k++){
                // word 中第 i 个字母的起始列位置为 i*6 ,后续每一列为 i*6+k
                str[j][i*6+k] = letters[word[i]-'A'][j][k];
            }
        }
    }

    // 把所需要的空列放进输出板子:从第二个单词开始,每个单词前面需要有一列空列;
    for(int i=1; i<word.size(); i++){
        for(int j=0; j<7; j++){
            str[j][i*6-1] = ' ';
        }
    }

    // 打印整个输出板子,每次打印一行;
    for(int i=0; i<7; i++){
        cout<<str[i]<<endl;
    }
}
int main(){
    // 把字母存进三维数组;
    for(int i=0; i<26; i++){
        for(int j=0; j<7; j++){
            cin>>letters[i][j];
        }
    }
    string word;
    char c;
    while((c=getchar())!=-1){
        // 一个完整的单词的输入和输出,最后重置此单词
        if(c>='A'&&c<='Z') word+=c;
        else{
            output(word);
            word="";
        }
    }
    output(word);
    return 0;
}