Codeforces Round #720 (Div. 2) B. Nastia and a Good Array

Problem - B - Codeforces

题意

给定一个序列一次操作可以选i,j,x,y使a[i]=x,a[j]=y其中满足min(a[i],a[j])=min(x,y)最多操作n次问你怎么操作可以使所有相邻的数使得gcd(a[i],a[i+1])=1输出操作序列

思路

首先这是构造题我们把条件列出来

1.gcd(a[i],a[i+1])=1

2.min(a[i],a[j])=min(x,y)

3.最多修改n次

对于第一个典中典中典构造x和x+1即可

对于第二个我们需要确定一种操作顺序使每个数只被改一次

对于第三个直接取n保证每个数只被改一次

如果顺序修改肯定不行这样不能保证每个数只被改一次因为不是排好序的这给出的是个序列我们不能手动给它排序

那么是什么顺序呢

为了满足第2个条件我们取全局的最小值然后拿这个值和其他的数操作

设最小值下标是k

我们让k+2,k+4....为mi

让k-2,k-4....为mi

让k+1,k+3....变成mi+1

让k-1,k-3....变成mi+1

这样就构造好了

这道题关键在于通过第二个条件想出拿全局最小值去和别的数操作

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=2e5+10,mod=1e9+7;
int n;
int a[mxn];
void solve(){
    cin>>n;
    int mi=1e18,ansi;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(mi>a[i]){
            mi=a[i];
            ansi=i;
        }
    }
    cout<<n-1<<'\n';
    for(int i=ansi-2;i>=1;i-=2) cout<<i<<" "<<ansi<<" "<<mi<<" "<<mi<<'\n';
    for(int i=ansi+2;i<=n;i+=2) cout<<ansi<<" "<<i<<" "<<mi<<" "<<mi<<'\n';
    for(int i=ansi-1;i>=1;i-=2) cout<<i<<" "<<ansi<<" "<<mi+1<<" "<<mi<<'\n';
    for(int i=ansi+1;i<=n;i+=2) cout<<ansi<<" "<<i<<" "<<mi<<" "<<mi+1<<'\n';
}
signed main(){
    int __=1;cin>>__;
    while(__--)solve();return 0;
}