Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

trie树TLE的注意了!!!!!

Posted by moretimes at 2012-09-14 12:50:56 on Problem 1204 and last updated at 2012-09-14 12:51:42
1.数组开小的话就是一切皆有可能
2.优化是这样的:
由于单词个数很少 而且在矩阵中不会有重复(数据特殊)
所以很多单词在刚刚开始匹配时就夭折了(绝大多数)
所以枚举判断时 不要先把字符串取出来 更不要写成函数!!
for (int i = 0; i < n; i ++)
		for (int j = 0; j < m; j ++)
			for (int k = 0; k < 8; k ++)
			{
				int p (0);
				int x = i, y = j;
				while (x < n && y < m && x >= 0 && y >= 0)
				{
					char ch = map[x][y];
					if (t[p][ch - 'A'])
					{
						p = t[p][ch - 'A'];
						if (vis[p])
						{
							vis[p] = false;
							ans[la[p]][0] = i;
							ans[la[p]][1] = j;
							ans[la[p]][2] = k;
						}
					
					}
					else
						break;
					x += dx[k];
					y += dy[k];
				}
			}
1s和AC自动机差不多

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator