- 题目描述:请重新排列某个仅包含2和3的数组,使得数组的所有连续子数组权值之和最小
- 数组的权值定义为,数组中所有元素之积的因子个数,例如:rank([2,3])=4
x = p 1 c 1 × p 2 c 2 × p 3 c 3 ⋅ ⋅ ⋅ × p k c k r a n k = ( c 1 + 1 ) × ( c 2 + 1 ) × ( c 3 + 1 ) ⋅ ⋅ ⋅ × ( c 2 + 1 ) x = p_1^{c_1} \times p_2^{c_2}\times p_3^{c_3} \cdot\cdot\cdot \times p_k^{c_k}\\ rank = (c_1+1)\times (c_2+1) \times (c_3+1) \cdot\cdot\cdot \times (c_2+1) x=p1c1×p2c2×p3c3⋅⋅⋅×pkckrank=(c1+1)×(c2+1)×(c3+1)⋅⋅⋅×(c2+1)
- 本题 P1=2 ,P2 =3,2和3互质,所以子数组的权值为(2的个数+1)*(3的个数+1)
2 n + 1 个数字, n + 1 个 2 , n 个 3 ,长度为 2 n 的连续子数组的权值 顺序的情况 : ( n + 1 + 1 ) ∗ ( n − 1 + 1 ) + ( n + 1 + 1 ) ∗ ( n − 1 + 1 ) = ( n + 2 ) ∗ ( n ) + ( n + 2 ) ∗ ( n ) 乱序为 : ( n + 1 ) ∗ ( n + 1 ) + ( n + 1 ) ∗ ( n + 1 ) 2n+1个数字,n+1个2,n个3,长度为2n的连续子数组的权值\\ 顺序的情况 : \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ (n+1+1)*(n-1+1)+ (n+1+1)*(n-1+1)\\ = (n+2)*(n)+ (n+2)*(n)\\ 乱序为: \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ (n+1)*(n+1)+(n+1)*(n+1) 2n+1个数字,n+1个2,n个3,长度为2n的连续子数组的权值顺序的情况: (n+1+1)∗(n−1+1)+(n+1+1)∗(n−1+1)=(n+2)∗(n)+(n+2)∗(n)乱序为: (n+1)∗(n+1)+(n+1)∗(n+1)
例如:[2,2,2,3,3]和[2,2,3,3,2]的长度为4的连续子数组
- 所以在和的个数相同的情况下,越分散乘积就越大,越集中乘积就越小,排列应为顺序的情况
对于某个权值为 K 的数组,将 2 换成 3 的权值为 K ∗ ( N 2 − 1 ) + 1 N 2 + 1 ∗ ( N 3 + 1 ) + 1 N 3 + 1 对于某个权值为K的数组,将2换成3的权值为\\ K*\frac{(N_2-1) +1}{ N_2+1}*\frac{(N_3+1)+1}{N_3+1} 对于某个权值为K的数组,将2换成3的权值为K∗N2+1(N2−1)+1∗N3+1(N3+1)+1
例如:[2,2,2],K=(3+1) * (0+1)=4,
[2,2,3]K= (2+1) * (1+1)=6 = 4* 3 4 \frac{3}{4} 43* 2 1 \frac{2}{1} 12
CG
- 参考: 权值不超过K的连续子数组的数量
- 本题的解答,右边界从0到n,对于每个右边界,左边界从0开始,如果窗口中的因子数量满足条件(大于或等于K),则收缩左边界直到不满足条件,这样可以得出有几个满足条件的连续子数组。
- 注:在每次重新计算时,作者并没有将j,即左窗口放回到0,因为有边界扩大,之前的j个窗口满足条件,再窗口中加入数值只能增加权值
- 注:作者使用了匿名函数来计算当前窗口的权值: lambda 表达式——匿名函数 auto i= [ ] () { };, 填入 & 时,代表通过引用传递捕捉父作用域的变量 https://blog.csdn.net/lievech/article/details/121393346
#include <stdio.h>
#include<unordered_map>
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
int main() {int n, k;cout<<"N长度的vector有多少连续子数组的权值不小于K"<<endl;cin >> n >> k;vector<int> a(n);unordered_map<int, int> mp;ll cnt = 1, res = 0;//因子数量(cnt)auto addv = [&](int x, int t) {for (int i = 2; i * i <= x; i++) {while (x % i == 0) {cout<<i<<" "<<mp[i]<<endl;cnt /= (mp[i] + 1);cout<<"cnt"<<"<-->"<<cnt<<endl;mp[i] += t;cnt *= (mp[i] + 1);cout<<"cnt"<<"<-->"<<cnt<<endl;x /= i;}}if (x > 1) {cnt /= (mp[x] + 1);cout<<"cnt"<<"-->"<<cnt<<endl;mp[x] += t;cnt *= (mp[x] + 1);}};for (int i = 0, j = 0; i < n; i++) {cin >> a[i];addv(a[i], 1);while (j <= i && cnt >= k) {addv(a[j], -1);j++;}res += j;}cout<<"----->";cout << res << "\n";
}
N长度的vector有多少连续子数组的权值不小于K
3
4
6
2 0
cnt<-->1
cnt<-->2
cnt-->2
2 1
cnt<-->2
cnt<-->2
cnt-->1
N长度的vector有多少连续子数组的权值不小于K
3
4
9
3 0
cnt<-->1
cnt<-->2
3 1
cnt<-->1
cnt<-->3
6
2 0
cnt<-->3
cnt<-->6
cnt-->2
3 3
cnt<-->2
cnt<-->6
3 2
cnt<-->2
cnt<-->4
2 1
cnt<-->2
cnt<-->2
cnt-->1
2
cnt-->1
----->4