怎样提高自己网站排名,温州瓯海区营销型网站建设,中天建设集团有限公司重庆分公司,企业 cms好数组
给定一个长度为 n 的数组 a#xff0c;计算数组 a 中所有子数组中好数组的数目。
好数组定义如下#xff1a;
对于数组 al ,al1, ⋯ ,ar #xff0c;若数组中所有数的质因数种类数不超过 k#xff0c;则称为好数组。
Input
输入的第一行包含两个正整数 n,k (1≤…好数组
给定一个长度为 n 的数组 a计算数组 a 中所有子数组中好数组的数目。
好数组定义如下
对于数组 al ,al1, ⋯ ,ar 若数组中所有数的质因数种类数不超过 k则称为好数组。
Input
输入的第一行包含两个正整数 n,k (1≤k≤n≤10^5)
输入的第二行包含 n 个正整数 ai(1≤ ai ≤100)
Output
输出数组
a 中所有子数组中好数组的数目。
样例输入
4 2 2 6 5 15 样例输出
6 样例
对于所有子数组
[2] [2,6] [2,6,5] [2,6,5,15] [6] [6,5] [6,5,15] [5] [5,15] [15]
k2所以除了 [2,6,5],[2,6,5,15],[6,5,15],[6,5] 这四个子数组其他都是符合的。
解析
尺取法像尺子一样取一段尺取法通常是对数组保存一对下标即所选取的区间的左右端点然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多尤其是数据量大的时候所以说尺取法是一种高效的枚举区间的方法。
#include bits/stdc.h
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
priority_queueint,vectorint,greaterint ll;
priority_queueint rr;
typedef pairint,int PII;
const int N1e510;
int n,k;
vector int prime[N];
int a[N];
map int,int q;
void get_prime(int n)
{int mn;for (int i2;in/i;i){if (n%i0){prime[m].push_back(i);while (n%i0) n /i;}}if (n1) prime[m].push_back(n);
}
signed main()
{ios;cinnk;for (int i1;in;i){cina[i];if (prime[a[i]].size()0) get_prime(a[i]);}int cnt0;for (int r1,l1;rn;r){for (int i0;iprime[a[r]].size();i) q[prime[a[r]][i]]; while (q.size()k) //当种类数大于 k 时就从当前 l 开始减去a[l]的质数直到种类数小于等于 k 为止{ for (int i0;iprime[a[l]].size();i) {q[prime[a[l]][i]]--;if (q[prime[a[l]][i]]0) q.erase(prime[a[l]][i]);}l;}cnt r-l1;}coutcnt;return 0;
}
