放牧代码和思想
专注自然语言处理、机器学习算法

AOJ 1070 FIMO sequence 题解《挑战程序设计竞赛》

目录

工作簿1.png挑战程序设计竞赛第二版.jpg

AOJ 1070 FIMO sequence 

FIMO序列:对空序列执行如下十种操作:

0、将x插入序列尾部,同一个x只出现一次

1、删除中点元素并输出该元素

2、输出前半段的最小元素

3、输出后半段的最小元素

4、假设重复2和1,输出属于{2的输出}且属于{初始状态前半段的元素}中的第i小的元素

5、假设重复3和1,输出属于{3的输出}且属于{初始状态后半段的元素}中的第i小的元素

6、输出前半段的最大元素

7、输出后半段的最大元素

8、假设重复2和1,输出属于{2的输出}且属于{初始状态前半段的元素}中的第i大的元素

9、假设重复3和1,输出属于{3的输出}且属于{初始状态后半段的元素}中的第i大的元素

4.4常用技巧精选(二) 

双端队列 

这是对双端队列的终极应用,因为一下子用了6个……

题目怪长的,还是举例说明比较快。日本人的英文跟中国人的英文半斤八两,都难以理解,只能看日语原文去揣摩。

拿31那个case举例如下

query fh.data|sh.data fh.MIN|sh.MIN fh.MAX|sh.MAX output
0 6 6 |  6 |  6 | 
0 2 6 | 2  6 | 2  6 | 2 
0 3 6 2 | 3  6 2 | 3  6 | 3 
0 4 6 2 | 3 4  6 2 | 3 4  6 | 4 
0 5 6 2 3 | 4 5  6 2 | 4 5  6 | 5 
0 1 6 2 3 | 4 5 1  6 2 | 1  6 | 5 1 
0 8 6 2 3 4 | 5 1 8  6 2 | 1 8  6 | 8 
4 1 6 2 3 4 | 5 1 8  6 2 | 1 8  6 | 8  2
4 2 6 2 3 4 | 5 1 8  6 2 | 1 8  6 | 8  6
5 1 6 2 3 4 | 5 1 8  6 2 | 1 8  6 | 8  1
5 2 6 2 3 4 | 5 1 8  6 2 | 1 8  6 | 8  8
2 6 2 3 4 | 5 1 8  6 2 | 1 8  6 | 8  2
3 6 2 3 4 | 5 1 8  6 2 | 1 8  6 | 8  1
1 6 2 3 | 5 1 8  6 2 | 1 8  6 | 8  4
2 6 2 3 | 5 1 8  6 2 | 1 8  6 | 8  2
3 6 2 3 | 5 1 8  6 2 | 1 8  6 | 8  1
1 6 2 5 | 1 8  6 2 | 1 8  6 | 8  3
2 6 2 5 | 1 8  6 2 | 1 8  6 | 8  2
3 6 2 5 | 1 8  6 2 | 1 8  6 | 8  1
1 6 2 | 1 8  6 2 | 1 8  6 | 8  5
2 6 2 | 1 8  6 2 | 1 8  6 | 8  2
3 6 2 | 1 8  6 2 | 1 8  6 | 8  1
1 6 1 | 8  6 1 | 8  6 | 8  2
2 6 1 | 8  6 1 | 8  6 | 8  1
3 6 1 | 8  6 1 | 8  6 | 8  8
1 6 | 8  6 | 8  6 | 8  1
2 6 | 8  6 | 8  6 | 8  6
3 6 | 8  6 | 8  6 | 8  8
1 8 |  8 |  8 |  6
2 8 |  8 |  8 |  8
1 8

将序列分为前半段和后半段,每部分都用双端队列维护原始数据data,最小值MIN和最大值MAX。

观察样例

Assume that deletion will be repeated to the sequence {6,2,3,4,5,1,8}.
{6,2,3,4,5,1,8} The minimum element in the first half of the sequence is 2.
{6,2,3,5,1,8}   The minimum element in the first half of the sequence is 2.
{6,2,5,1,8}     The minimum element in the first half of the sequence is 2.
{6,2,1,8}       The minimum element in the first half of the sequence is 2.
{6,1,8}         The minimum element in the first half of the sequence is 1.
{6,8}           The minimum element in the first half of the sequence is 6.
{8}             The minimum element in the first half of the sequence is 8.
{}              The first half of the sequence is empty.
For the initial state, {6,2,3,4} is the first half of the sequence. 2 and 6 become the minimum element of the first half of the sequence. In this example, the 1-st minimum element is 2 and the 2-nd is 6.

由于操作1总是删除前半段的尾部,查询其最小值。如果尾部能被输出,它必须是整个前半段的最小元素。又因为要查询第i小,所以MIN是一个单调减的队列,仅需要在尾部插入时检查新元素是否比尾部小,小就插入,否则丢弃。同理维护MAX。

而后半段就不一样了

