上海计算机学会2021年4月月赛C++乙组T1反子序列
发布时间
阅读量：
阅读量
题目描述
设有一个长度为n的序列为a₁,a₂,…,aₙ，则其中每一个元素均满足条件1 ≤ ai ≤ k。我们需要构造一个新的序贯，并确保其所有项都在区间[1,k]范围内同时避免成为原有序贯的一个子式结构（即无需连续）。我们的目标是在这种限制条件下找到具有最小可能长度的新序贯，并确定该最小值是多少？
输入格式
第一行：两个整数 n 与 k；
第二行：n 个整数表示 a1,a2,⋯,an。
输出格式
单个正整数：表示所求数列的最短长度、
数据范围
- 对于 50% 数据，1≤n≤100，1≤k≤10；
- 对于 100% 数据，1≤n≤100,000，1≤k≤10000；
样例数据
输入:
5 2
2 2 1 1 2
输出:
3
说明:
1,1,1 是最短的满足条件的序列之一，长度为3
输入:
9 3
1 2 3 1 2 3 1 2 3
输出:
4
解析：如果该子序列中的前i个元素包含了从1到k的所有整数，则这一个元素的所有排列都会被包含在内；类似地, 而该子序列中从第i+1个元素到第j个元素之间也包含了全部k个整数, 那么这两个元素的所有排列也会被包含进去一次；以此类推, 我们只需要统计满足条件的情况出现了多少次, 将这些情况的数量相加再加一即可得到最终结果。
详见代码：
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main() {
int n, k;
int ans = 0;
cin >> n >> k;
int cnt = 0;
for (int i = 1; i <= n; i++) {
int t;
scanf("%d", &t);
if (a[t] == 0) {//当前段未出现过
a[t] = 1;
cnt++;//当前段出现数字的个数
}
if (cnt == k) {//出全了
cnt = 0;//个数清零
ans++;//段计数加一
memset(a, 0, sizeof(a));//清空，开启新段统计
}
}
cout << ans + 1 << endl;
return 0;
}全部评论 (0)
还没有任何评论哟~