简答题 偏难
#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

6 2
1 2 1 2 1 2

输出样例 1

3

输入样例 2

7 3
3 1 3 1 2 1 2

输出样例 2

2

数据范围

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; 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 &gt;= 0; i--)         if (cnt + jump[i][u] &lt;= n) {             cnt += jump[i][u];             ans += 1 &lt;&lt; i;             u = (u + jump[i][u] - 1) % n + 1;         }     return ans; } int main() {     scanf("%d%d", &amp;n, &amp;m);     for (int i = 1; i &lt;= n; i++) {         scanf("%d", &amp;t[i]);         t[i + n] = t[i];     }     for (int i = 1, r = 0; i &lt;= n; i++) {         while (tot &lt; m) {             r++;             if (!cnt[t[r]]++)                 tot++;         }         jump[0][i] = r - i + 1;         if (!--cnt[t[i]])             tot--;     }     for (int i = 1; i &lt; L; i++)         for (int j = 1; j &lt;= 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 &lt;= n; i++)         ans = max(ans, go(i));     printf("%d\n", ans);     return 0; }</pre>
这道题暂未补解析。