首页 > ACM题库 > HDU-杭电 > HDU 4125-Moles-KMP-[解题报告]HOJ
2015
04-16

HDU 4125-Moles-KMP-[解题报告]HOJ

Moles

问题描述 :

A mole is a strange mammal adapted to a subterranean lifestyle. It has invisible eyes and short, powerful limbs with large paws oriented for digging.

Before the catastrophic earthquake, a group of moles have perceived the disaster. They move to a safe place and want to dig holes under the ground. There are n moles, numbered from 1 to n. They stand in a line and dig holes one by one. The mole line is not necessary sorted by the mole number. Every mole should live in a hole dug by itself and every mole just digs one hole. The first mole in the line digs the first hole with a channel to the ground. Then other moles go down through that channel and dig more holes and channels. A hole may have at most three neighbors connected by channels, one is on the upper level, and the other two holes are on the lower level lying on the left side and the right side. When a mole reaches a hole, if its number is smaller than the hole owner’s, it will go to the left-lower hole(or digs a left-lower hole and stays there when there is no left-lower hole), otherwise it will go to the right-lower hole(or digs a right-lower hole and stays there when there is no right-lower hole). Due to the excellent ability and well-designed layout, these holes and channels will not cross with each other.

Mouse Jerry is a friend of those moles. He comes to visit them and prepares gifts for every mole. There is a rule that the mole whose number is smaller must get the gift earlier than the mole whose number is larger. Jerry starts from the ground. He travels through the holes and channels to deliver his gifts. After giving out all his gifts, he comes back to the ground. In the mole world, it is interesting that the moles with odd numbers are males and others are females. When reaching a hole, Jerry takes a note about the gender of the hole owner(0 represents female and 1 represents male). When he gets back to the ground, he will get a 0-1 sequence. Now he wants to calculate the "harmony value". The harmony value represents the number of occurrences of a given "harmony string" in the above mentioned sequence. Occurrences may overlap.

Please note that Jerry is very smart so his travel distance is as small as possible.

输入:

The first line contains an integer t meaning that there are t test cases(t <= 10).
For each test case :
The first line is an integer n meaning that there are n moles. (n <= 600000).
The second line contains n integers representing the mole line. Each integer is a mole’s number and the first integer is the number of the first mole in the line.
The third line is the harmony string. The string length is not large than 7000.

输出:

The first line contains an integer t meaning that there are t test cases(t <= 10).
For each test case :
The first line is an integer n meaning that there are n moles. (n <= 600000).
The second line contains n integers representing the mole line. Each integer is a mole’s number and the first integer is the number of the first mole in the line.
The third line is the harmony string. The string length is not large than 7000.

样例输入:

2
8
5 1 3 2 7 8 4 6
01
10
1 2 3 4 5 6 7 8 9 10
1010

样例输出:

Case #1: 4
Case #2: 8

(Please note that there is a blank before '#' and after ':')
Hint
In the first test case, the 0-1 sequence of the first case is "111010111101011", and the number of occurrences of harmony string "01" is 4.

题意:有n(1<=n<=600000)个鼹鼠挖洞,每个鼹鼠有给定权值,挖的洞是一颗二叉树(左边的鼹鼠权值都比当前鼹鼠小,右边的鼹鼠权值比当前鼹鼠大),

         也要按照鼹鼠的出场顺序挖洞,在形成的二叉树按照中序遍历顺序奇数偶数(1,0)得到01序列,问01序列中给定的序列出现多少次。

题解:笛卡尔树,k(SBT)为鼹鼠的权值,a(堆)为鼹鼠的编号,排序后O(n)建树之后kmp即可。递归会RE,手动模拟栈。


Sure原创,转载请注明出处

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 600002;
const int maxm = 7002;
struct P
{
    int k,a;
    bool operator < (const P &other) const
    {
        return k < other.k;
    }
}mole[maxn];
struct T
{
    int l,r,fa;
}tree[maxn];
int next[maxm],stack[maxn],state[maxn];
char str[maxm],list[maxn * 3];
int n,tot,top;

void init()
{
    memset(tree,0,sizeof(tree));
    memset(state,0,sizeof(state));
    tot = top = 0;
    return;
}

void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&mole[i].k);
        mole[i].a = i;
    }
    sort(mole + 1 , mole + n + 1);
    scanf("%s",str);
    return;
}

void rotate(int x)
{
    int p = tree[x].fa;
    int l = tree[x].l;
    if(p == tree[tree[p].fa].l)
    {
        tree[tree[p].fa].l = x;
    }
    else
    {
        tree[tree[p].fa].r = x;
    }
    tree[x].fa = tree[p].fa;
    tree[x].l = p;
    tree[p].fa = x;
    tree[p].r = l;
    if(l) tree[l].fa = p;
    return;
}

void dfs(int st)
{
    stack[top++] = st;
    while(top)
    {
        int cur = stack[top-1];
        list[tot++] = (mole[cur].k & 1) + '0';
        if(++state[cur] == 3)
        {
            top--;
            continue;
        }
        if(state[cur] == 1)
        {
            if(tree[cur].l) stack[top++] = tree[cur].l;
            else state[cur]++;
        }
        if(state[cur] == 2)
        {
            if(tree[cur].r) stack[top++] = tree[cur].r;
            else state[cur]++;
        }
        if(state[cur] == 3) top--;
    }
    return;
}

void make()
{
    tree[0].r = 1;
    int rightmost = 1;
    for(int i=2;i<=n;i++)
    {
        tree[rightmost].r = i;
        tree[i].fa = rightmost;
        rightmost = i;
        while(tree[i].fa && mole[i].a < mole[tree[i].fa].a) rotate(i);
    }
    dfs(tree[0].r);
    list[tot] = '\0';
    return;
}

void getnext(char *s)
{
    int len=strlen(s);
    for(int i=0;i<=len;i++)
    {
        next[i] = 0;
    }
    next[0] = -1;
    int j=-1;
    for(int i=0;i<len;)
    {
        if(j==-1||s[i]==s[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else j=next[j];
    }
    return;
}

int kmp(char a[],char b[])
{
    int count=0;
    getnext(b);
    int lena = strlen(a);
    int lenb = strlen(b);
    int j=0,i=0;
    while(i<lena && j<lenb)
    {
        if(j==-1 || b[j]==a[i])
        {
            j++;
            i++;
        }
        else j=next[j];
        if(j == lenb)
        {
            count++;
            j = next[j];
        }
    }
    return count;
}

int main()
{
    int cas;
    scanf("%d",&cas);
    for(int i=1;i<=cas;i++)
    {
        printf("Case #%d: ",i);
        init();
        read();
        make();
        printf("%d\n",kmp(list,str));
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/flying_stones_sure/article/details/8110090


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。