头像

陌_5




离线:5天前



陌_5
10天前

快速排序

参考题目:

Acwing 785.快速排序

Acwing 786.第k个数

快排思路——分治思想:

  1. 确定分界点:q[l] 、 q[l+r/2] 、 q[r] 或随机点,一般选择q[l+r/2]

  2. 调整区间:将区间根据分界点划分为两部分,左边那部分小于等于分界点,右边那部分大于等于分界点

  3. 对划分的区间进行递归操作

易错点:

  • 双指针操作部分,只可以使用do while而不能使用while do

因为在交换之后左右指针需要先改变再判断所以要先do后while,不然遇到相等情况,则会进入无限循环。

例:头尾指针还有分界点的值相等:{2,2}

  • 递归排序的时候选用i或选用j作为递归的参数跟mid向上或向下取取整是有关系的。

向上取整要使用i:quick_sort(a, l ,i-1);quick_sort(a,i,r);

向下取整要使用j:quick_sort(a, l ,j);quick_sort(a,j+1,r);

例:两个数的时候,如:{1,2}

要说明两点:

  1. 最后左右指针停留的位置。有两种情况:

    第一种:如果序列个数为偶数,那么左右指针是交叉的

    第二种:如果序列个数为奇数,那么左右指针为重合的

  2. mid的取值,向上跟向下取整,对于特例:区间只有两个数的时候

    向下取整mid指向第一个数,上取整指向第二个数

说明向下取整的使用i指针出错的情况:

区间[1,2],最后左右指针停留的位置在1

所以左边界为使用i表示为:[l,i-1] = [1,0]
右边界:[i,r] = [1,2] 跟之前一样,对[1,2]进行划分之后还是[1,2]所以右区间会进入无穷循环

同理,向上取整,且取右边界也会发生同样的情况

易错点总结:

  1. 交换之后指针要改变,所以使用do while。例:头尾指针还有分界点的值相等:{2,2}
  2. 区间结束后头尾指针不是重叠就是交叉,区间判断跟分界点取值上下取整有关。例:只有两个数的时候:{1,2}

代码

#include<iostream>
using namespace std;
const int N = 100010;

int a[N];
void quick_sort(int a[],int l,int r)
{
    //递归终止条件,区间为一个数的时候
    if(l >= r)return ;
    // 确定分界点,左右指针初始化
    int mid = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    // 调整区间:左区间<= mid   右区间>= mid
    while(i < j)
    {
        do i++; while(a[i] < mid);//寻找不符合左区间的值
        do j--; while(a[j] > mid);//去渣不符合有区间的值
        if(i < j)swap(a[i], a[j]);//交换
    }
    quick_sort(a, l ,j);//递归对左区间进行排序
    quick_sort(a,j+1,r);//递归对右区间进行排序
}

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

    quick_sort(a,0,n-1);

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



陌_5
11天前

Acwing 422.校门外的树

题目链接:

Acwing 422.校门外的树

思路:区间合并

  1. 将所有重叠的区间进行合并。例如:[1,5]和[3,7] 合并为 [1,7]
  2. 计算区间之间的距离大小:ed - st + 1
  3. 总长度减去所有区间的大小。

区间合并的过程:

  1. 将所有区间按照左边界进行从小到大的排序

  2. 使用st指针表示左边界,ed 指针表示右边界

  3. 然后遍历区间进行判断:
    如果第二个区间的左边界大于第一个区间的右边界,则说明这是两个完全分开的区间
    如果小于或等于第一个区间的右边界,则说明这两个区间的是有相交或相邻的

  4. 如果是相交或相邻,就将第一个区间的右边界改成第二个区间的右边界,合并为一个区间

代码:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 105;

vector<pair<int,int>> mes,res;
int l,m;

int main()
{
    cin>>l>>m;

    for(int i = 0; i < m; i ++)
    {
        int a ,b;
        cin>>a>>b;
        mes.push_back({a,b});
    }

    int st,ed;
    st = ed = -1;
    sort(mes.begin(),mes.end());
    for( int i = 0; i < m; i ++)
    {
        if(mes[i].first > ed){
            if(st != -1){
                res.push_back({st,ed});
            }
            st = mes[i].first;
            ed = mes[i].second;
        }else{
            ed = max(ed,mes[i].second);
        }
    }
    if(st != -1)res.push_back({st,ed});

    l++;
    for(int i = 0; i < res.size(); i++ )
    {
        l = l - (res[i].second - res[i].first) - 1;
    }
    cout<<l<<endl;
    return 0;
}



陌_5
11天前

Acwing 680.剪绳子

题目链接:

Acwing 680.剪绳子

解题步骤:

算法:二分

通过二分,在绳子的范围内,找出符合要求的绳子长度。

二分是通过折半查找的方式最终找到需要的结果。所以每次这种都将折中后的长度mid进行判断。

对每条绳子进行判断,看能剪出几条mid长度的绳子,累加如果超过或等于需要的绳子数量即满足要求。

