CDZSC_2022寒假个人训练赛21级(1)

A

题意：略

题解：将n个数加起来的总和除以n即可。

#include<bits/stdc++.h>

using namespace std;

signed main(){
    
    int n;
    scanf("%d", &n);
    int sum = 0;
    for(int i = 1; i <= n; i++){
    
        int x;
        scanf("%d", &x);
        sum += x;
    }
    printf("%.10f\n", sum * 1.0 / n);
    return 0;
}

B

题意：略

题解：由于要求的是最小值，所以优先使用大面额的金钱。

#include<bits/stdc++.h>

using namespace std;
int a[] = {
    100, 20, 10, 5, 1};

signed main(){
    
    int n;
    scanf("%d", &n);
    int ans = 0;
    for(int i = 0; i < 5; i++){
    
        ans += n / a[i];
        n %= a[i];
    }
    printf("%d\n", ans);
    return 0;
}

C

题意：略

知识点：STL的应用

题解：将字符串与自己拼接，相当于长度乘2；例如：abcd -> abcdabcd
之后取出每一个长度为len(原本字符串的长度)的字串，用map记录即可。

#include<bits/stdc++.h>

using namespace std;
map<string, int> mp;

signed main(){
    
    string s;
    cin >> s;
    int len = s.length();
    s += s;
    int ans = 0;
    for(int i = 0; i < len; i++){
    
        string t = s.substr(i, len);
        if(mp[t] == 0) ans++;
        mp[t]++;
    }
    printf("%d\n", ans);
    return 0;
}

D

题意：略

题解：由于6 = 2 * 3，所以做一次乘2除6的操作相当于除以3，所以操作变成了用一步操作将n除以6或者两步操作将n除以3，如果n不能通过这两种操作变成1则无解。

#include<bits/stdc++.h>

using namespace std;

void solve(){
    
    int n;
    scanf("%d", &n);
    int ans = 0;
    while(true){
    
        if(n % 6 == 0){
    
            n /= 6;
            ans++;
        }
        else if(n % 3 == 0){
    
            n /= 3;
            ans += 2;
        }
        else{
    
            break;
        }
    }
    if(n == 1) printf("%d\n", ans);
    else printf("-1\n");
}

signed main(){
    
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

E

题意：略

题解：每次选出最小的数去减，相当于将数组排好序之后依次减去每一个数，而且如果一个数出现多次的话也只会减去一次。对于每一个a[i]而言，数组减去的是它与前一个的差值，即a[i] - a[i - 1]

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int a[N];

signed main(){
    
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    n = unique(a + 1, a + 1 + n) - a - 1;
    for(int i = 1; i <= k; i++){
    
        if(i <= n) printf("%d\n", a[i] - a[i - 1]);
        else printf("0\n");
    }
    return 0;
}

F

题意：略

题解：如果n个数之和不为0，那么将这n个数分为一段即可。如果n个数之和为0，那么找到最后一个不为0的数(下标为pos)，将(1,pos - 1)分成一段，(pos, n)分成一段即可。

#include<bits/stdc++.h>

using namespace std;
const int N = 110;
int a[N];

signed main(){
    
    int n;
    scanf("%d", &n);
    int sum = 0;
    for(int i = 1; i <= n; i++){
    
        scanf("%d", &a[i]);
        sum += a[i];
    }
    if(sum){
    
        printf("YES\n");
        printf("1\n");
        printf("1 %d\n", n);
    }
    else{
    
        int pos = -1;
        for(int i = 1; i <= n; i++)
            if(a[i]) pos = i;
        if(pos == -1) printf("NO\n");
        else{
    
            printf("YES\n");
            printf("2\n");
            printf("1 %d\n", pos - 1);
            printf("%d %d\n", pos, n);
        }
    }
    return 0;
}

G

题意：略

题解：由于数组最终形成一个等差数列，我们可以枚举a[1]的值即可知道整个数组的值，用得到的数组与原来的数组相比较，记录不同的数有多少个，答案取最优解即可。

#include<bits/stdc++.h>

using namespace std;
const int N = 1010;
int a[N], b[N], t[N];

signed main(){
    
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int ans = n;
    for(int i = 1; i <= 1000; i++){
    
        b[1] = i;
        int cnt = 0;
        for(int j = 1; j <= n; j++){
    
            b[j] = b[1] + (j - 1) * k;
            if(b[j] != a[j]) cnt++;
        }
        if(cnt < ans){
    
            memcpy(t, b, sizeof(b));
            ans = cnt;
        }
    }
    printf("%d\n", ans);
    for(int i = 1; i <= n; i++){
    
        if(t[i] > a[i]) printf("+ %d %d\n", i, t[i] - a[i]);
        else if(t[i] < a[i]) printf("- %d %d\n", i, a[i] - t[i]);
    }
    return 0;
}