[数据结构与算法] Codeforces Round #720 (Div. 2) B. Nastia and a Good Array(1300)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Codeforces Round #720 (Div. 2) B. Nastia and a Good Array(1300) -> 正文阅读

[数据结构与算法]Codeforces Round #720 (Div. 2) B. Nastia and a Good Array(1300)

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

Link

$1300$ 构造卡了 $1$ 小时，题意在最多不超过 $n$ 次的操作下，每次操作选择两个下标不相等的数将 $a [l], a [r]$ 变成 $x, y$ 其中 $m i n (x, y) = = m i n (a [l], a [r])$ 。最终构造的数组中任意相邻数的 $g c d = = 1$
思路：找到数组中最小数的下标，因为操作的时候不要求相邻，所以我们可以通过 $n ? 1$ 次操作(除去他本身下标)，将其左右两边数进行构造。例如当前下标为 $i d x$ 的数构造值为 $a b s (i d x ? p o s) + a [p o s]$ ，那么最终的数组就构造成了每相邻数的值差为 $1$ ，那么 $g c d$ 必然也为 $1$ ，总操作数 $n ? 1$ 同样符合要求。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int a[N];
void solve(){
    int n;
    cin>>n;
    int ma=2e9;
    int pos;
    for(int i=1;i<=n;i++){cin>>a[i];if(ma>a[i]){ma=a[i],pos=i;};}//找到pos
    cout<<n-1<<endl;
    for(int i=1;i<=n;i++){
        if(i!=pos)
        cout<<pos<<' '<<i<<' '<<a[pos]<<' '<<abs(i-pos)+a[pos]<<endl;
    }
}
signed main(){
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}