头像

Hasity




离线:20小时前


最近来访(1033)
用户头像
无人圣地
用户头像
新人orz
用户头像
hellozmc
用户头像
野蛮生长
用户头像
万叶的狗
用户头像
羽佳
用户头像
一颗硫酸锌
用户头像
被自己菜醒
用户头像
LiquidFloy
用户头像
shark_big
用户头像
小张小张自作主张
用户头像
OJOJO
用户头像
Nigel
用户头像
人生如戏ba
用户头像
张凌云
用户头像
寄一心明月
用户头像
蟹老板_3
用户头像
咖啡不加糖
用户头像
xhQYm
用户头像
互联网十级冲浪选手


Hasity
30天前

什么是前缀和?

  • 数列的和时,Sn = a1+a2+a3+…an; Sn就是数列的前 n 项和。

  • 前缀和就是新建一个数组,新建数组中保存原数组前 n 项的和。

前缀和2.png


前缀和有什么用?

  • 快速求某个区间中所有元素的加和。例 S5 = a1 + a2 + a3 + a4 + a5; S2 = a1 + a2。所以可以通过 S5-S2 得到 a3+a4+a5 的值。

前缀和3.png


代码:

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];//保存原数组
int s[N];//保存前缀和
int main(){
    int n, m;
    cin >> n >> m;
    //从a[1]开始保存。a[0]是0
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    s[0] = 0;
    //计算前缀和
    for(int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + a[i];

    for(int i = 0; i < m; ++i){
        int l, r;//保存区间
        cin >> l >> r;
        //s[r] = a[1]+ ··· + a[r]
        //s[l - 1] = a[1]+ ··· + a[l - 1]
        //s[r] - s[l - 1] = a[l] + ··· + a[r]
        cout << s[r] - s[l - 1] << endl;
    }
}



Hasity
1个月前

什么队列?

  • 就是一个特殊的数组。这个数组,最前面叫队头,最后面叫队尾。只允许在最后面添加元素,只允许在最前面删除元素。

1.png


解题思路:

  • 用一个数组 q 保存数据。

  • hh 代表队头,q[hh] 就是队头元素, q[hh + 1] 就是第二个元素。

  • tt 代表队尾, q[tt] 就是队尾元素, q[tt + 1] 就是下一次入队,元素应该放的位置。

  • [hh, tt] 左闭右闭,代表队列中元素所在的区间。

  • 出队pop:因为 hh 代表队头,[hh, tt] 代表元素所在区间。所以出队可以用 hh++实现,hh++后,区间变为[hh + 1, tt]

  • 入队push:因为 tt 代表队尾,[hh, tt] 代表元素所在区间。所以入出队可以用 tt++实现,hh++后,区间变为[hh, tt + 1], 然后在q[tt+1]位置放入入队元素。

  • 是否为空empty:[hh, tt] 代表元素所在区间,当区间非空的时候,对列非空。也就是tt >= hh的时候,对列非空。

  • 询问队头query:用 hh 代表队头,q[hh] 就是队头元素,返回 q[hh] 即可。

2.png


代码

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

//[hh, tt] 之间为队列(左闭右闭)
int hh = 0;//队头位置
int tt = -1;//队尾位置
//操作次数
int m;
//操作方式
string s;

//入队:队尾先往后移动一格,再放入要插入的数据
void push(int x){
    q[++tt] = x;
}
//出队:队头往后移动一格
void pop(){
    hh++;
}
//[hh, tt]表示队列区间,当tt >= hh时,区间为空
void empty(){
    if(tt >= hh) cout << "NO" << endl;
    else cout << "YES" << endl;
} 
//hh指向队头,q[hh]代表队头元素
void query (){
    cout << q[hh] << endl;
}

int main(){
    cin >> m;
    while(m--){
        cin >> s;
        //入队
        if(s == "push"){
            int x;
            cin >> x;
            push(x);
        }
        //出队
        if(s == "pop"){
            pop();
        }
        //问空
        if(s == "empty"){
            empty();
        }
        //问队头
        if(s == "query"){
            query();
        }
    }
}



Hasity
1个月前

<= 点个赞吧

递归想法很容易想到,现在提一个找规律的算法。

通过题意可以得出以下结论:

  • 当把一个点染色后,他和它的儿子都被染色。

  • 根节点开始的颜色是:0

  • 因为目标颜色的范围是 1~n, 根节点肯定要染色。

再想一下:

  • 根节点染色后,他所有儿子节点变为和根节点一样的颜色。

  • 所以:只要儿子节点和父亲节点颜色不一样,就要染一次。

得出解题思路:只要数一数和父亲节点颜色不一样的节点有几个,答案就是几


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

using namespace std;
const int N = 2e4 + 10;
//p保存父节点编号,t保存目标颜色
int p[N],t[N];
int main()
{
    int n;
    cin >> n;
    p[1] = 0;
    for(int i = 2; i <= n; ++i)
    {
        cin >> p[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        cin >> t[i];
    }
    int res = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(t[i] != t[p[i]])//和父节点颜色不一样,就要染一次
        {
            res ++;
        }
    }
    cout << res << endl;
    return 0;
}




Hasity
2个月前

堆排序概念补充

  1. 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序, 它的最坏、最好、平均时间复杂度均为 O(nlogn), 它也是不稳定排序。

  2. 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值, 这种情况称为大顶堆,注意:没有要求结点的左孩子的值和右孩子的值的大小关系。

  3. 每个结点的值都小于或等于其左右孩子结点的值, 这种情况称为小顶堆。

  4. 大顶堆举例说明:
    20210320153023354.png

  5. 小顶堆举例说明:
    20210320153049609.png
  6. 一般升序采用大顶堆, 降序采用小顶堆。

基本思想

  1. 将待排序序列构造成一个大顶堆。

  2. 此时,整个序列的最大值就是堆顶的根节点。

  3. 将其与末尾元素进行交换, 此时末尾就为最大值。

  4. 然后将剩余 n-1 个元素重新构造成一个堆, 这样会得到 n 个元素的次小值。 如此反复执行, 便能得到一个有序序列了。

可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列了。

堆排序步骤图解

数组 {4,6,8,5,9},要求使用堆排序法,将数组升序排序(升序采用大顶堆,降序采用小顶堆)。

构造

  1. 将给定无序序列结构如下。20210320153153312.png

  2. 从最后一个非叶子结点开始,从右至左,从下至上进行调整。
    调整规则:找到该节点和他的所有儿子。如果该节点中存的值是找到节点值中的最大值,则不进行调整。如果不是,就将该节点的值和最大值进行交换,然后递归的调整和该节点交换值得那个节点。如下图:


  • 最后一个非叶子结点开始(也就是下面的 6 结点),从左至右,从下至上进行调整。6 有两个儿子:5 和 9,这三个值中 9 最大。6 和 9 交换。

20210320153221152.png

  • 因为 6 和 9 交换了,递归处理现在保存 6 的那个节点,发现它没有儿子,停止递归。

  • 找到第二个非叶节点4,由于[4,9,8]中9元素最大,4 和 9 交换。

20210320153251438.png

  • 因为 4 和 9 交换了,递归处理现在保存 4 的那个节点: 找到它的两个儿子:5, 6, 其中 6 最大,交换 4 和 6。

20210320153330130.png

  • 然后继续递归处理,发现现在保存4 的节点没有儿子,停止。

  • 此时,我们就将一个无序序列构造成了一个大顶堆。


排序

  1. 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。如下图:

  • 将堆顶元素 9 和末尾元素 4 进行交换。

20210320153411240.png

  • 重新调整结构(规则如上),使其继续满足堆定义。

20210320153445908.png

  • 再将堆顶元素 8 与末尾元素 5 进行交换,得到第二大元素 8。

20210320153510654.png

  • 后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序。

20210320153532768.png


总结

  1. 将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆。

  2. 将堆顶元素与末尾元素交换,将最大元素”沉”到数组末端。

  3. 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。


本题可以使用堆排序,构造小顶堆,然后输出堆顶,输出后把堆顶和堆尾交换。重复执行m次即可。

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

using namespace std;

const int N = 100010;

int a[N];//保存数组
int n, m;//n个点,求前m小
int r ;//堆得右边界
void down(int u)//调整函数
{
    //t记录最小点的编号
    int t = u;

    //有左儿子,并且左儿子比t节点的值小,更新t
    if(2 * u <= r && a[2 * u] < a[u]) t = 2 * u;

    //有右儿子,并且右儿子比t节点的值小,更新t
    if(2 * u + 1 <= r && a[2 * u + 1] < a[t]) t = 2 * u + 1;

    //如果待调整点不是最小的
    if(u != t)
    {
        //和最小的交换
        swap(a[u], a[t]);

        //递归处理
        down(t);
    }
}



int main()
{
    cin >> n >> m;
    r = n;//开始时,右边界是数组边界

    //读入数据
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> a[i];
    }

    //从第一个非叶节点开始,从右到左,从下到上处理每个节点
   for(int i = n /2 ; i >= 1; i--)
   {
       down(i);
   }

    //输出m个最小值
    while (m -- )
    {
        //堆顶保存的最小值,输出堆顶
        cout << a[1] << " ";

        //将堆顶和右边界交换
        swap(a[1], a[r]);

        //右边界左移
        r--;

        //从新处理堆顶
        down(1);
    }
}



