长乐7.17集训

当闺蜜在逛街的时候,我在集训

当闺蜜看电影的时候,我在集训

当闺蜜在恋爱的时候,我在集训

 


1.二叉堆:模板


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
父节点:i,左子节点:2i,右子节点:2i+1

priority_queue< int,vector<int>,greater<int> > q;//小顶堆,升序
priority_queue< int,vector<int>,less<int> > q;//大顶堆,降序

结构体://↓根据a值排序
struct node
{
    long long a;
    long long b;
};
struct cmp
{
    bool operator() (node x,node y)
    {
        return x.a>y.a;  
    }
};
priority_queue< node,vector<node>,cmp > q;

 


2.树状数组:https://www.bilibili.com/video/BV1jf4y12714?from=search&seid=14636685476178326059

模板:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
C[i]的父亲节点为C[i+2<sup>k</sup>];
C[i]的兄弟节点为C[i-2<sup>k</sup>];

求2<sup>k</sup>中的k:
lowbit(n)=n&-n;

对某个元素进行加法操作:
void update(int x,int y) //查找父亲节点,边界为n
{
    for(;x<=n;x+=x&-x) c[x]+=y;
}

查询前缀和:
long long sum(int x) //查找兄弟节点,边界为0
{
    long long ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}

 


3.RMQ:https://www.bilibili.com/video/BV1nE411L7rz?t=836

 


4.合并果子:http://noip.ybtoj.com.cn/contest/40/problem/1

题解:堆,两堆合并时要将合并的值入堆。

 


5.序列合并:http://noip.ybtoj.com.cn/contest/40/problem/2

题解:堆,两队相加判断时,因为在n^2中取n,所以循环可以i*j<=n来减少时间。

 


6.龙珠游戏:http://noip.ybtoj.com.cn/contest/40/problem/3

题解:在枚举当前未打印的数中的最大值时用堆,并 建立数组from[ ]和next[ ],来存储每个数当前前后数的坐标。(小数据过了,大数据炸了,没有AC,一时也改不出来)

 


7.工作安排:http://noip.ybtoj.com.cn/contest/40/problem/4

题解:结构体堆排序,贪心思想,每项工作都做,当时间不够时,减去当前价值最小的工作。

 


8.单点修改区间查询:http://noip.ybtoj.com.cn/contest/42/problem/1

题解:模板题。

 


The end.