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

╰半橙微兮° 2024-03-29 15:51 65阅读 0赞

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

[Problem - B - Codeforces]: https://codeforces.com/contest/1521/problem/B