常州集训Day5

上午

堆/优先队列（STL）

STL会慢一些，空间占用多一些（所以学习手打是很有用的）

定义与代码

小根堆

根比左右节点小

#include <bits/stdc++.h>
using namespace std;
int a[100001],len=0; 
void puts(int x)
{
    a[++len]=x;
    for(int i=len;i>1;)
    {
        if(a[i] >1])
        {
            swap(a[i>>1],a[i]);
            i = i>>1;
        }
        else return ;
    }
} 
int gets()
{
    int x=a[1];
    a[1]=a[len--];
    for(int i=1;i<=len;)
    {
        int left=INT_MAX,right=INT_MAX;
        if((i<<1) <= len) left=a[i<<1];
        if((i<<1)+1 <= len) right=a[(i< min(left,right))
        {
            if(left < right) 
            {
                swap(a[i],a[i<<1]);
                i=i<<1;
            }
            else
            {
                swap(a[i],a[(i<<1)+1]);
                i=(i<<1)+1;
            }
        }
        else return x;
    }
    return x;
}
int main()
{
    return 0;
}

大根堆

根比左右节点大

#include <bits/stdc++.h>
using namespace std;
int a[100001],len=0; 
void puts(int x)
{
    a[++len]=x;
    for(int i=len;i>1;)
    {
        if(a[i] > a[i>>1])
        {
            swap(a[i>>1],a[i]);
            i = i>>1;
        }
        else return ;
    }
} 
int gets()
{
    int x=a[1];
    a[1]=a[len--];
    for(int i=1;i<=len;)
    {
        int left=INT_MIN,right=INT_MIN;
        if((i<<1) <= len) left=a[i<<1];
        if((i<<1)+1 <= len) right=a[(i<<1)+1];
        if(a[i]  right) 
            {
                swap(a[i],a[i<<1]);
                i=i<<1;
            }
            else
            {
                swap(a[i],a[(i<<1)+1]);
                i=(i<<1)+1;
            }
        }
        else return x;
    }
    return x;
}
int main()
{
    return 0;
}

打堆的小故事/事故

睡前故事《wzt堆炸了》

wzt写完了小根堆，准备开始测试了，puts()没有出问题，但是因为wzt的偷懒习惯他使用了连续的cout<<进行输出。然后wzt以为是gets()里面的问题，于是一遍遍修改了代码，还“参考”了老师的标程，知道他发现自己的cout<<是有问题的，30分钟过去了，wzt很……

请逐个输出，警钟长鸣！

下午

p.s.发现我的改变了，我去年打这套题目，只会打第一题。（哭泣

• 第一题 “Hello”-队列应用

• 第二题 括号匹配-栈的应用

• 第三题 质质数-堆/优先队列的应用

• 第四题 贪心算法莫名其妙WA了

• 第五题 经典BFS，注意剪枝，记录到达(x,y)的最小花费，注意最短路径并不一定是最小花费。