什么？只是一道蓝题？
什么？我tm不会做？
什么？你告诉我是普及月赛T3？
题目链接
题意
给定一个长度为 的序列 ，可以进行如下操作若干次：
- 选定一个区间 ，令 ；
- 令所有的 。
一次操作的代价是 ， 为给定常数。
求将所有数字变得相同的最小总代价。
题解
这篇题解用到了一个叫做 baka's trick 的技巧。
玛卡巴卡（
首先这道题还是要分析一些性质的。
性质 ：最终所有数字一定都是
。
显然，第
个位置上的数字，最终一定是
的因数，而所有数字都要相等，所以他们必然都是所有数字的最大公倍数。
性质 ：所有位置最多参与一次操作。
这个想一想大概也能想出来。
同一个位置被操作两次，显然不如取两次操作的并，直接操作一次。
设 。
这样我们大概就能设计出一个 dp：
表示区间只涉及 的位置，并将前 个位置都变成 的最小总代价。
考虑转移。
若初始就有 ，那么 可以不进行操作，就有转移 。
否则，枚举最右侧的操作区间为 ，一定有 。
暴力转移，时间复杂度为 ，可以拿到 分。
设 ，并对于每一个 ，二分出最大的，合法的 ，可以替代上面的转移：
时间复杂度 ，可以拿到
分。
baka's trick
不难发现，时间复杂度瓶颈主要在于二分与 gcd。
那么能不能加速这个寻找
的过程呢？
首先会发现，当 增长时， 单调不降，首先考虑双指针。
不难发现，我们双指针过程中，加入一个元素复杂度为 ，但是删除需要 ，很难蚌。
这个时候，就需要一个技巧，就是 baka's trick，不带删的双指针。
普通的双指针，我们会维护三个值 ，表示当前区间为 ，值为 。
进行 baka's trick 时，我们再额外维护一个值 ，并对于所有的 ，维护出 或
。
初始时，有 。
当右端点右移时，我们可以在 时间内更新出新的 。
使用 和 可以在 时间内算出当前区间 的权值。
当左端点左移时，若有 ，则令 ，并重新更新 。
可以证明，这个复杂度是均摊 的。
这样，我们就将寻找
的复杂度变为了 ，就可以进行我们上边的dp了。
总复杂度 ，可以通过这道题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
ll dp[4000001];
ll f[4000001];
int a[4000001];
int v[4000001];
int l,r,mid;
int base;
int n,k;
inline int gcd(int a,int b)
{
int r=a%b;
while(r)
{
a=b;
b=r;
r=a%b;
}
return b;
}
inline void update()
{
int now=0;mid=r;
for(int i=r;i>=l;i--) v[i]=now=gcd(now,a[i]);
}
inline int get(int l,int r){ return gcd(v[l],v[r]);}
int main()
{
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read(),base=gcd(base,a[i]);
l=mid=1;
for(int i=1;i<=n;i++)
{
r=i,v[r]=gcd(v[r-1],a[i]);
if(a[i]==base)
{
dp[i]=min(dp[i-1],f[i-1]+i+k);
f[i]=min(f[i-1],dp[i]-i);
continue;
}
while(get(l,r)==base)
{
l++;
if(mid<l) update();
}
if(l==1) dp[i]=inf;
else dp[i]=f[l-2]+i+k;
f[i]=min(f[i-1],dp[i]-i);
}
printf("%lld\n",dp[n]);
return 0;
}
|
感谢观看！