B. Nastia and a Good Array(构造)

本文主要是介绍B. Nastia and a Good Array(构造)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意
给你一个序列，如果这个序列对于所有的i满足 g c d ( a i , a i − 1 ) = 1 gcd(a_i,a_{i-1})=1 gcd(ai​,ai−1​)=1，则称为这个序列为好的，我们可以每次选择 m i n ( a i , a j ) = m i n ( x , y ) min(a_i,a_j)=min(x,y) min(ai​,aj​)=min(x,y)，让 a i = x , a j = y a_i=x,a_j=y ai​=x,aj​=y,最多可以进行n次替换，使这个序列成为好的。
思路
分析这个题，可以找到的性质。
最小的数肯定会被保留下来。
__gcd(x,x+1)=1;
根据这两个性质，我们可以找到最小数的位置，然后替换左右的值，使其成为一个每次递增为1的序列，那样就可以保证每两个数之间相差都是1，那样最大公约数也一定是1.
需要注意的是，要开ll，否则会WA3.
代码

#include <bits/stdc++.h>
#define ll long long
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        ll minn=1e18;
        int flag=0;
        for(int i=1 ; i<=n ; i++)
        {
            cin>>a[i];
            if(minn>a[i])
            {
                minn=a[i];
                flag=i;
            }
        }
        ll c=minn;
        cout<<n-1<<endl;
        for(int i=flag-1 ; i>=1 ; i--)
        {
            cout<<flag<<" "<<i<<" "<<minn<<" "<<++c<<endl;
        }
        c=minn;
        for(int i=flag+1 ; i<=n ; i++)
        {
            cout<<flag<<" "<<i<<" "<<minn<<" "<<++c<<endl;
        }
    }
    return 0;
}

昨天晚上两个性质都想到了，但是当时想的是把最小值换到开头，然后从前往后选择两个数中最小的+1来构造，最后发现这样构造是错误的。

这篇关于B. Nastia and a Good Array(构造)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！