A7253 | [GESP202512 八级] 宝石项链
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
小A有一串包含 $n$ 枚宝石的宝石项链，这些宝石按照在项链中的顺序依次以 $1,2,\ldots,n$ 编号，第 $n$ 枚宝石与第 $1$ 枚宝石相邻。项链由 $m$ 种宝石组成，其中第 $i$ 枚宝石种类为 $t_i$。
小A想将宝石项链分给他的好朋友们。具体而言，小A会将项链划分为若干连续段，并且需要保证每段都包含全部 $m$ 种宝石。请帮小A计算在满足条件的前提下，宝石项链最多可以划分为多少段。
小A想将宝石项链分给他的好朋友们。具体而言，小A会将项链划分为若干连续段，并且需要保证每段都包含全部 $m$ 种宝石。请帮小A计算在满足条件的前提下，宝石项链最多可以划分为多少段。
输入格式
第一行，两个正整数 $n,m$，分别表示宝石项链中的宝石的数量与种类数。
第二行，$n$ 个正整数 $t_1,t_2,\ldots,t_n$，表示每枚宝石的种类。
第二行，$n$ 个正整数 $t_1,t_2,\ldots,t_n$，表示每枚宝石的种类。
输出格式
输出一行，一个整数，表示宝石项链最多可以划分的段数。
输入输出样例
输入 #1
6 2 1 2 1 2 1 2
输出 #1
3
输入 #2
7 3 3 1 3 1 2 1 2
输出 #2
2
对于 40% 的测试点，保证 $2\le n\le 1000$。
对于所有测试点，保证 $2\le n\le 10^5$，$2\le m\le n$，$1\le t_i\le m$，保证 $1,2,\ldots,m$ 均在 $t_1,t_2,\ldots,t_n$ 中出现。
对于所有测试点，保证 $2\le n\le 10^5$，$2\le m\le n$，$1\le t_i\le m$，保证 $1,2,\ldots,m$ 均在 $t_1,t_2,\ldots,t_n$ 中出现。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？