二分开始的状态:l = 0; r = 100000;mid = (l+r)/2;

代码:

#include<iostream>
#include<algorithm>

using namespace std;

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

//判断是否满足要求
bool check(double mid)
{
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        res += q[i] / mid;
        if(res >= m)return true;
    }
    return false;
}

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

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

    double l,r,mid;
    l = 0, r = 1e9;

    // 二分查找符合条件的值
    while(r - l >= 1e-3)
    {
        mid = (l + r) / 2;
        // 如果当前值过小就取大的那部分,否则取小的那部分
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2f\n",l);

    return 0;
}




陌_5
11天前

Acwing 1346.回文平方

题目链接:

Acwing 1346.回文平方

解题步骤:

核心:1.进制转换 2.回文判断

进制转换:

十进制转其他进制:短除法

数字转字符串(进制范围:2≤B≤20)

短除法:

image-20210224210213719

短除法的操作有三个步骤:

  1. 求余
  2. 求商
  3. 对结果进行翻转

回文判断:

第一种:将结果进行翻转,与原理的结果进行对比,如果一样则是回文

第二种:双指针,头尾对比,有一个不同则不是回文

代码:

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

using namespace std;

// 数字转字符串
char get(int a)
{
    char res;
    if(a <= 9){
        res = '0' + a;
        return res;
    }else{
        res = 'A' + (a-10);
        return res;
    }
}

// 短除法:10进制转其他进制
string base(int a,int b)
{
    string res;
    while(a)
    {
        res += get(a % b);
        a /= b;
    }
    reverse(res.begin(),res.end());
    return res;
}

bool check(string a)
{
    string tmp = a;
    reverse(a.begin(),a.end());
    if(tmp == a)return true;
    return false;
}

int main()
{
    int b;
    cin>>b;

    for(int i = 1; i <= 300; i ++)
        if(check(base(i * i,b)))
            cout<<base(i,b)<<' '<<base(i*i,b)<<endl;

    return 0;
}



陌_5
11天前

Acwing 1113.红与黑

题目链接:

Acwing 1113.红与黑

思路:宽搜

本题宽搜的要点:

  1. 起点:输入数据时判断@的坐标,就是起点
  2. 终点:没有终点,直到无路可走,即结束
  3. 搜索的方式:上下左右四个方向,如果是符号. 即可行走

宽搜的步骤:

  1. 起点坐标插入队列,并标记
  2. 获取队头坐标,并弹出
  3. 以该点进行搜索,符合条件的坐标插入队列,并标记
  4. 循环,直到终点

代码:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> site;
const int N = 25;
char q[N][N];

int main()
{
    int n,m;
    cin>>n>>m;
    while( n != 0 && m != 0)
    {
        int res = 0;
        queue<site> que;
        // 上右下左
        int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};

        for(int i = 0; i < m; i++ )
            for(int j = 0; j < n; j ++)
            {
                char tmp;
                cin>>tmp;
                q[i][j] = tmp;
                //第一步:将起点坐标插入队列,并标记
                if(tmp == '@'){
                    que.push({i,j});
                    q[i][j] = '#';
                }
            }
        //第四步:直到队列为空,表示没有任何的坐标可以通过,即表示结束
        while(!que.empty())
        {
            //第二步:获取队头,弹出
            site s = que.front();
            que.pop();
            res ++;
            //第三步:搜索方式:以该点进行搜索,符合条件插入队列,并标记
            for(int i = 0; i < 4; i ++)
            {
                int a = s.first,b = s.second;
                a += dx[i],b += dy[i];
                if(q[a][b] == '.')
                {
                    que.push({a,b}); 
                    q[a][b] = '#';
                }
            }
        }
        cout << res << endl;
        cin>>n>>m;
    }
    return 0;
}



陌_5
12天前

Acwing 756. 蛇形矩阵

题目链接:

Acwing 756. 蛇形矩阵

例题:

输入样例:
3 3
输出样例:
1 2 3
8 9 4
7 6 5

思路:

误区:

一开始陷入的误区,之前操作二维数组,一般都是一层循环控制行,一层循环控制列。

然后控制的时候一直都是行不变,然后对列进行操作,这样一行一行下去。

甚至都没想到列不变行变来对行进行操作。

可以的操作:

  1. 列不变,然后一层循环,对一列进行操作
  2. 一层循环直接对行列进行操作(也可以将二维数组看成一维数组)

方法一:一层循环对行列进行全部操作

将二维数组的空间大小作为循环的次数。

一般循环的操作顺序是这样的:

image-20210223215957263

但是这不是我们想要的,我们需要的是像深搜一样,不同的是开头是在左上角,结尾是在最中间而已。

然后搜索的操作是一样的,碰到边界,进行判断,自动转向

image-20210223220357156

方法二:一行一列的循环操作,直到0

