hdu2222

maksyuki 发表于 oj 分类，标签: 字符串-AC自动机

15 9月 2015

Keywords Search

Problem Description

In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.

Input

First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.

Output

Print how many keywords are contained in the description.

Sample Input

she

say

shr

her

yasherhs

Sample Output

Author

Wiskey

题目类型：AC自动机

算法分析：直接将按照单词建立一个AC自动机，然后如果找到一个匹配的模式串，则不断寻找这个模式串的后缀，看能不能又找到一个匹配的模式串，防止漏解。注意使用G++会MLE！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1e9 + 7;
const int maxn = 26;

char ss[1000000+maxn];

struct Node
{
    Node *next[maxn];
    Node *pre;
    int last;
    Node ()
    {
        memset (next, 0, sizeof (next));
        pre = 0, last = 0;
    }
};

Node *root;

void Init ()
{
    root = new Node;
}

void Insert (char *s)
{
    if (!s[0]) return ;

    Node *p = root;
    for (int i = 0; s[i]; i++)
    {
        if (!p -> next[s[i]-'a'])
            p -> next[s[i]-'a'] = new Node;

        p = p -> next[s[i]-'a'];
    }
    p -> last++;
}

void Build ()
{
    queue <Node*> qu;
    Node *p = root;
    for (int i = 0; i < maxn; i++)
        if (p -> next[i])
        {
            Node *pp = p -> next[i];
            pp -> pre = root;
            qu.push (pp);
        }

    while (!qu.empty ())
    {
        Node *temp = qu.front (); qu.pop ();
        for (int i = 0; i < maxn; i++)
        {
            Node *pp = temp -> next[i];
            if (pp)
            {
                Node *par = temp -> pre;
                do
                {
                    if (par -> next[i])
                    {
                        pp -> pre = par -> next[i];
                        break;
                    }

                    else
                        par = par -> pre;
                } while (par);

                if (!par)
                    pp -> pre = root;

                qu.push (pp);
            }
        }
    }
}

int Query (char *s)
{
    if (!s[0]) return 0;

    Node *p = root;
    int cnt = 0;
    for (int i = 0; s[i]; i++)
    {
        while (p != root && !p -> next[s[i]-'a'])
            p = p -> pre;

        p = p -> next[s[i]-'a'];
        if (!p)
            p = root;

        Node *pp = p;
        while (pp != root && pp -> last != -1)
        {
            cnt += pp -> last;
            pp -> last = -1;
            pp = pp -> pre;
        }
    }
return cnt;
}

