What is the problem D. New Year Concert in Codeforces Round 769 (Div. 2) about?
- 内容介绍
- 文章标签
- 相关推荐
本文共计1319个文字，预计阅读时间需要6分钟。
题目解析：阅读以下内容，理解题目大意。给你一个只包含正整数的数组（a），你可以任意修改其中的元素为任意正整数。问你对（a）的每个前缀和数组（（a_1，a_1+a_2，a_1+a_2+a_3…））进行修改后，最少需要修改多少个元素。
面向题解做题题面看这里题目大意
给你一个只含正整数的数组 \(a\)，你可以任意修改其中的元素为任意正整数，问你对于 \(a\) 的每个前缀数组\((a_1,a_1a_2,a_1a_2a_3\dots)\)，至少需要修改多少个元素，才能满足：该前缀数组中不存在任何一个子区间 \(a_l,a_{l+1}\dots a_{r-1},a_r\)，满足 \(\gcd(a_l,a_{l+1}\dots a_{r-1},a_r)=r-l+1\)，即每个子区间的区间 \(\gcd\) 都不等于区间长度。
\((1\leq n\leq 2e5,~1\leq a_i\leq1e9)\)
题目分析首先考虑最暴力的算法，从左到右，对于每个位置 \(i\)，我们对他前面的每一个位置 \(j(1\leq j\leq i)\) 都判断一下，看下 \(a_j\) 到 \(a_i\) 的区间 \(\gcd\) 是否等于区间长度，如果每个都不等，则不需要修改；否则，至少要修改一个数，修改谁呢？修改为啥呢？设我们要修改的数为 \(a_k\)，注意到可以修改为任意正整数，显然我们只需要将其修改成一个特别大的质数，就可以在保证 \([1,i]\) 区间合法性的同时，让处在后面的区间 \([k+1,n]\) 中的每个位置 \(i'\) 只需判断 \([k+1,i']\) 即可，所以为了保证修改次数为最小，\(k\) 一定要取最大值，因此 \(k=i\)，只需修改 \(a_i\) 即可。
区间 \(\gcd\) 可以用 st表 或者 线段树 \(n\log n\) 预处理出来，然后每次查询区间 \(\gcd\) 的时间复杂度是 \(\log n\) 总复杂度 \(O(n^2\log n)\)，伪代码如下：
int last=0,ans=0; //last记录的是上一次修改的位置,j只需要遍历[last+1,i]即可,小优化
for(int i=1;i<=n;i++){
bool flag=true;
for(int j=i;j>last;j--){
if(query(j,i)==i-j+1){
flag=false;
break;
}
}
if(!flag) ans++,last=i;
cout << ans << " ";
}
接下来考虑优化，注意到重点是对于每一个非法的区间，我们都要修改其右端点的数，显然，对于一个左端点 \(l_x\)，最多只能有一个右端点跟它构成非法区间。（左端点固定的区间 \(\gcd\) 是非递增的，而区间长度又是递增的，假如这个非法区间为 \([l_x,r_x]\)，那么 \(r_x\) 之后的区间 \(\gcd\) 只会不变或者更小，而区间长度一定会变大，所以一定不相等）
因此，对于每个位置 \(i\)，我们需要找到以它为左端点的非法区间的右端点，记为 \(v_i\)，如果不存在则令 \(v_i=0\)。那么我们就可以 \(O(n)\) 求出答案：
long long nex=inf; //在多个非法区间中选出最小的右端点,即为下一次要修改的位置
for(int i=1;i<=n;i++){
if(v[i]){
nex=min(nex,v[i]);
}
if(i==nex){
ans++;
nex=inf;
}
cout << ans << " ";
}
现在问题转化为了找到每个非法区间，通过上面的分析，发现 \(\gcd([l_x,r_x])\geq r_x-l_x+1\) 这个式子具有单调性，如果 \([l_x,r_x]\) 满足该式子，则 \([l_x,r_y(l_x\leq r_y\leq r_x)]\) 也一定满足，因此我们可以固定 \(l_x\)，然后二分查找最大的 \(r_x\) 满足 \(\gcd([l_x,r_x])\geq r_x-l_x+1\)，最后再判断一下是否相等，相等就找到了一个非法区间。时间复杂度 \(O(n\log n\log n)\))。
代码实现#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=LLONG_MAX/10;
constexpr int maxn=2e5+6;
long long n,m,k,ans,_=1,a[maxn],v[maxn];
long long f[maxn][22];
long long lg[maxn];
long long gcd(long long a,long long b){
if(!a||!b) return a+b;
while((a%=b)&&(b%=a)) ;
return a+b;
}
void init(){
lg[0]=-1;
for(int i=1;i<=n;i++){
f[i][0]=a[i],lg[i]=lg[i>>1]+1;
}
lg[0]=0;
for(int j=1;j<=lg[n];j++){
for(int i=1;i+(1<<j)<n+2;i++){
f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
long long query(int l,int r){
int len=lg[r-l+1];
return gcd(f[l][len],f[r-(1<<len)+1][len]);
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
init();
for(int i=1;i<=n;i++){
int l=i,r=n,mid,rr;
while(l<=r){
mid=l+r>>1;
long long d=query(i,mid);
if(d>=mid-i+1){
rr=mid;
l=mid+1;
}
else {
r=mid-1;
}
}
if(query(i,rr)==rr-i+1){
v[i]=rr;
}
}
long long nex=inf;
for(int i=1;i<=n;i++){
if(v[i]){
nex=min(nex,v[i]);
}
if(i==nex){
ans++;
nex=inf;
}
cout << ans << " ";
}
}
本文共计1319个文字，预计阅读时间需要6分钟。
题目解析：阅读以下内容，理解题目大意。给你一个只包含正整数的数组（a），你可以任意修改其中的元素为任意正整数。问你对（a）的每个前缀和数组（（a_1，a_1+a_2，a_1+a_2+a_3…））进行修改后，最少需要修改多少个元素。
面向题解做题题面看这里题目大意
给你一个只含正整数的数组 \(a\)，你可以任意修改其中的元素为任意正整数，问你对于 \(a\) 的每个前缀数组\((a_1,a_1a_2,a_1a_2a_3\dots)\)，至少需要修改多少个元素，才能满足：该前缀数组中不存在任何一个子区间 \(a_l,a_{l+1}\dots a_{r-1},a_r\)，满足 \(\gcd(a_l,a_{l+1}\dots a_{r-1},a_r)=r-l+1\)，即每个子区间的区间 \(\gcd\) 都不等于区间长度。
\((1\leq n\leq 2e5,~1\leq a_i\leq1e9)\)
题目分析首先考虑最暴力的算法，从左到右，对于每个位置 \(i\)，我们对他前面的每一个位置 \(j(1\leq j\leq i)\) 都判断一下，看下 \(a_j\) 到 \(a_i\) 的区间 \(\gcd\) 是否等于区间长度，如果每个都不等，则不需要修改；否则，至少要修改一个数，修改谁呢？修改为啥呢？设我们要修改的数为 \(a_k\)，注意到可以修改为任意正整数，显然我们只需要将其修改成一个特别大的质数，就可以在保证 \([1,i]\) 区间合法性的同时，让处在后面的区间 \([k+1,n]\) 中的每个位置 \(i'\) 只需判断 \([k+1,i']\) 即可，所以为了保证修改次数为最小，\(k\) 一定要取最大值，因此 \(k=i\)，只需修改 \(a_i\) 即可。
区间 \(\gcd\) 可以用 st表 或者 线段树 \(n\log n\) 预处理出来，然后每次查询区间 \(\gcd\) 的时间复杂度是 \(\log n\) 总复杂度 \(O(n^2\log n)\)，伪代码如下：
int last=0,ans=0; //last记录的是上一次修改的位置,j只需要遍历[last+1,i]即可,小优化
for(int i=1;i<=n;i++){
bool flag=true;
for(int j=i;j>last;j--){
if(query(j,i)==i-j+1){
flag=false;
break;
}
}
if(!flag) ans++,last=i;
cout << ans << " ";
}
接下来考虑优化，注意到重点是对于每一个非法的区间，我们都要修改其右端点的数，显然，对于一个左端点 \(l_x\)，最多只能有一个右端点跟它构成非法区间。（左端点固定的区间 \(\gcd\) 是非递增的，而区间长度又是递增的，假如这个非法区间为 \([l_x,r_x]\)，那么 \(r_x\) 之后的区间 \(\gcd\) 只会不变或者更小，而区间长度一定会变大，所以一定不相等）
因此，对于每个位置 \(i\)，我们需要找到以它为左端点的非法区间的右端点，记为 \(v_i\)，如果不存在则令 \(v_i=0\)。那么我们就可以 \(O(n)\) 求出答案：
long long nex=inf; //在多个非法区间中选出最小的右端点,即为下一次要修改的位置
for(int i=1;i<=n;i++){
if(v[i]){
nex=min(nex,v[i]);
}
if(i==nex){
ans++;
nex=inf;
}
cout << ans << " ";
}
现在问题转化为了找到每个非法区间，通过上面的分析，发现 \(\gcd([l_x,r_x])\geq r_x-l_x+1\) 这个式子具有单调性，如果 \([l_x,r_x]\) 满足该式子，则 \([l_x,r_y(l_x\leq r_y\leq r_x)]\) 也一定满足，因此我们可以固定 \(l_x\)，然后二分查找最大的 \(r_x\) 满足 \(\gcd([l_x,r_x])\geq r_x-l_x+1\)，最后再判断一下是否相等，相等就找到了一个非法区间。时间复杂度 \(O(n\log n\log n)\))。
代码实现#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=LLONG_MAX/10;
constexpr int maxn=2e5+6;
long long n,m,k,ans,_=1,a[maxn],v[maxn];
long long f[maxn][22];
long long lg[maxn];
long long gcd(long long a,long long b){
if(!a||!b) return a+b;
while((a%=b)&&(b%=a)) ;
return a+b;
}
void init(){
lg[0]=-1;
for(int i=1;i<=n;i++){
f[i][0]=a[i],lg[i]=lg[i>>1]+1;
}
lg[0]=0;
for(int j=1;j<=lg[n];j++){
for(int i=1;i+(1<<j)<n+2;i++){
f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
long long query(int l,int r){
int len=lg[r-l+1];
return gcd(f[l][len],f[r-(1<<len)+1][len]);
}
int main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
init();
for(int i=1;i<=n;i++){
int l=i,r=n,mid,rr;
while(l<=r){
mid=l+r>>1;
long long d=query(i,mid);
if(d>=mid-i+1){
rr=mid;
l=mid+1;
}
else {
r=mid-1;
}
}
if(query(i,rr)==rr-i+1){
v[i]=rr;
}
}
long long nex=inf;
for(int i=1;i<=n;i++){
if(v[i]){
nex=min(nex,v[i]);
}
if(i==nex){
ans++;
nex=inf;
}
cout << ans << " ";
}
}