网站建设的基本技术,温州外贸网站建设公司,一站式网站建设服务,山西成宁做的网站Musical Theme(后缀数组)
题意#xff1a;
n个数#xff0c;选取一段子序列#xff0c;满足以下条件#xff1a; 1.长度至少为5 2.在数列中其他位置出现过(允许转置) 3.与其他位置出现的不重叠 转置#xff1a;将恒定的正或负值添加到子序列上 例如#xff1a; n个数为…Musical Theme(后缀数组)
题意
n个数选取一段子序列满足以下条件 1.长度至少为5 2.在数列中其他位置出现过(允许转置) 3.与其他位置出现的不重叠 转置将恒定的正或负值添加到子序列上 例如 n个数为12,34,56,78,910 12345是一段子序列那6,78,910也是因为前者加5等于后者且两者没有重叠
题解
人是傻的完全不会。。。 虽然两段序列不相等但是也是有关系的他们的差分区间相同也就是其两两之间的差值一样这样题目就转化成不重叠的最长公共子串问题 可以用二分后缀数组 我们将原数组前后相减得到的新数据做后缀数组 二分的check 二分最大长度k 检查两个子串是否不想交且公共前缀k 顺序扫描height数组 (height反应的是相邻两个后缀的lcp长度) 把heightk的放在一起统计(将公共前缀k满足条件的串放在一起)这是为了实现公共前缀k
保证其中最大的sa - 最小的sa k,说明两个子串的位置距离差大于k这是为了保证不相交 SA[i]排序第i的后缀的开始位置
例如字符串“aabaaaab’” 当k2时后缀分为四组 最长公共前缀不小于k 的两个后缀一定在同一组
代码
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int maxm 100005;
const int INF 1e9 7;
int a[maxm], b[maxm], sa[maxm], s[maxm], Rank[maxm], id[maxm], Height[maxm];
int n, m;
void Rsort()
{for (int i 0; i m; i) s[i] 0;for (int i 1; i n; i) s[Rank[id[i]]] ;for (int i 1; i m; i) s[i] s[i - 1];for (int i n; i 1; i--) sa[s[Rank[id[i]]] --] id[i];
}
int cmp(int *f, int x, int y, int w)
{return f[x] f[y] f[x w] f[y w];
}
void suffix()
{for (int i 1; i n; i) Rank[i] a[i], id[i] i;m 200, Rsort();for (int w 1, p 1, i; p n; w w, m p){for (p 0, i n - w 1; i n; i) id[p] i;for (i 1; i n; i) if (sa[i] w) id[p] sa[i] - w;Rsort(), swap(Rank, id), Rank[sa[1]] p 1;for (i 2; i n; i) Rank[sa[i]] cmp(id, sa[i], sa[i - 1], w) ? p : p;}int j, k 0;for (int i 1; i n; Height[Rank[i]] k)for (k k ? k - 1 : k, j sa[Rank[i] - 1]; a[i k] a[j k]; k);
}
int judge(int x)
{int mi INF, mx -INF;for (int i 2;i n;i){if (Height[i] x){mi min(mi, min(sa[i], sa[i - 1]));mx max(mx, max(sa[i], sa[i - 1]));if (mx - mi x) return 1;}else mi INF, mx -INF;}return 0;
}
int main()
{int i, j, k, sum, ans;while (scanf(%d, n), n ! 0){ans 0;for (i 1;i n;i) scanf(%d, b[i]);for (i 1;i n;i) a[i] b[i] - b[i - 1] 100;suffix();int l 0, r n * 2;while (r - l 1){int mid (r l) / 2;if (judge(mid)) l mid, ans mid;else r mid;}if (ans 4) printf(%d\n, ans 1);else printf(0\n);}return 0;
}
