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,pi) , min(x+1,pj) )
  2. min( max(x,pi) , max(x+1,pj) )

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

思路:

先观察一下这两种操作。

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

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

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

对于第一种操作,如果取x = n-1,那么就变成了max( min(n-1,pi) , min(n,pj) ) 由于里面取的是min。如果这两个数 都小于 n-1,那么这样查,查出来的就是 max(pi,pj),由此每次可以排除两个小于n-1 的数。那么对于 n-1,和 n。不管 n或者n-1在左边,那么查询结果都是 n-1。即 max( min(n-1,n-1) , min(n,pj) ) , max( min(n-1,n) , min(n,pj) ) 结果都是 n-1。那么这时候,只要再查询一次,把 pi, pj 交换位置,变成 max( min(n-1,pj) , min(n,pi) ) 如果 pi 是 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();
    }
}
上一篇:手机端自适应屏幕


下一篇:Pano2VR 展示全景图