设置四个方向的边界,除非边界的之间的距离为0,说明已经到一个点了。不然就是一行一个循环,一列一个循环,慢慢圈起来

image-20210223221133070

四个循环之后已经走了一环边界缩小,重复下去,直到最后一个点;

代码:方法一

#include<iostream>
using namespace std;
const int N = 105;
// 存放矩阵
int q[N][N];


int main()
{
    int n,m;
    cin>>n>>m;
    // 控制方向,利用循环跟判断控制方向,上右下左
    int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1},d = 1;

    // 控制行走的坐标
    int x = 0,y = 0;

    // 模拟蛇在走,总共走n*m格
    for(int i = 1; i <= n*m; i++)
    {
        // 赋值
        q[x][y] = i;
        // 将下一步的坐标赋值给a,b
        int a = x + dx[d],b = y + dy[d];
        // 判断如果碰壁,
        if(q[a][b] != 0 || a >= n || b >= m || a < 0 || b < 0)
        {
            d = (d+1) % 4;

            a = x + dx[d],b = y + dy[d];
        }

        x = a, y = b;
    }

    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cout<<q[i][j]<<' ';
        cout<<endl;


    return 0;
}



陌_5
12天前

Acwing 898 数字三角形

题目链接:

Acwing 898 数字三角形

例题:

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

思路:

由题可知,要到最后一层的时候,所走的路径之和为最大,那么有两个需求:

第一:是走到最后一层

第二:是求最大的

那么最后一层的结果有很多,如例题有五个节点都是最终结果,而且路径不一样,同一个结果的路径之和也不一样。

有如下图,到达同一个节点,但是由于路径不同,其结果也不同。

image-20210223210739356

步骤:

  1. 要先求出最后一层每一个节点的最优解
  2. 从最后一层的所有节点的最优解中取最大

第一步:求最后一层每一个节点的最优解(核心):

比如要求第二个节点的最优解,那么只要保证第四层能够通往他的两个节点是最优解即可:

image-20210223213104023

同理可得,第三层的节点的最优解亦是如此:

image-20210223213339318

由此可以退出状态公式:dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + q[i][j];

代码:

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N = 510;

int p[N][N];
int dp[N][N];

int main()
{
    int n;
    cin>>n;
    //初始化
    for(int i = 0; i < N ; i++ )
        for (int j = 0 ; j < N; j ++)
            p[i][j] = dp[i][j] = -10001;
    //输入
    for(int i = 1; i <= n ; i++ )
        for (int j = 1 ; j <= i; j ++)
            cin>>p[i][j];
    //记录状态
    dp[1][1] = p[1][1];
    //递推
    for( int i = 2; i <= n; i ++)
        for( int j = 1; j <= i; j ++)
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + p[i][j];
    //从最后一层中寻找最优解
    int res = -10001;
    for(int i = 1; i <= n; i ++)
        res = max(dp[n][i],res);
    cout<<res<<endl;
    return 0;
}



陌_5
12天前

Acwing 104 货仓地址

题目链接:

Acwing 104 货仓地址

思路:

由图可得,假如有两点,要在数轴上面选择一点,让这点到这两个点的距离之和最小

那么有三种情况:如下图演示可得,将这个点选择在两点的中间,则这个距离最短。

那么如果有奇数点呢,那么就将这个点选在最中间的那个点上面。

所以可以推出,这个点要选择在所有点的中间。

仓货地址

代码:

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1000010;

int nums[N];

int main()
{
    int n;
    int res = 0;
    cin>>n;
    for(int i = 0; i < n; i++ )cin>>nums[i];
    sort(nums,nums+n);
    for(int i = 0; i < n; i++)
    {
        //nums[n/2] 为最中间那个点,每一个点剪去最中间的点的和便是结果
        int tmp = nums[i] - nums[n/2];
        tmp = tmp > 0 ? tmp : tmp * (-1);
        res += tmp;
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 126. 最大的和

陌_5
13天前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 105;

int p[N][N];

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

    // 输入并且对列进行前缀和
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j++)
        {
            int x;
            cin>>x;
            p[i][j] = p[i-1][j] + x;
        }

    int res = -400;

    // 前面两重循环用于遍历纵方向,以i为结尾的各个区间,然后取得最大值
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= i; j++)
        {
            // f是用于行向dp时,存储状态的变量
            int f = 0;
            // 第三重循环用dp的方式求行方向上面的最大值
            for(int k = 1; k <= n; k++)
            {
                //获取列上区间的和
                int w = p[i][k] - p[j-1][k];
                f = max(f,0) + w;
                res = max(f,res);
            }
        }
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

陌_5
13天前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 105;

int q[N][N];
int dp[N][N];

void work()
{
    int n,m;
    cin>>n>>m;

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j++)
            cin>>q[i][j];

    dp[1][1] = q[1][1];

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + q[i][j];
        }
    }
    cout<<dp[n][m]<<endl;



}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        work();
    }
    return 0;
}