欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #720 (Div. 2)

程序员文章站 2024-03-21 13:22:58
...

总算又能安心刷题了

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} 23n⌋+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();
    }
}
相关标签: Div2 Codeforces