首页 程序设计 Codeforces

题目传送门

# A

水题，疯狂打暴力就好了

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n, a[N], res[] = {1, 2, 1, 1, 3}, ans[] = {1, 2, 3, 5, 0};
void solve () {
    map<int, int> cnt;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1, x; i <= n; i++) {
        x = a[i];
        cnt[x]++;

        int check = 0;
        for (int j = 0; j < 5; j++)
            if (cnt[ans[j]] >= res[j])
                check++;
        
        if (check == 5) {
            cout << i << endl;
            return;
        }
    }

    cout << 0 << endl;
}

# B

# 题目大意

给定 nn 个数 (a1,...,an)(a_1, ..., a_n)，再给一个教练需要的团队最小实力 xx
一个团队的实力定义为： 团队人数 * 团队中的最小实力 ，如果这个团队的实力 ≥x\ge x，那么就可以组一只队伍
问：最多能组成多少队

# 题解

排序之后，倒着找就好了

  • 对于单人实力 ≥x\ge x 的，单人组队
  • 反之，慢慢往前组队，直到实力 ≥x\ge x 位置
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    void solve () {
        int res = 0;

        cin >> n >> x;

        for (int i = 1; i <= n; i++)
            cin >> a[i];

        sort(a + 1, a + n + 1);

        int idx = n;
        while (idx >= 1 && a[idx] >= x)
            idx--, res++;

        for (int i = idx; i >= 1; i--) {
            if (a[i] * (idx - i + 1) >= x)
                res++, idx = i - 1;
        }

        cout << res << endl;
    }

# C

# 题目大意

给你一个 nn，问你能不能找到一个 11 到 nn 的排列，满足循环移位 + 题目指定特性

什么是循环移位+题目指定特性？

一种 11 到 nn 的排列组合，满足在每次循环移动中都有一个点，满足这个点的值和当前的位置相同

循环移位就是每次将尾部的数移到头部

# 题解

是一道构造的水题

  • 偶数个数不能组成题目要求的排列
  • 奇数个数可以组成题目要求的排列
    只需要奇数、偶数分开输出即可，此处选择先输出 22 到 n−1n-1 的偶数，再输出 11 到 nn 的奇数
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void solve () {
        cin >> n;
        
        if (!(n & 1))
            cout << -1 << endl;
        else {
            for (int i = 2; i <= n - 1; i += 2)
                cout << i << " ";
            for (int i = 1; i <= n; i += 2)
                cout << i << " ";
            cout << endl;
        }
    }

# D

# 题目大意

给定 nn，mm，kk，分别代表场馆长、宽和参赛人数，每个人要坐 (i,j)(i,j) 的一个位置，如果一行中，有连起来的位置，就称为长凳
问，长凳的最小长度是？

# 题解

尽可能分开排位置，一行最多有 peo=⌈k/n⌉peo =\lceil{k / n}\rceil 个人
对于该行，还剩下 m−peom - peo 个空位，也就是将人分成 m−peo+1m - peo + 1 个部分，那么最多的人就是 ⌈peom−peo+1⌉\lceil{\frac{peo}{m - peo + 1}}\rceil

C++
1
2
3
4
5
6
7
8
void solve () {
    cin >> n >> m >> k;

    int peo = (k + n - 1) / n;
    int fm = m - peo + 1;

    cout << (peo + fm - 1) / fm << endl;
}

# E

# 题目大意

对于 1≤a,b≤n1 \le a,b \le n，满足 lcm(a,b)gcd(a,b)\frac{lcm(a,b)}{gcd(a,b)} 是质数的个数。

# 题解

做一点小变化：

gcd(a,b)lcm(a,b)=agcd(a,b)⋅bgcd(a,b){\frac{gcd(a,b)}{lcm(a,b)}}={\frac{a}{gcd(a,b)}·{\frac{b}{gcd(a,b)}}}

显然，如果它要是质数的话，agcd(a,b)\frac{a}{gcd(a,b)} 必须等于 11，也就是说，只需要满足 ba\frac{b}{a} 是质数即可

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void init(int n) {
    notPrime[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (!notPrime[i])
            prime.push_back(i);
        for (auto p : prime) {
            if (p * i > n)
                break;
            notPrime[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
}

void solve () {
    int n;
    cin >> n;

    int ans = 0;
    for (auto t : prime) {
        if (t > n)
            break;

        ans += n / t;
    }

    cout << ans << endl;
}

# F

拼劲全力还是无法战胜的 DPDP 题

# 题目大意

给定一个 n×mn \times m 的，由 X 和 # 组成的攀岩面

  • X 代表可以抓的，突出的岩石
  • # 代表光滑的岩壁
    现在一个人，已知他的手臂长度为 dd
    问这个人一共有多少条路径可以从第一行爬到最后一行？
  • 每层选择的点都不能低于前一个点
  • 每层最多选两个点（只有两只手）
    （求出结果并用结果对 998244353998244353998244353998244353 求模）

# 数据范围

2≤n≤2000,1≤m,d≤20002 \le n \le 2000,1 \le m,d \le 2000

# 题解

对于本题，有两种攀爬方式：

  1. 向上爬
  2. 水平方向爬
    对于有两种及以上移动方式的题目，不妨分开考虑，本题我们就可以考虑设置两个数组，一个代表从一层爬上新的一层的 ui,ju_{i,j}，一个代表水平移动的 p_
  • ui,ju_{i,j} 为从上一层到这一层的能够到达终点的路径数
  • pi,jp_{i,j} 为这一层上横向攀爬一次的能够到达终点的路径数
    由题则可推出：

ui,j=∑k=max(j−d+1,1)min(j+d−1,m)pi−1,ku_{i,j}=\sum\limits_{k=max(j-d+1,1)}^{min(j+d-1,m)} {p_{i-1,k}}

pi,j=∑k=max(j−1,1)min(j+d,m)ui,kp_{i,j} = {\sum\limits_{k=max(j-1,1)}^{min(j+d,m)}{u_{i,k}}}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const int N = 2e3 + 10;
const int MOD = 998244353;

int n, m, d;
char s[N][N];
int u[N][N], p[N][N], preU[N][N], preP[N][N];

void init() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            u[i][j] = p[i][j] = 0;
}

void solve() {
    cin >> n >> m >> d, init();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];

    for (int j = 1; j <= m; j++) {
        if (s[1][j] == 'X')
            u[1][j] = 1;

        preU[1][j] = (preU[1][j - 1] + u[1][j]) % MOD;
    }

    for (int j = 1; j <= m; j++) {
        if (s[1][j] == 'X')
            p[1][j] = (preU[1][min(j + d, m)] - preU[1][max(j - d - 1, (int)0)] + MOD) % MOD;

        preP[1][j] = (preP[1][j - 1] + p[1][j] + MOD) % MOD;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == 'X')
                u[i][j] = (preP[i - 1][min(j + d - 1, m)] - preP[i - 1][max(j - d, (int)0)] + MOD) % MOD;

            preU[i][j] = (preU[i][j - 1] + u[i][j]) % MOD;
        }
        
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == 'X')
                p[i][j] = (preU[i][min(j + d, m)] - preU[i][max(j - d - 1, (int)0)] + MOD) % MOD;

            preP[i][j] = (preP[i][j - 1] + p[i][j]) % MOD;
        }
    }

    cout << preP[n][m] << endl;
}

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