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

题目分析

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

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100000+50;
int T, n, m;

struct node{
    int t, value;
}tree[N];
bool com(node x, node y){
    return x.value > y.value;
}
int main(){
    scanf("%d", &T);
    while(T--){
        long long ans = 0;
        scanf("%d", &n);
        memset(tree , 0, sizeof(tree));
        for (int i = 1; i <= n; i++){
            scanf("%d", &tree[i].value); ans += tree[i].value;
        }
        for (int i = 1; i < n; i++){
            int k, p;
            scanf("%d%d", &k, &p);
            tree[k].t++; tree[p].t++;
        }
        sort(tree + 1, tree + n + 1, com);
        printf("%lld", ans);
        for (int i = 1; i <= n; i++)
        {
            while (tree[i].t > 1)
            {
                ans += tree[i].value;
                tree[i].t--;
                printf(" %lld", ans);
            }
        }
        putchar('\n');

    }
    return 0;
}