void DelTree (Node *s)
{
    if (!s) return ;

    for (int i = 0; i < maxn; i++)
    {
        if (s -> next[i])
            DelTree (s -> next[i]);
    }
    delete s;
}

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t;
    scanf ("%d", &t);
    while (t--)
    {
        int n;
        scanf ("%d",&n);
        Init ();

        for (int i = 1; i <= n; i++)
        {
            scanf ("%s", ss);
            Insert (ss);
        }

        gets (ss);
        gets (ss);

        Build ();

        printf ("%d\n", Query (ss));
        DelTree (root);
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1e9 + 7;

const int maxn = 26;

char ss[1000000+maxn];

struct Node

{

Node *next[maxn];

Node *pre;

int last;

Node ()

{

memset (next, 0, sizeof (next));

pre = 0, last = 0;

}

};

Node *root;

void Init ()

{

root = new Node;

}

void Insert (char *s)

{

if (!s[0]) return ;

Node *p = root;

for (int i = 0; s[i]; i++)

{

if (!p -> next[s[i]-'a'])

p -> next[s[i]-'a'] = new Node;

p = p -> next[s[i]-'a'];

}

p -> last++;

}

void Build ()

{

queue <Node*> qu;

Node *p = root;

for (int i = 0; i < maxn; i++)

if (p -> next[i])

{

Node *pp = p -> next[i];

pp -> pre = root;

qu.push (pp);

}

while (!qu.empty ())

{

Node *temp = qu.front (); qu.pop ();

for (int i = 0; i < maxn; i++)

{

Node *pp = temp -> next[i];

if (pp)

{

Node *par = temp -> pre;

{

if (par -> next[i])

{

pp -> pre = par -> next[i];

break;

}

else

par = par -> pre;

} while (par);

if (!par)

pp -> pre = root;

qu.push (pp);

}

int Query (char *s)

{

if (!s[0]) return 0;

Node *p = root;

int cnt = 0;

for (int i = 0; s[i]; i++)

{

while (p != root && !p -> next[s[i]-'a'])

p = p -> pre;

p = p -> next[s[i]-'a'];

if (!p)

p = root;

Node *pp = p;

while (pp != root && pp -> last != -1)

{

cnt += pp -> last;

pp -> last = -1;

pp = pp -> pre;

}

return cnt;

}

void DelTree (Node *s)

{

if (!s) return ;

for (int i = 0; i < maxn; i++)

{

if (s -> next[i])

DelTree (s -> next[i]);

}

delete s;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t;

scanf ("%d", &t);

while (t--)

{

int n;

scanf ("%d",&n);

Init ();

for (int i = 1; i <= n; i++)

{

scanf ("%s", ss);

Insert (ss);

}

gets (ss);

Build ();

printf ("%d\n", Query (ss));

DelTree (root);

}

return 0;

}

hdu2191

maksyuki 发表于 oj 分类，标签: DP-背包

15 9月 2015

念512汶川大地震遇难同胞——珍惜现在，感恩生活

Problem Description

急！灾区的食物依然短缺！阅读全文 »

hdu2188

maksyuki 发表于 oj 分类，标签: 博弈-Bash

15 9月 2015

悼念512汶川大地震遇难同胞——选拔志愿者

Problem Description

对于四川同胞遭受的灾难，全国人民纷纷伸出援助之手，几乎每个省市都派出了大量的救援人员，这其中包括抢险救灾的武警部队，治疗和防疫的医护人员，以及进行心理疏导的心理学专家。根据要求，我校也有一个奔赴灾区救灾阅读全文 »

hdu2152

maksyuki 发表于 oj 分类，标签: 组合数学-普通母函数

15 9月 2015

Fruit

Problem Description

转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。

于是，很多人们慕名而来，找Lele买水果。阅读全文 »

hdu2149

maksyuki 发表于 oj 分类，标签: 博弈-Bash

15 9月 2015

Public Sale

Problem Description

虽然不想，但是现实总归是现实，Lele始终没有逃过退学的命运，阅读全文 »

hdu2141

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

15 9月 2015

Can you find it?

Problem Description

Give you three sequences of numbers A, B, C, then we 阅读全文 »

hdu2138

maksyuki 发表于 oj 分类，标签: 数论-大素数测试

15 9月 2015

How many prime numbers

Problem Description

Give you a lot of positive integers, just to find out how many prime numbers there are. 阅读全文 »

hdu2098

maksyuki 发表于 oj 分类，标签: 数论-筛法

15 9月 2015

分拆素数和

Problem Description

把一个偶数拆成两个不同素数的和，有几种拆法呢？

Input

输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。阅读全文 »

hdu2067

maksyuki 发表于 oj 分类，标签: 组合数学-Catalan数

15 9月 2015

小兔的棋盘

Problem Description

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧! 阅读全文 »

hdu2051

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

15 9月 2015

Bitset

Problem Description

Give you a number on base ten,you should output it on base two.(0 < n < 1000)

Input

For each case there is a postive number n on base ten, end 阅读全文 »

hdu2044

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

15 9月 2015

一只小蜜蜂...

Problem Description

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。阅读全文 »

hdu1950

maksyuki 发表于 oj 分类，标签: DP-线性DP

15 9月 2015

Bridging signals

Problem Description

'Oh no, they've done it again', cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too
expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without rossing each other, is imminent. Bearing in mind that there may be housands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?

Figure 1. To the left: The two blocks' ports and their signal mapping (4,2,6,3,1,5). To the right: At most three signals may be routed on the silicon surface without crossing each other. The dashed signals must be bridged.

A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number pecifies which port on the right side should be connected to the i:th port on the left side.
Two signals cross if and only if the straight lines connecting the two ports of each pair do.

Input

On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer p<40000, the number of ports on the two functional blocks. Then follow p lines, describing the signal mapping: On the i:th line is the port number of the block on the right side which should be connected to the i:th port of the block on the left side.

Output

For each test scenario, output one line containing the maximum number of signals which may be routed on the silicon surface without crossing each other.

Sample Input

Sample Output

Source

NWERC2003

题目类型：LIS

算法分析：直接使用LIS求解即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 500000 + 666;

int ans[maxn], b[maxn], LEN;

//用二分查找的方法找到一个位置，使得num>b[i-1] 并且num<b[i],并用num代替b[i]
int Search (int num,int low,int high)
{
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(num>=b[mid])  low=mid+1;
        else   high=mid-1;
    }
    return low;
}


int LIS (int n)
{
    int i, len, pos;
    b[1] = ans[1];
    len = 1;
    for (i = 2;i <= n; i++)
    {
        if(ans[i] >= b[len])//如果a[i]比b[]数组中最大还大直接插入到后面即可
        {
            len++;
            b[len] = ans[i];
        }

        else//用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置
        {
            pos = Search (ans[i], 1, len);
            b[pos] = ans[i];
        }
    }

return len;
}



int main()
{
//    ifstream cin ("aaa.txt");
//    freopen ("aaa.txt", "r", stdin);

    int t;
    scanf ("%d", &t);

    while (t--)
    {
        int  n;
        scanf ("%d", &n);

        for (int i = 1; i <= n; i++)
            scanf ("%d", &ans[i]);

        printf ("%d\n", LIS (n));
    }

return 0;
}

100

101

102

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 500000 + 666;

int ans[maxn], b[maxn], LEN;

//用二分查找的方法找到一个位置，使得num>b[i-1] 并且num<b[i],并用num代替b[i]

int Search (int num,int low,int high)

{

int mid;

while(low<=high)

{

mid=(low+high)/2;

if(num>=b[mid]) low=mid+1;

else high=mid-1;

}

return low;

}

int LIS (int n)

{

int i, len, pos;

b[1] = ans[1];

len = 1;

for (i = 2;i <= n; i++)

{

if(ans[i] >= b[len])//如果a[i]比b[]数组中最大还大直接插入到后面即可

{

len++;

b[len] = ans[i];

}

else//用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置

{

pos = Search (ans[i], 1, len);

b[pos] = ans[i];

}

return len;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t;

scanf ("%d", &t);

while (t--)

{

int n;

scanf ("%d", &n);

for (int i = 1; i <= n; i++)

scanf ("%d", &ans[i]);

printf ("%d\n", LIS (n));

}

return 0;

}

hdu1863

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

15 9月 2015

畅通工程

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查阅读全文 »

hdu1846

maksyuki 发表于 oj 分类，标签: 博弈-Bash

15 9月 2015

Brave Game

Problem Description

十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》（英文名称：Zathura），一直到现在，我依然对于电影中的部分电脑特技印象深刻。阅读全文 »

hdu1792

maksyuki 发表于 oj 分类，标签: 数论-模算术

15 9月 2015

A New Change Problem

Problem Description

Now given two kinds of coins A and B,which satisfy that GCD(A,B)=1. 阅读全文 »

hdu1788

maksyuki 发表于 oj 分类，标签: 数论-模算术

15 9月 2015

Chinese remainder theorem again

Problem Description

我知道部分同学最近在看中国剩余定理，就这个定理本身，还是比较简单的：
假设m1,m2,…,mk两两互素，则下面同余方程组：阅读全文 »

返回首页上一页 9 10 11 12 13 下一页最后一页

超客的水墨烟雨

hdu2222

Keywords Search

hdu2191

念512汶川大地震遇难同胞——珍惜现在，感恩生活

hdu2188

悼念512汶川大地震遇难同胞——选拔志愿者

hdu2152

Fruit

hdu2149

Public Sale

hdu2141

Can you find it?

hdu2138

How many prime numbers

hdu2098

分拆素数和

hdu2067

小兔的棋盘

hdu2051

Bitset

hdu2044

一只小蜜蜂...

hdu1950

Bridging signals

hdu1863

畅通工程

hdu1846

Brave Game

hdu1792

A New Change Problem

hdu1788

Chinese remainder theorem again

分类目录

标签云

书签

近期评论

2015年9月
一	二	三	四	五	六	日
« 8月				10月 »
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30