[杂题] SPOJ744
评论30次阅读2008.01.04 20:45; 作者：Felicia
这个题目是Sherlock推荐我做的。
题目意思是给一个长度为n（n <= 100000）的序列，里面的数满足1 <= a[i] <= n。要找一个最长的连续子串，使得这个子串是1..k的一个排列。
昨天晚上mmd想了个n^(3/2)的算法，今天Sherlock想了个nlogn的算法。我一直在考虑有没有O(n)的算法。我觉得应该有的。
今天晚上吃饭的时候忽然想出来了。回来写了果然AC。
下面是我的算法：
注意到满足题目要求的序列必有如下性质：
- 最大值等于长度
- 必含1
- 序列和为k * (k + 1) / 2
- 序列内元素不重复
如果一个序列同时满足性质3，4，那么一定符合题目要求。
于是如果做了O(n)的预处理，可以用O(1)的时间验证某序列是否满足题目要求。
然后我的算法就顺理成章了：
- 预处理s[i]，为序列的部分和
- 预处理rl[i]，为从i开始往右，最长的不重复序列的末端的下标
- 预处理m[i]，为从i开始，到i右边的第一个1（或者最右端），这一段数的最大值。
- 枚举左端点lp，则lp到其右边的第一个1（或者最右端）中的最大值为m[lp]。把m[lp]作为序列长度，则序列的右端点为lp + m[lp] – 1。利用s[i]和rl[i]数组可以验证这段序列是否满足题目要求，若满足，就更新最优解。
- 把输入序列反过来，重复步骤1－4。
以上每步的时间复杂度都是O(n)，故算法总的时间复杂度也是O(n)。
下面是我的代码
下载: spoj744.cpp
/**********************************************************************
Author: WHU_GCC
Created Time: 2008-1-4 18:06:14
File Name: spoj744.cpp
Description:
**********************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 100010;
int n;
int a[maxn];
int s[maxn];
int rl[maxn];
int hash[maxn];
int m[maxn];
int calc()
{
s[0] = 0;
for (int i = 1; i <= n; i++)
s[i] = a[i] + s[i - 1];
memset(hash, 0, sizeof(hash));
for (int i = 1, j = 1; i <= n; i++)
{
while (j <= n && hash[a[j]] == 0)
hash[a[j++]] = 1;
rl[i] = j - 1;
hash[a[i]] = 0;
}
for (int i = n; i >= 1; i--)
if (a[i] == 1)
m[i] = 1;
else if (i == n)
m[i] = a[i];
else
m[i] = max(m[i + 1], a[i]);
int ret = 0;
for (int i = 1; i <= n; i++)
if (rl[i] >= i + m[i] - 1 && s[i + m[i] - 1] - s[i - 1] == m[i] * (m[i] + 1) / 2)
ret >?= m[i];
return ret;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = calc();
reverse(a + 1, a + n + 1);
ans >?= calc();
printf("%d\n", ans);
return 0;
}
Author: WHU_GCC
Created Time: 2008-1-4 18:06:14
File Name: spoj744.cpp
Description:
**********************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 100010;
int n;
int a[maxn];
int s[maxn];
int rl[maxn];
int hash[maxn];
int m[maxn];
int calc()
{
s[0] = 0;
for (int i = 1; i <= n; i++)
s[i] = a[i] + s[i - 1];
memset(hash, 0, sizeof(hash));
for (int i = 1, j = 1; i <= n; i++)
{
while (j <= n && hash[a[j]] == 0)
hash[a[j++]] = 1;
rl[i] = j - 1;
hash[a[i]] = 0;
}
for (int i = n; i >= 1; i--)
if (a[i] == 1)
m[i] = 1;
else if (i == n)
m[i] = a[i];
else
m[i] = max(m[i + 1], a[i]);
int ret = 0;
for (int i = 1; i <= n; i++)
if (rl[i] >= i + m[i] - 1 && s[i + m[i] - 1] - s[i - 1] == m[i] * (m[i] + 1) / 2)
ret >?= m[i];
return ret;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = calc();
reverse(a + 1, a + n + 1);
ans >?= calc();
printf("%d\n", ans);
return 0;
}
发表回复
- 评论 (0)
- 引用通告 (0)
发表评论 引用通告暂无评论.
暂无引用通告