Codeforces Round #720 (Div. 2) B. Nastia and a Good Array-蒲公英云

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;
}