简答题
偏难
#19755
宝石项链 时间限制:1.0 s 内存限制:512.0 MB 题目描述 小 A 有一串包含n枚宝石的宝石项链,这些宝石按照在项链中的顺序依次以1,2,...,n编…
宝石项链
时间限制:1.0 s
内存限制:512.0 MB
题目描述
小 A 有一串包含n枚宝石的宝石项链,这些宝石按照在项链中的顺序依次以1,2,...,n编号,第n枚宝石与第1枚宝石相邻。项链由m种宝石组成,其中第i枚宝石种类为ti。
小 A 想将宝石项链分给他的好朋友们。具体而言,小 A 会将项链划分为若干连续段,并且需要保证每段都包含全部种宝石。请帮小 A 计算在满足条件的前提下,宝石项链最多可以划分为多少段。
输入格式
第一行,两个正整数n,m,分别表示宝石项链中的宝石的数量与种类数。
第二行,n个正整数ti,t2,...,tn,表示每枚宝石的种类。
输出格式
输出一行,一个整数,表示宝石项链最多可以划分的段数。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围

答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include <cstdio>
#include <algorithm>
using namespace std;
const int L = 20;
const int N = 2e5 + 5;
const int oo = 1e9;
int n, m;
int t[N], jump[L][N];
int cnt[N], tot;
int ans;
int go(int u) {
int cnt = 0, ans = 0;
for (int i = L - 1; i >= 0; i--)
if (cnt + jump[i][u] <= n) {
cnt += jump[i][u];
ans += 1 << i;
u = (u + jump[i][u] - 1) % n + 1;
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]);
t[i + n] = t[i];
}
for (int i = 1, r = 0; i <= n; i++) {
while (tot < m) {
r++;
if (!cnt[t[r]]++)
tot++;
}
jump[0][i] = r - i + 1;
if (!--cnt[t[i]])
tot--;
}
for (int i = 1; i < L; i++)
for (int j = 1; j <= n; j++) {
int tar = (j + jump[i - 1][j] - 1) % n + 1;
jump[i][j] = min(jump[i - 1][j] + jump[i - 1][tar], oo);
}
for (int i = 1; i <= n; i++)
ans = max(ans, go(i));
printf("%d\n", ans);
return 0;
}</pre>
这道题暂未补解析。