hdu3474 Necklace

57 阅读 0 评论 38 点赞

我是靠谱客的博主端庄冰淇淋，最近开发中收集的这篇文章主要介绍hdu3474 Necklace，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2010年acm多校训练赛的一道水题，不过感觉挺有趣的。

题目大意是输入一个由C和J组成的字符串。把这个字符串看成一个环，问有多少切法使从正反方向至少一个方向上能使每次C的总数都大于等于J的总数。

想了一段时间，把C换成数字1，J换成-1，问题就转化成所有前i项和都大于等于零。问题是不能每切一次就算一次前i项和，其实可以从第一次切的结果中得到后面切法中的最小数，只要最小数大于等于零就可以了。

设字符串长度为n，设a[i]为0位置切的前i项和，设mina(l, r)为a的第l项到第r项间的最小值。从i位置切相当于从0位置切的前i位值移到串尾，所以由从0位置切的结果，可以推得从i位置切的前i项和的最小值是，min(a[i] + mina(i, n), mina(1, i - 1) + a[n])，只要每次计算该值就可以了，因为求区间最小值的区间只有(1, x)、(x, n)这两种总共2n个，所以只需要用2n时间2n空间事先求出mina的所有值就好了（我一开始竟然用了ST然后MLE了……）。反方向再算一遍最后统计所有结果数就可以了，

Time: 250MS Memory:13924K

#include <cstdio>
#include <cmath>
#include <cstring>
#define MAXN 1000005
#define min(a, b) ((a)<=(b)?(a):(b))
using namespace std;
int num[MAXN];
char ans[MAXN];
char s[MAXN];
int l[MAXN];
int r[MAXN];
void initx(int n)
{
l[1] = num[1];
for (int i = 2; i <= n; i++)
l[i] = min(l[i - 1], num[i]);
r[n] = num[n];
for (int i = n - 1; i >= 1; i--)
r[i] = min(r[i + 1], num[i]);
}
int main()
{
int t;
int ANS;
int lenx;
scanf("%d", &t);
for (int k = 0; k < t; k++) {
scanf("%s", s);
lenx = strlen(s);
memset(ans, 0, sizeof(ans));
ANS = 0;
num[0] = 0;
for (int i = 0; i < lenx; i++) {
if (s[i] == 'C') num[i + 1] = num[i] + 1;
else num[i + 1] = num[i] - 1;
}
initx(lenx);
if (l[lenx] >= 0) ans[0] = 1;
for (int i = 1; i < lenx; i++) {
if (r[i + 1] - num[i] >= 0 && num[lenx] - num [i] + l[i] >= 0) ans[i] = 1;
}
for (int i = 0; i < lenx; i++) {
if (s[lenx - i - 1] == 'C') num[i + 1] = num[i] + 1;
else num[i + 1] = num[i] - 1;
}
initx(lenx);
if (l[lenx] >= 0) ans[0] = 1;
for (int i = 1; i < lenx; i++) {
if (r[i + 1] - num[i] >= 0 && num[lenx] - num [i] + l[i] >= 0) ans[lenx - i] = 1;
}
for (int i = 0; i < lenx; i++) if (ans[i] == 1) ANS++;
printf("Case %d: %dn", k + 1, ANS);
}
return 0;
}