Assume that deletion will be repeated to the sequence {6,2,3,4,5,1,8}.
{6,2,3,4,5,1,8} The minimum elemets in the latter half of the sequence is 1.
{6,2,3,5,1,8}   The minimum elemets in the latter half of the sequence is 1.
{6,2,5,1,8}     The minimum elemets in the latter half of the sequence is 1.
{6,2,1,8}       The minimum elemets in the latter half of the sequence is 1.
{6,1,8}         The minimum elemets in the latter half of the sequence is 8.
{6,8}           The minimum elemets in the latter half of the sequence is 8.
{8}             The latter half of the sequence is empty.
{}              The latter half of the sequence is empty.
For the initial state, {5,1,8} is the latter half of the sequence. 1 and 8 becomes the minimum element of the latter half ot the sequence. In this example, the 1-st minimum element is 1 and the 2-nd is 8.

由于操作1执行后,后半段可能失去首部(转让成为前半段的尾部),如果首部能被输出,它必须是整个后半段的最小元素。又因为要查询第i小,所以MIN是一个单调增的队列,在尾部插入时要弹出所有比新元素大的既存元素。同理维护MAX。

#include <iostream>
#include <deque>

using namespace std;

struct FIMO_sequence
{
    struct first_half
    {
        deque<int> data;
        deque<int> MAX, MIN;

        /**
         * 添加到尾部
         * @param x
         */
        void add(int x)
        {
            data.push_back(x);
            if (data.size() == 1)
            {
                MAX.push_back(x);
                MIN.push_back(x);
            }
            else
            {
                if (MAX.back() < x)
                {
                    MAX.push_back(x);
                }
                if (MIN.back() > x)
                {
                    MIN.push_back(x);
                }
            }
        }

        /**
         * 从尾部删除
         * @return
         */
        int remove()
        {
            int x = data.back();
            data.pop_back();
            if (MIN.back() == x)
                MIN.pop_back();
            if (MAX.back() == x)
                MAX.pop_back();
            return x;
        }

        int size() const
        {
            return data.size();
        }
    } fh;

    struct second_half
    {
        deque<int> data;
        deque<int> MAX, MIN;

        /**
         * 添加到尾部
         * @param x
         */
        void add(int x)
        {
            data.push_back(x);
            if (data.size() == 1)
            {
                MAX.push_back(x);
                MIN.push_back(x);
            }
            else
            {
                while ((!MAX.empty()) && MAX.back() < x)
                {
                    MAX.pop_back();
                }
                while ((!MIN.empty()) && MIN.back() > x)
                {
                    MIN.pop_back();
                }
                MAX.push_back(x);
                MIN.push_back(x);
            }
        }

        /**
         * 删除首部元素
         * @return
         */
        int remove()
        {
            int x = data.front();
            data.pop_front();
            if (MIN.front() == x)
                MIN.pop_front();
            if (MAX.front() == x)
                MAX.pop_front();
            return x;
        }

        int size() const
        {
            return data.size();
        }
    } sh;

    int size()
    {
        return sh.size() + fh.size();
    }

    void add(int x)
    {
        sh.add(x);
        if (sh.size() > fh.size())
        {
            fh.add(sh.remove());
        }
    }

    int remove()
    {
        int r = fh.remove();
        if (sh.size() > fh.size())
        {
            fh.add(sh.remove());
        }
        return r;
    }

    /**
     * 前半段第i小
     * @param i
     * @return
     */
    int min_fh(int i)
    {
        return *(fh.MIN.end() - i);
    }

    /**
     * 后半段第i小
     * @param i
     * @return
     */
    int min_sh(int i)
    {
        return *(sh.MIN.begin() + i - 1);
    }

    /**
     * 前半段第i大
     * @param i
     * @return
     */
    int max_fh(int i)
    {
        return *(fh.MAX.end() - i);
    }

    /**
     * 后半段第i大
     * @param i
     * @return
     */
    int max_sh(int i)
    {
        return *(sh.MAX.begin() + i - 1);
    }
};

int main()
{
    while (true)
    {
        int q;
        scanf("%d", &q);
        if (q == 0)
            break;
        FIMO_sequence fimo;
        for (int i = 0; i < q; i++)
        {
            int qt, t;
            scanf("%d", &qt);
            switch (qt)
            {
                case 0:
                    scanf("%d", &t);
                    fimo.add(t);
                    break;
                case 1:
                    printf("%d\n", fimo.remove());
                    break;
                case 2:
                    printf("%d\n", fimo.min_fh(1));
                    break;
                case 3:
                    printf("%d\n", fimo.min_sh(1));
                    break;
                case 4:
                    scanf("%d", &t);
                    printf("%d\n", fimo.min_fh(t));
                    break;
                case 5:
                    scanf("%d", &t);
                    printf("%d\n", fimo.min_sh(t));
                    break;
                case 6:
                    printf("%d\n", fimo.max_fh(1));
                    break;
                case 7:
                    printf("%d\n", fimo.max_sh(1));
                    break;
                case 8:
                    scanf("%d", &t);
                    printf("%d\n", fimo.max_fh(t));
                    break;
                case 9:
                    scanf("%d", &t);
                    printf("%d\n", fimo.max_sh(t));
                    break;
            }
        }
        puts("end");
    }
    return 0;
}

hankcs.com 2017-01-19 下午10.35.37.png

Reference

http://d.hatena.ne.jp/k_operafan/20110925/1316916422

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » AOJ 1070 FIMO sequence 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机