Hasity
2个月前

<= 点赞支持一下吧~~

什么是并查集?

逐字拆解一下,并、查、集。这个三个字,其中前面两个字都是动词,第三个字是个名词。

先看名词,因为只有知道了这个东西是什么,才能去理解它能干什么。

集就是集合,中学时期就学过这个东西,集合用大白话说就是将一堆元素没有顺序地摆放在同一个地方。

其实并查集本质就是集合

那它能做什么呢?这就要看前两个字 - “并” 和 “查”。

集合的一些操作,例如,交集,并集等等,这里的 “并” 其实就指的是并集操作,两个集合合并后就会变成一个集合。例如:

{1,3,5,7} U {2,4,6,8} = {1,2,3,4,5,6,7,8}

那 “查” 又是什么呢?集合本身只是容器,最终还是要知道里面存的是什么元素,因此这里的 “查” 是对于集合中存放的元素来说的,即要查找这个元素在不在集合中,还要确定这个元素是在哪个集合中。

好了,现在知道并查集是什么,以及它能干什么了,总结下来就是:

  • 并查集可以进行集合合并的操作(并)
  • 并查集可以查找元素在哪个集合中(查)
  • 并查集维护的是一堆集合(集)

举个例子:

有8个元素:14, 35, 48, 87, 65, 20

