Codeforces Round #665 (Div. 2)A~C题解

发布于 2020-08-22  0 次阅读


A. Distance and Axis

题目大意:

给你一个点a的坐标n,求点b的坐标,使得∣ O B − ∣ A B ∣ ∣ = K

思路:

先判断n和k的大小关系
b在OA中每移动一个点改变的大小为2,所以判断n − k 的奇偶性即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, k;
void solve(){
    cin>>n>>k;
    if(n<=k)    cout<<k-n<<endl;
    else        cout<<((n-k)%2==0 ? 0:1)<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

B. Ternary Sequence(贪心)

题目大意:

image 18

思路:

贪心,
1、让a的2优先匹配b的1,这样贡献为2,然后再匹配b的2,贡献为0(但是可以降低b中2的数量,使得后面-2尽可能少)
2、对于b中的2,在a中优先让0去匹配,使得贡献为0,最后才让a的1去匹配,贡献-2

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
int x, y, z;
int x2, y2, z2;

void solve(){
    cin>>x>>y>>z;
    cin>>x2>>y2>>z2;
    int ans=0;

    int tep=min(z,y2);  //a中2,匹配b中1,贡献为2
    ans+=tep*2;
    z-=tep, y2-=tep;
    if(z>0){           //a中2,匹配b中2,贡献为0
        tep=min(z, z2);
        z-=tep, z2-=tep;
    }
    if(z>0){            //b中的1和2都被匹配完了,剩余的0也就无所谓了,直接输出
        cout<<ans<<endl;
        return ;
    }

    if(z2>0){           //b中2,匹配a中0,贡献0
        tep=min(x, z2);
        x-=tep, z2-=tep;
    }
    if(z2>0){           //b中2,匹配a中1,贡献-2
        tep=min(y, z2);
        ans-=tep*2;
        y-=tep, z2-=tep;
    }
    cout<<ans<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

C. Mere Array

题目大意:

给你一个长度为n的数组a,其中g c d ( ai , aj ) = min 的两两元素可以做交换,求最后能否将数组a改变成非递减的数组

思路:

可以复制一个a数组先排序,然后对于排序后的数组,与a不同的位置判断能否通过交换改变
交换操作:既然gcd等于最小值,即为该数的因子包含最小值,所以包含最小值的元素可以通过最小值进行交换,也就是ai % min == 0 即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int n, a[N], b[N], mi;

void solve(){
    cin>>n;
    mi=INF;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        b[i]=a[i];
        if(a[i]<mi) mi=a[i];
    }
    sort(b+1, b+1+n);
    int flag=0;
    for(int i=1; i<=n; i++)
        if(a[i]!=b[i] && a[i]%mi!=0)    {flag=1; break;}
    if(flag)    cout<<"NO"<<endl;
    else        cout<<"YES"<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}


平平无奇的在校大学生