CodeForces Good Bye 2020 A-D

A. Bovine Dilemma

题目分析

题意：给你一组数,看他们两两组合的差有多少种情况 。

那么直接求出两两组合的差，然后去重即可得出答案。去重既可以选择开一个数组标记，也可以选择用STL的unique实现

AC代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6   100;
int q[N], T, n, ans;
bool s[N];//数组标记
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while(T--){
        memset(s, 0, sizeof(s));
        cin >> n;
        ans = 0;
        for(int i = 0; i < n; i  ) cin >> q[i];
        for(int i = 1; i < n; i  ){
            for(int j = 0; j < i; j  )
                if(!s[q[i] - q[j]])
                    s[q[i] - q[j]] = 1, ans  ;
        }
        cout << ans << endl;
    }
    
    return 0;
}

#include<bits/stdc  .h>
 using namespace std;
const int N = 1e6   1000;
 int q[N];
vector<int> arr;//vector储存，然后unqiue去重
int T, n, m;
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while(T--){
        cin >> n;
        for(int i = 0; i < n; i  ) cin >> q[i];
        for(int i = 1; i < n; i  )
            for(int j = 0; j < i; j  )
                arr.push_back(q[i] - q[j]);
        
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());
        cout << arr.size() << endl;//最后输出去重后剩下的元素的数量
        arr.clear();
    }
 
    return 0;
}

B. Last minute enhancements

题目分析

题意：给你一组数字，你能给每一个数字加上1，问你进行多次操作后最多能让这组数字有几个不同的数字

我们只需要遍历数组，如果数字未出现过，那么给它标记一下，然后ans ；如果数字出现过，再看看它加上1之后有没有出现过，如果加上1之后没有出现过，那么标记一下，ans ， 最终输出答案。

注意

• 注意x的数据范围

• 本题的解题思路有一个前提：所给的数据是有序的。虽然给的样例是有序的数组，但是题目并没有保证测试数据会给有序的数组

• 每一次询问结束之后清空标记的数组，同时也要选择适当的数组，防止TLE

AC代码

#include<bits/stdc  .h>
using namespace std;
const int N = 1e6   1000;
int q[N];
bool s[N];

int T, n;
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while(T--){
        memset(s, 0, sizeof(s));
        ans = 0;
        cin >> n;
        for(int i = 0; i < n; i  ) cin >> q[i];
        sort(q, q   n);
        for(int i = 0; i < n; i  ){
            if(!s[q[i]]) s[q[i]] = 1, ans  ;//不改变值的情况
            else if(!s[q[i]   1]) s[q[i]   1] = 1, ans  ;//加上1的情况
        }
        cout << ans << endl;
    }
 
    return 0;
}

---

C. Canine poetry

题目分析

题意：给几个字符串，问操作几次能让字符串所有的字串不构成回文

这道题是一道贪心题目，我们只需考虑aa 和 aba 这两种情况，用一个非小写字母破坏掉就可以达成目的了

AC代码

#include<bits/stdc  .h>
using namespace std;
int T, ans;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> T;
    while(T--){
        ans = 0;
        string str;
        cin >> str;
        for(int i = 1; i < str.length(); i  ){
            if(str[i] == str[i - 1]){
                str[i] = '?', ans  ;
            }
            else if(str[i] == str[i - 2] && i > 1){//小细节要处理好
                    str[i] = '?', ans  ;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

---

D. 13th Labour of Heracles

题目分析

本题应对点考虑贡献度，点权越大的点计算次数越多，对于答案的贡献度也就越多（答案的值也就越大），所以应该采用贪心策略，从最大的权值开始，同时记录一下点出现的情况。详情请见代码

AC代码

//qwq
#include<bits/stdc  .h>
using namespace std;
const int N = 100000 50;
int T,n,m;
long long ans;
struct node{
    int d,a;
}tree[N];
bool cmp(node x,node y){
    return x.a>y.a;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n); ans=0;
        memset(tree,0,sizeof(tree));
        for (int i=1; i<=n;   i){
            scanf("%d",&tree[i].a); ans =tree[i].a;
        }
        for (int i=1,q1,q2; i<n;   i){
            scanf("%d%d",&q1,&q2);
            tree[q1].d  ; tree[q2].d  ;
        }
        sort(tree 1,tree n 1,cmp);
        printf("%lld",ans);
        for (int i=1; i<=n;   i){
            while (tree[i].d>1){
                ans =tree[i].a;
                tree[i].d--;
                printf(" %lld",ans);
            }
        }
        cout << endl;
    }
    return 0;
}

来源：https://www./content-4-805351.html