:把个位相同的数字归在同一个集合。集合划分为如下:

{14}, {35, 65}, {48}, {87}, {20}

:给定一个元素,得到这个元素属于哪个集合。例如:

  • 给定元素14,可以得出:14 位于第一个集合。
  • 给定元素65,可以得出:65 位于第二个集合。
  • 给定元素20,可以得出:20 位于第五个集合。

:将两个集合合并,例如将个位为偶数的集合合并的到第一个集合,个位为奇数的集合合并到第二个集合,结果如下:
{14, 48, 20}, {35, 65, 87}


相信通过上面的表述,已经知道,并查集维护的是一堆集合。用什么样的数据结构表示并查集?

对于并查集,有两个信息是必须要知道的:

  • 元素的值。
  • 集合的标号。

一个元素必须仅存在于一个集合中,一个集合中可以有多个元素。

元素对集合来说,是多对一的关系。这么看来可以用一个健值对的结构来表示并查集(键是元素,值时所属集合)。

但是如果对元素本身没有特定要求的话,可以使用数组,这样速度更快,使用起来也更加简单:

{0}, {1}, {2}, {3}, {4}, {5} => [0,1,2,3,4,5]

{0,1,2}, {3,4,5} => [0,0,0,3,3,3] or [1,1,1,4,4,4] 

