2022牛客寒假算法基础集训营1

本文主要是介绍2022牛客寒假算法基础集训营1，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A
首先把原数组中的数按题目要求进行转化
状态表示\(f[i][j]\)表示从前\(i\)个选，凑成的数组为\(j\)的所有方案数

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, MOD = 998244353;
int n;
int a[N], f[N][10];
signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i ++ )  scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i ++ ) {
        int m = a[i];
        while (m >= 10) {
            int sum = 0;
            while (m) {
                sum += m % 10;
                m /= 10;
            }
            m = sum;
        }
        a[i] = m;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= 9; j ++ ) {
            f[i][j] = (f[i][j] + f[i - 1][j]) % MOD;
            int m = (a[i] + j) % 10;
            if (a[i] + j >= 10)    m ++;
            f[i][m] = (f[i][m] + f[i - 1][j]) % MOD;
        }
        f[i][a[i]] = (f[i][a[i]] + 1) % MOD;
    }
    for (int i = 1; i <= 9; i ++ )
        printf("%d ", f[n][i]);
    return 0;
}

C
模拟

#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
    scanf("%d", &n);
    int cnt = 0;
    int last1 = 0, last2 = 0, last3 = 0;
    for (int i = 1; i <= n; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c) {
            if (last3 < 1) {
                cnt ++;
                last1 ++;
                last2 ++;
                last3 = 1;
            }
        }
        if (b) {
            if (last2 < 2) {
                cnt += (2 - last2);
                last1 += (2 - last2);
                last2 = 2;
            }
        }
        if (a) {
            if (last1 < 3) {
                cnt += (3 - last1);
                last2 += (3 - last1);
                last1 = 3;
            }
        }
        last3 = last2;
        last2 = last1;
        last1 = 0;
    }
    printf("%d\n", cnt);
    return 0;
}

D
对于问题一打表找规律
对于问题二从大到小遍历，找到第一个质数

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T, n, l, r;
int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}
signed main() {
    scanf("%d", &T);
    while (T -- ) {
        scanf("%lld", &n);
        if (n == 1) {printf("-1\n"); continue;}
        int sum = 1;
        for (int i = 0; i <= 24; i ++ ) {
            if (sum * primes[i] > n) {
                printf("%d ", sum);
                break;
            }
            else sum *= primes[i];
        }
        for (int i = n; ; i -- ) {
            if (is_prime(i)) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}

E
签到

#include <bits/stdc++.h>
using namespace std;
int T, n, m;
int main() {
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d%d", &n, &m);
        if (n == m && m == 1) {printf("1\n"); continue;}
        if (m == 1) {printf("-1\n"); continue;}
        int k = (int)ceil((n - m) * 1.0 / (m - 1) * 1.0);
        printf("%d\n", k * 2 + 1);
    }
    return 0;
}

F
签到

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T, n, m, sum;
int a[N];
int main() {
    scanf("%d", &T);
    while (T -- ) {
        sum = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ )  scanf("%d", &a[i]);
        for (int i = 1; i <= n; i ++ ) {
            if (a[i] >= m)  sum ++;
            else sum --;
        }
        printf("%d\n", sum > 0 ? sum : -1);
    }
    return 0;
}

H
前缀和

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, tot, sum;
int a[N], b[N], s[N];
signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i ++ )  scanf("%lld", &a[i]);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i ++ )
        s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= n; i ++ ) {
        int l = i, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= 1000 - a[i]) r = mid;
            else l = mid + 1;
        }
        int k = n - l + 1;
        if (k >= l - i)    sum += a[i] * (k - l + i);
        else sum -= a[i] * (l - i - k);
        sum += s[n] - s[l - 1];
        sum -= s[l - 1] - s[i - 1];
        tot += l - i;        
    }
    if (n * (n + 1) / 2 - tot >= tot)    sum -= (n * (n + 1) / 2 - tot * 2) * 1000;
    else sum += (tot * 2 - n * (n + 1) / 2) * 1000;
    printf("%lld\n", sum);
    return 0;
}

I
概率 + 逆元
答案为\(m \times \frac{2^n-2}{2^n}\)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int T, n, m;
int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k) {
        if (k & 1)    res = (long long)res * t % p;
        t = (long long)t * t % p;
        k >>= 1;
    }
    return res;
}
int main() {
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d%d", &n, &m);
        printf("%d\n", (long long)m * (qmi(2, n, MOD) - 2) % MOD * (qmi(qmi(2, n, MOD), MOD - 2, MOD)) % MOD);
    }
    return 0;
}

#include <bits/stdc++.h>
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int N = 1e4 + 10;
int T, n, m, s;
int a[N], b[N];
int main() {
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d%d%d", &n, &m, &s);
        vector<PII> v;
        for (int i = 1; i <= n; i ++ ) {
            int x;
            scanf("%d", &x);
            v.push_back({x, 1});
        }
        for (int i = 1; i <= m; i ++ ) {
            int x;
            scanf("%d", &x);
            v.push_back({x, 0});
        }
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        if (n < (s + 1) / 2) {printf("-1\n"); continue;}
        else {
            int sum0 = 0, sum1 = 0, sum = 0;
            for (int i = 0; sum0 + sum1 < s; i ++ ) {
                if (v[i].y == 1) {
                    sum0 ++;
                    sum += v[i].x;
                }
                else {
                    if (sum1 < s / 2) {
                        sum += v[i].x;
                        sum1 ++;
                    }
                }
            }
            printf("%d\n", sum);
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int T, n, x, y;
double ans;
char s[N];
int main() {
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d", &n);
        scanf("%s", s + 1);
        x = 0, y = 0, ans = 0.0;
        for (int i = 1; i <= n; i ++ ) {
            if (s[i] == 'L')    x --;
            else if (s[i] == 'R')   x ++;
            else if (s[i] == 'U')    y ++;
            else    y --;
            ans = max(ans, sqrt(x * x * 1.0 + y * y * 1.0));
        }
        printf("%.10lf\n", ans);
    }
    return 0;
}

这篇关于2022牛客寒假算法基础集训营1的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

2022牛客寒假算法基础集训营1

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