Codeforces Round #720 (Div. 2)

总算又能安心刷题了

A. Nastia and Nearly Good Numbers

题意：

给定A、B，要求找出三个数 x，y，z。满足条件：

1. x + y = z
2. 其中有两个数只能整除A，有一个可以整除A*B
3. x，y，z 各不相同

思路：

显然，z是最大的，让z整除A*B就行了 。
那么令 x = A*(B-1) , y = A , z = A*B 就行了。
这个时候，可以发现，B不能等于1，同时当B等于2的时候，x 和 y 相等。那么可以令 x = 3A ，y = A ，z = 4A。

Code：

#include <bits/stdc++.h>
#define int long long
const int inf = 1e18;
using namespace std;
const int N = 1e6+7;
int t = 1,n,m;
int a[N];

signed main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        if(m == 1){
            cout<<"NO"<<endl;
        }else{
            cout<<"YES"<<endl;
            if(m != 2)
                cout<<n*(m-1)<<" "<<n<<" "<<n*m<<endl;
            else{
                cout<<n*(3)<<" "<<n<<" "<<n*4<<endl;
 
            }
        }
    }
 
}

B. Nastia and a Good Array

题意：

给定一个数组，给定一种操作，可以选择两个位置上的数，给他们重新赋值，要求保持 赋值后 两个数的最小值 等于 原来的最小值。要把数组变成相邻位置全部互质，问如何操作。

思路：

众所周知， gcd(x,x+1) = 1，也就是相邻两数是互质的。那么只需要找到数组中的一个最小值。然后有了这个最小值，就可以把数组变成一个 从最小值的位置往两边递增的数组，且增量为1。也就是
x+2 , x+1 , x , x+1 , x+2 , x+3

Code：

#include <bits/stdc++.h>
#define int long long
const int inf = 1e18;
using namespace std;
const int N = 1e6+7;
int t = 1,n,m;
int a[N];
 
signed main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i = 0  ; i < n ; i ++) cin>>a[i];
        if(n == 1){
            cout<<0<<endl;
        }else{
            int maxi = 0;
            int minn = 2e9;
            for(int i = 0 ; i < n ; i ++){
                if(a[i] < minn){
                    minn = a[i];
                    maxi = i;
                }
            }
            cout<<n-1<<endl;
            int now = minn;
            for(int i = maxi ; i < n-1 ; i ++){
                cout<<maxi+1<<" "<<i+2<<" "<<a[maxi] <<" "<< ++ now <<endl;
            }
            now = minn;
            for(int i = maxi ; i > 0 ; i --){
                cout<<maxi+1<<" "<<i<<" "<<a[maxi] <<" "<< ++ now<<endl;
            }
        }
    }
 
}

C. Nastia and a Hidden Permutation

题意：

给定一个未知的排列，即数组元素为 1 - n。
有两种询问( 1 <= x <= n-1)。

1. max( min(x,p_i) , min(x+1,p_j) )
2. min( max(x,p_i) , max(x+1,p_j) )

要求在 ⌊ 3 ⋅ n 2 \frac{3⋅n}{2} 23⋅n​⌋+30 次 询问之内， 还原这个排列。

思路：

先观察一下这两种操作。

对于第二种操作。如果知道 p_j = n。那么问题就解决了。

只需要询问 min( max(1,p_i) , max(2,n) ) 就知道p_i是多少了。因为右边永远是 n，而左边 永远是p_i，而外面 又是min，那么查询的结果就是 p_i。

于是问题变成了，如何用 n/2 次操作找到 p_j = n。

对于第一种操作，如果取x = n-1，那么就变成了max( min(n-1,p_i) , min(n,p_j) ) 由于里面取的是min。如果这两个数 都小于 n-1，那么这样查，查出来的就是 max(p_i,p_j)，由此每次可以排除两个小于n-1 的数。那么对于 n-1，和 n。不管 n或者n-1在左边，那么查询结果都是 n-1。即 max( min(n-1,n-1) , min(n,p_j) ) ， max( min(n-1,n) , min(n,pj) ) 结果都是 n-1。那么这时候，只要再查询一次，把 p_i， p_j 交换位置，变成 max( min(n-1,p_j) , min(n,p_i) ) 如果 p_i 是 n，这时候就能查出来了。

因为是两个数两个数一查，也就是 n/2 次 + 一两次。

还有一个小细节就是当 n为奇数时。如果 前面 n-1 个都没查到n。那么最后一个就是n了。

Code：

#include <bits/stdc++.h>
#define int long long
const int inf = 1e18;
using namespace std;
const int N = 1e6+7;
int t = 1,n,m;
int a[N];
 
int ask(int op,int i,int j,int x){
    cout<<"? "<<op<<" "<<i<<" "<<j<<" "<<x<<endl;
    cout.flush();
    cin>>x;
    return x;
}
 
int ans(){
    cout<<"! ";
    for(int i = 1 ; i <= n ; i ++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    cout.flush();
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        int flag = 0;
        for(int i = 1 ; i <= n-1 ; i += 2){
            int minn = ask(1,i,i+1,n-1);
            if(minn == n){
                a[i+1] = n;
                for(int j = 1 ;  j <= i ; j ++){
                    a[j] = ask(2,j,i+1,1);
                }
                for(int j = i+2 ; j <= n ; j ++){
                    a[j] = ask(2,j,i+1,1);
                }
                flag = 1;
                break;
            }else if(minn == n-1){
                minn = ask(1,i+1,i,n-1);
                if(minn == n){
                    a[i] = n;
                    flag = 1;
                    for(int j = 1 ;  j < i ; j ++){
                        a[j] = ask(2,j,i,1);
                    }
                    for(int j = i+1 ; j <= n ; j ++){
                        a[j] = ask(2,j,i,1);
                    }
                    break;
                }else{
                    a[i] = n-1;
                }
            }
        }
        if(!flag){
            a[n] = n;
            int i = n;
            for(int j = 1 ;  j < i ; j ++){
                a[j] = ask(2,j,i,1);
            }
        }
        ans();
    }
}