在解释上面的数组表示方式之前,不知道有没有发现一个事实:

  • 元素本身的值是固定不变的,但是元素所属的集合是可以变化的”

因此可以使用两个数组:

  • 第一个数组保存所有元素
  • 第二个数组使用数组的 下标 来代表数组一中元素,对应位置上 存放的值 表示元素所属的集合。

例如:{0,1,2}, {3,4,5} => [0,0,0,3,3,3]:第一个数组是0, 1, 2, 3, 4, 5,第二个数组是0, 0, 0, 3, 3, 3。第一个数组保存了所有元素,第二个数组保存了元素所属集合。

  • 第二个数组中,第一个元素是0,含义是:第一个数组的第一个元素属于 0 号集合。
  • 第二个数组中,第二个元素是0,含义是:第一个数组的第二个元素属于 0 号集合。
  • 第二个数组中,第三个元素是0,含义是:第一个数组的第三个元素属于 0 号集合。
  • 第二个数组中,第四个元素是3,含义是:第一个数组的第四个元素属于 3 号集合。
  • 第二个数组中,第五个元素是3,含义是:第一个数组的第五个元素属于 3 号集合。
  • 第二个数组中,第六个元素是3,含义是:第一个数组的第六个元素属于 3 号集合。

说完了集合的表示,来看看如何基于这种表示去实现 “并” 和 “查”,也就是集合的合并和元素的查找,这两个操作是相互影响的。合并其实就是改变第二个数组中存放的值,这个值表示的是第一个数组对应位置元素所在的集合。

上述实现并查集方法很直观。但是将连个集合合并的时候,需要修改其中一个集合中的所有元素对应的数组二中的值,有没有办法优化下呢?

这个问题的源是:第二个数组中保存的是第一个数组中各个元素所属集合,所以合并集合的时候,第二个数组中需要修改元素比较多。

可以为每个元素选出一个代表它的元素,数组二中存放代表元素

例如:{0,1,2}, {3,4,5} => [0,0,0,3,3,3]:第一个数组是0, 1, 2, 3, 4, 5,第二个数组是0, 0, 0, 3, 3, 3。第一个数组保存了所有元素,第二个数组保存了能代表该元素的元素。

  • 第二个数组中,0号位置保存的是0,含义是:第一个数组的0号位置保存的元素和 第一个数组中的0号位置保存的元素属于同一个集合。

  • 第二个数组中,1号位置保存的是0,含义是:第一个数组的1号位置保存的元素和 第一个数组中的0号位置保存的元素属于同一个集合。

  • 第二个数组中,2号位置保存的是0,含义是:第一个数组的2号位置保存的元素和 第一个数组中的0号位置保存的元素属于同一个集合。

  • 第二个数组中,3号位置保存的是3,含义是:第一个数组的3号位置保存的元素和 第一个数组中的3号位置保存的元素属于同一个集合。

  • 第二个数组中,4号位置保存的是3,含义是:第一个数组的4号位置保存的元素和 第一个数组中的3号位置保存的元素属于同一个集合。

  • 第二个数组中,5号位置保存的是3,含义是:第一个数组的5号位置保存的元素和 第一个数组中的3号位置保存的元素属于同一个集合。

这个时候,如果要合并两个集合,只需要修改代表元素即可。

例如:将{0,1,2}, {3,4,5} => [0,0,0,3,3,3]中的第二个集合合并到第一个集合中,。只需要修改第二个集合的代表元素集合,合并后为:{0,1,2,3,4,5} => [0,0,0,0,3,3]

这个时候,问:5这个元素位于哪个集合?查找过程如下:

  1. 在数组一中找到 5 这个元素的位置下标是:5
  2. 在第二个数组中查看下标5位置保存的元素是3。说明5这个元素和3这个元素在同一个集合。
  3. 在数组一中找到 3 这个元素的位置下标是:3。在第二个数组中查看下标3位置保存的元素是0。说明5这个元素和0这个元素在同一个集合。
  4. 在数组一中找到 0 这个元素的位置下标是:0。在第二个数组中查看下标0位置保存的元素是0,也就是找到了代表元素。得出结论5这个元素的代表元素是0,他们在同一个集合。

第二个数组保存代表元素,就能简化集合的合并。


总结:

  • 用一个数组保存对应位置元素所属集合的代表元素。
  • AB两个集合合并:将B集合代表元素的代表元素设置为A集合的代表元素。
  • 查找C元素属于哪个集合:找C元素的代表元素,如果不是他自己,就重复查找代表元素的代表元素,知道查找到一个元素的代表元素是它自己,C就属于整个代表元素所代表的集合。(啊啊啊,绕口令吗!!!)

代码实现

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

using namespace std;

const int N = 100010;

int p[N];//存放代表元素

//查找 x 所属的集合,就是 x 元素的代表元素
int find(int x)
{
    //如果 x 的代表元素不是他自己,就递归的x的代表元素修改为代表元素的代表元素
    if(x != p[x]) p[x] = find(p[x]);

    return p[x];
}

//合并a b所在的两个集合
void merge(int a, int b)
{
    int pa = find(a);//找到 a 所在集合的代表元素
    int pb = find(b);//找到 b 所在集合的代表元素
    if(pa != pb)//如果不是同一个,则属于不同集合,需要合并
    {
        p[pa] = pb;//将a所在集合代表元素的代表元素设置为b所在集合的代表元素。
    }
}


void query(int a,int b)
{
    int pa = find(a);//找到 a 所在集合的代表元素
    int pb = find(b);//找到 b 所在集合的代表元素
    //判断 a 和 b 是否有同一个代表元素
    if(pa == pb) cout << "Yes" << endl;
    else cout << "No" << endl;
    return ;
}
int main()
{
    int n, m;
    cin >> n >> m;
    //初始化代表元素集合,开始的时候,各自属于一个集合,即每个元素的代表元素是他自己。
    for (int i = 1; i <= n; i ++ )
        p[i] = i;

    while (m -- )
    {
        char op;
        cin >> op;
        int a, b;
        cin >> a >> b;

        if(op == 'M')
        {//合并
            merge(a, b);
        }
        else
        {//查询
            query(a, b);
        }
    }
}



Hasity
3个月前
let buf = "";

process.stdin.on("readable", function() {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});

process.stdin.on("end", function(){
    let nums = buf.split('\n').map(x => {
        return parseInt(x);
    });

    //循环终止条件如果是 i < nums.length, 调试代码是对的,提交时错的,
    //            如果是 i < nums.length - 1, 调试代码是错的,提交时对的。
    for(let i = 0; i < nums.length - 1; i++){
        if(nums[i] <= 0) nums[i] = 1;
        console.log(`X[${i}] = ${nums[i]}`);
    }
});


分享 xx

Hasity
4个月前

20200716201955.png

55289_lg_5de0e068ab.png




Hasity
4个月前

$\color{green}{<–画图不易,点下这里}$

分情况讨论

起点 a, 终点 b,传送门:c, d.

  • 情况一:不使用传送门,abs(b - a)

1.PNG

  • 情况二: a -> c 然后通过c传送到d, 再从d->b。总距离为abs(a - c) + abs(b - d)

2.PNG

  • 情况二: a -> d 然后通过d传送到c, 再从c->b。总距离为abs(a - d) + abs(b - c)

3.PNG

三种情况取最小值即可。


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

using namespace std;

int a, b, c, d;

int main(){
    cin >> a >> b >> c >> d;
    //3 种情况取最小值即可
    cout << min({abs(b - a), abs(a - c) + abs(d - b), abs(a - d) + abs(b - c)});
    return 0;
}



Hasity
4个月前

$\color{green}{<–画图不易,点下这里}$

思路

