Codeforces Round #669 (Div. 2) A、B题题解

Problem A - Ahahahahahahahaha

https://codeforces.com/contest/1407/problem/A

题意：

给定一个偶数数组(元素值 0，1），在删除一定的数组元素（最多 个) 以后偶数位和 是否能等于 奇数位和。

在不改变原序列的情况下输出剩下的 k个数 #card=math&code=%28n%20%2F%202%20%3C%3D%20K%20%3C%3D%20n%29)

思路：

先统计 数组整体和 , 如果 即数组中一半以上是 ，这种情况下只需删去 $ s % 2 $，奇数转偶数。具体可以参考以下代码

//Cpp
#include<bits/stdc++.h>
#define ll int long long
using namespace std;
int i, j, k;
string yn[2] = { "No\n","Yes\n" };
int main(){
    int t; cin >> t; while (t--) {
        int o = 0, e = 0, x = 0, n, s = 0; cin >> n;
        int a[n];
        for (i = 0; i < n; i++) {
            cin >> a[i]; s += a[i];
        }
        if (s > n / 2)x++;
        if (x)s -= s % 2;
        else s = n - s;
        cout << s << endl;
        for (i = 0; i < s; i++)cout << x << " ";
        cout << endl;
    }
}

#python
for _ in " "*int(input()):
    a=int(input())
    z=list(map(int,input().split()))
    s=z.count(0);k=a//2
    s1=z.count(1)
    if s>=s1:print(k);print('0 '*k)
    else:print(k+k%2);print('1 '*(k+k%2))

Problem B - Big Vova

https://codeforces.com/contest/1407/problem/B

首先把a从大到小排序，因为最大的gcd肯定最大 所以直接输出a1，然后暴力找于a1gcd最大的元素并把它做上标记以此类推，on2找完所有元素，但是如果迭代中发现gcd==1了就可以跳出循环从大到小输出其数组元素就可以了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
void solve(){
    int n;cin>>n;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n/2;i++) swap(a[i],a[n-i-1]);
    int ans=a[0],y;
    for(int i=1;i<n;i++){
        int mxm_gcd=1,y=i;
        for(int j=i;j<n;j++){
            int x=mxm_gcd;
            mxm_gcd=max(gcd(a[j],ans),mxm_gcd);
            if(mxm_gcd>x) {
                y=j;
            }
        }
        swap(a[i],a[y]);
        ans=gcd(ans,a[i]);
    }
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
    cout<<"\n";
}
int main(){
    int t;cin>>t;
    while(t--) solve();
}