头像

冰中月




离线:20小时前


最近来访(2010)
用户头像
布克波波
用户头像
Kirito_9
用户头像
doudou_0
用户头像
种花家的兔兔
用户头像
云衣醉梦
用户头像
LiquidFloy
用户头像
这道题有点难耶
用户头像
AcWing2AK
用户头像
恋上风
用户头像
tuffynibbles
用户头像
Behappyeveryday
用户头像
rick_2
用户头像
xiuzhiyuan
用户头像
Rain丶bow
用户头像
亚历山大
用户头像
头发乱了0
用户头像
Expelliarmus2011
用户头像
下栈
用户头像
wzy233
用户头像
Vertex

活动打卡代码 AcWing 125. 耍杂技的牛

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
int n;
pair <int,int> cow[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int w,s;
        scanf("%d%d",&w,&s);
        cow[i] = {w + s,w};
    }
    sort(cow,cow + n);
    int res = -2e9,sum = 0;
    for(int i = 0;i < n;i ++){
        int w = cow[i].second,s = cow[i].first - w;
        res = max(res,sum - s);
        sum += w;
    }
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
    sort(a,a + n);
    int res = 0;
    for(int i = 0;i < n;i ++) res += abs(a[i] - a[n / 2]);
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 913. 排队打水

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int t[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++) scanf("%d",&t[i]);
    sort(t,t + n);
    long long res = 0;
    for(int i = 0;i < n;i ++) res += t[i] * (n - i - 1);
    printf("%lld\n",res);
    return 0;
}



数据结构 堆 $heap$


堆的简介

堆($Heap$)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆分为两个板块,一个是大根堆,一个是小根堆。

  • 大根堆

    每一个节点元素的值都不小于左右子树的值
    根节点的元素最大

  • 小根堆

    每一个节点元素的值都不大于左右子树的值
    根节点的元素最小


堆的实现

手写堆

在写呢



活动打卡代码 AcWing 148. 合并果子

#include <iostream>
#include <queue>
using namespace std;
const int N = 10010;
int n;
priority_queue <int,vector <int>,greater <int> > heap;
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int x;
        scanf("%d",&x);
        heap.push(x);
    }
    int res = 0;
    while(heap.size() > 1){
        int x = heap.top();
        heap.pop();
        int y = heap.top();
        heap.pop();
        res += x + y;
        heap.push(x + y);
    }
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 907. 区间覆盖

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
    int l,r;
    bool operator < (const Range &w) const {
        return l < w.l;
    }
}range[N];
int main(){
    int s,t;
    scanf("%d%d",&s,&t);
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    sort(range,range + n);
    bool success = false;
    int res = 0;
    for(int i = 0;i < n;i ++){
        int j = i,r = -2e9;
        while(range[j].l <= s && j < n){
            r = max(range[j].r,r);
            j ++;
        }
        if(r < s){
            res = -1;
            break;
        }
        res ++;
        if(r >= t){
            success = true;
            break;
        }
        s = r;
        i = j - 1;
    }
    if(!success) res = -1;
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 906. 区间分组

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
    int l,r;
    bool operator < (const Range &w) const{
        return l < w.l;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    sort(range,range + n);
    priority_queue <int,vector <int>,greater <int> > heap;
    for(int i = 0;i < n;i ++){
        Range r = range[i];
        if(heap.empty() || heap.top() >= r.l) heap.push(r.r);
        else{
            heap.pop();
            heap.push(r.r);
        }
    }
    printf("%d\n",heap.size());
    return 0;
}



#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
    int l,r;
    bool operator < (const Range &w) const{
        return r < w.r;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    sort(range,range + n);
    int res = 0,ed = -2e9;
    for(int i = 0;i < n;i ++){
        if(ed < range[i].l){
            res ++;
            ed = range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}


活动打卡代码 AcWing 905. 区间选点

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range{
    int l,r;
    bool operator < (const Range &w)const{
        return r < w.r;
    }
}range[N];
int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        int l,r;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    sort(range,range + n);
    int res = 0,ed = -2e9;
    for(int i = 0;i < n;i ++){
        if(ed < range[i].l){
            res ++;
            ed = range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}



冰中月
13天前

题目描述

blablabla

样例

blablabla

算法1

(并查集) $O(10000)$

首先看题目,我们找到了这一句话:

现代的人对于本家族血统越来越感兴趣,现在给出充足的父子关系,请你编写程序找到某个人的最早的祖先。

找到某个人的最早的祖先,找祖先的这种问题,用并查集就能很好的实现,那下面我们来看看怎么实现。

手写这道题目输入的是人的名字,那为了更好的找到这个人的祖先并输出他的姓名,我们可以用一个$unordered\underline{~}map$来做映射。然后就直接手写并查集啦。

时间复杂度

并查集的每一个操作都是近乎$O(1)$的,一共有$10000$组父子关系,那就大概是$O(10000)$这个神奇的复杂度。

参考文献

C++ 代码

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map <string,string> p; // 每个节点的父节点,用unordered_map做映射
string find(string x){ // 查找根节点操作,因为父节点存的都是string类型的,所以定义为string类型
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin.tie(0); // 优化一下cin,cout
    cout.tie(0);
    char op; // 每个操作的类型
    string father; // 因为题目是输入一个父亲,然后跟着一些儿子,所以就需要拿一个字符串记下当前这个人的父亲,记得不要在while循环里定义哦,因为每个父亲不一定只有1个儿子
    while(cin>>op,op != '$'){ // 循环,只要op为$,就跳出循环
        string name; // 当前这个人的名字
        cin>>name;
        if(op == '#'){ // 如果这是个父亲
            father = name; // 找到一个父亲,存下来,方便后面儿子找到父亲
            if(p[name] == "") p[name] = name; // 如果这个人没有父亲,就把自己设为祖宗
        }
        else if(op == '+') p[name] = father; // 如果是个儿子,把自己的父亲找到,并赋值
        else cout<<name<<" "<<find(name)<<endl; // 否则就是查找这个人的祖宗,题目要求输出这个人的名字和他的祖宗的名字
    }
    return 0;
}