数据范围比较小模拟即可。

  • 开辟一个二维数组。各个元素为0

1.PNG

  • 先放割草机,割草机的位置放 1 。

2.PNG

  • 再广告牌,广告牌的位置放0.

3.PNG

  • 求雨布的上下左右边界

4.PNG

边界里面的面积即为雨布面积。

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

using namespace std;

const int N = 2010;
int g[N][N];

int x1, y1, x2, y2;
int a1, b1, a2, b2;

int main(){
    cin >> x1 >> y1 >> x2 >> y2;
    x1 += 1000;
    x2 += 1000;
    y1 += 1000;
    y2 += 1000;
    cin >> a1 >> b1 >> a2 >> b2;
    a1 += 1000;
    a2 += 1000;
    b1 += 1000;
    b2 += 1000;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i > x1 && i <= x2 && j > y1 && j <= y2) 
                g[i][j] = 1;
            if(i > a1 && i <= a2 && j > b1 && j <= b2)
                g[i][j] = 0;
        }
    }
    int u1, v1, u2, v2;
    for(int i = 0; i < N; i++){
        u1 = i;
        for(int j = 0; j < N; j++){//求雨布左下点的x的值
            if(g[i][j] == 1){
                u1--;
                break;
            }
        }
        if(u1 != i){
            break;
        }
    }

    for(int i = 0; i < N; i++){//求雨布左下点的y
        v1 = i;
        for(int j = 0; j < N; j++){
            if(g[j][i] == 1){
                v1--;
                break;
            }
        }
        if(v1 != i){
            break;
        }
    }

    for(int i = N - 1; i != 0; i--){
        u2 = i;
        for(int j = 0; j < N; j++){//求雨布右上点的x的值
            if(g[i][j] == 1){
                u2++;
                break;
            }
        }
        if(u2 != i){
            break;
        }
    }

    for(int i = N - 1; i >= 0; i--){//求雨布右上点的y的值
        v2 = i;
        for(int j = 0; j < N; j++){
            if(g[j][i] == 1){
                v2++;
                break;
            }
        }
        if(v2 != i){
            break;
        }
    }
    if(u1 > u2 || v1 > v2) cout << 0;//判断是否雨布坐标是否合法
    else
        cout << (u2 - u1 - 1)*(v2 - v1 - 1);
    return 0;
}

分情况讨论也是可以的~~




Hasity
4个月前

$\color{green}{<–画图不易,点下这里}$

思路

数据范围比较小模拟即可。

  • 开辟一个二维数组。各个元素为0

0.PNG

  • 先放两个广告牌,广告牌的位置放 1 。

1.PNG

  • 再放卡车,卡车的位置放0.

2.PNG

求二维数组中1的个数,就是能看到的广告牌的范围。


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

using namespace std;

const int N = 2010;
int g[N][N];

int x1, y1, x2, y2;
int a1, b1, a2, b2;
int u1, v1, u2, v2;
int main(){
    cin >> x1 >> y1 >> x2 >> y2;
    x1 += 1000;//数据中有负数,全部转换成整数
    x2 += 1000;
    y1 += 1000;
    y2 += 1000;
    cin >> a1 >> b1 >> a2 >> b2;
    a1 += 1000;//数据中有负数,全部转换成整数
    a2 += 1000;
    b1 += 1000;
    b2 += 1000;
    cin >> u1 >> v1 >> u2 >> v2;
    u1 += 1000;//数据中有负数,全部转换成整数
    u2 += 1000;
    v1 += 1000;
    v2 += 1000;   
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i > x1 && i <= x2 && j > y1 && j <= y2) //放第一个广告牌
                g[i][j] = 1;
            if(i > a1 && i <= a2 && j > b1 && j <= b2)//放第二个广告牌
                g[i][j] = 1;

            if(i > u1 && i <= u2 && j > v1 && j <= v2)//放卡车
                g[i][j] = 0;
        }
    }
    int res = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            res += g[i][j];
        }
    }
    cout << res;
    return 0;
}