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
ACM ICPC 2018 World Finals

为什么无限WA啊,不是很明白

Posted by scallop at 2018-01-12 21:04:04 on Problem 1743
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int MAXN = 21000;
int n, m;
int a[MAXN], rank[MAXN], y[MAXN], sa[MAXN], w[MAXN], wv[MAXN];
int height[MAXN];

void buildSA()
{
	m = 500;
	memset(w, 0, sizeof w);
	for (int i = 0; i < n; ++i)
	{
		rank[i] = a[i];
		++w[a[i]];
	}
	for (int i = 1; i < m; ++i)
		w[i] += w[i - 1];
	for (int i = n - 1; i > -1; --i)
	{
		--w[a[i]];
		sa[w[a[i]]] = i;
	}
	int p = 0;
	for (int i = 1; i < n && p < n; i *= 2)
	{
		p = 0;
		for (int j = n - i; j < n; ++j)
		{
			y[p] = j;
			++p;
		}
		for (int j = 0; j < n; ++j)
		{
			if (sa[j] >= i)
			{
				y[p] = sa[j] - i;
				++p;
			}
		}
		for (int j = 0; j < n; ++j)
			wv[j] = rank[y[j]];
		memset(w, 0, sizeof w);
		for (int j = 0; j < n; ++j)
			++w[wv[j]];
		for (int j = 1; j < m; ++j)
			w[j] += w[j - 1];
		for (int j = n - 1; j > -1; --j)
		{
			--w[wv[j]];
			sa[w[wv[j]]] = y[j];
		}
		for (int j = 0; j < n; ++j)
			swap(rank[j], y[j]);
		rank[sa[0]] = 0;
		p = 1;
		for (int j = 1; j < n; ++j)
		{
			if (y[sa[j]] == y[sa[j - 1]] && y[sa[j] + i] == y[sa[j - 1] + i])
				rank[sa[j]] = p - 1;
			else
			{
				rank[sa[j]] = p;
				++p;
			}
		}
		m = p;
	}
}

void calh()
{
	for (int i = 0; i < n; ++i)
		rank[sa[i]] = i;
	int k = 0;
	for (int i = 0; i < n; height[rank[i++]] = k)
	{	
		if (k > 0)
			--k;
		int j = sa[rank[i] - 1];
		while (a[i + k] == a[j + k])
			++k;
	}
}

bool check(int x)
{
	int big = sa[0], small = sa[0];
	for (int i = 0; i < n; ++i)
	{	
		if (height[i] >= x)
		{
			big = max(big, sa[i]);
			small = min(small, sa[i]);
			if (big - small > x)
				return true;
		}		
		else
		{
			big = sa[i];
			small = sa[i];
		}
	}
	if (big - small > x)
		return true;
	return false;
}

int read()
{
	int x;
	scanf("%d", &x);
	return x;
}

int main()
{
	//freopen("1.in", "r", stdin);
	//freopen("1.out", "w", stdout);
	while (true)
	{
		n = read();
		memset(a, 0, sizeof a);
		memset(height, 0, sizeof height);
		if (n == 0)
			break;
		for (int i = 0; i < n; ++i)
			a[i] = read();
		if (n < 10)
		{
			printf("0\n");
			continue;
		}
		for (int i = 0; i < n; ++i)
			a[i] = a[i] - a[i + 1];
		--n;
		a[n] = 0;
		for (int i = 0; i < n; ++i)
			a[i] += 180;
		buildSA();
		calh();
		int beg = 1, end = n;
		while (beg < end)
		{
			int mid = (beg + end + 1) / 2;
			if (check(mid))
				beg = mid;
			else
				end = mid - 1;
		}
		if (beg < 4)
			printf("0\n");
		else
			printf("%d\n", beg + 1);
	}
	return 0;
}

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