牛客网 - 7612. 2020 牛客 NOIP 赛前集训营 - 普及组（第五场）

#A-购物

#题面

#题目描述

超市进行了买 k 送一的活动，商品的单价是 x 元，牛妹想至少买 n 件商品， 输出最少需要花费多少钱。

#输入描述

第一行一个整数 $T\leq 100$，表示 $T$ 组数据。

接下来 T 行，每行 3 个整数 $n, k, x (1\leq n,x \leq 1000, 1\leq k \leq 100)$

#输出描述

对于每组数据输出一行表示答案。

#样例

样例输入 #1

3
3 2 1
10 3 4
5 3 2

样例输出 #1

2
32
8

#思路

签到题，模拟即可。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, k, x, ans = 0;
        cin >> n >> k >> x;
        int i = 0, j = 0;
        while(i < n) {
            i++;
            j++;
            ans += x;
            if(j == k) {
                j = 0;
                i++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

#B-交换

#题面

#题目描述

给一个长度为 $n$ 的 01 序列 $s_1, s_2, ...., s_n$，现在可以至多进行 1 次如下操作： 选择 $1 \leq x < n$，将 $s$ 序列变成 $\{s_{x+1},s_{x+2},....., s_n, s_1, s_2, ....s_x\}$

输出最长的全为 $1$ 的子区间长度。

#输入描述

一个 01 字符串，表示序列 $s$。($1\leq |s| \leq 100000$)

#输出描述

输出一个整数表示答案。

#样例

样例输入 #1

1001

样例输出 #1

2

样例输入 #2

11111

样例输出 #2

5

样例输入 #3

10111010

样例输出 #3

3

#思路

给定的字符串首尾相接就会成一个环，那么可以破环成列，在 s 的末尾在添加一个 s，以样例 10111010 为例，处理过后则变成了 1011101010111010，那么这样就可以找出最长的全为 $1$ 的子区间长度。

注意当给定的字符串全为 $1$ 时，有可能会出现 $f_i \geq n$ 的情况，按照题意， $f_i\leq n$ ，所以当 $s_i$ 为 '1' 时，递推式为 $f_i = \min(f_{i-1} + 1, n)$ 。

最终的答案就是 $\max(\{f_1, f_2, ..., f_n\})$

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<bits/stdc++.h>

using namespace std;

int main() {
    int ans = 0, cnt = 0;
    string s;
    cin >> s;
    int n = s.size()-1;
    s += s;
    int i = 0, f[200005];
    memset(f, 0x00, sizeof(f));
    for(int i = 1 ; i < s.size() ; i++) {
        if(s[i] == '1') {
            f[i] = min(f[i-1]+1, n);
        }
    }
    for(int i = 0 ; i <= 2*n ; i++) {
        ans = max(f[i], ans);
    }
    cout << ans << endl;
    return 0;
}

#C-最少移动

#题面

#题目描述

给一个长度为 $n$ 的正整数序列 $\{a_1,a_2,...,a_n\}$，每次操作可以选择两个相邻的位置，让一个元素 $-1$ 另一个元素 $+1$，输出最少几次操作，能让所有元素相等，如果不可能实现，请输出 -1。

#输入描述

第一行一个整数 $T(T \leq 20)$，表示 $T$ 组数据。

每组数据第一行一个整数 $n$，第二行 $n$ 个数字表示 $a$ 序列，$1 \leq a_i \leq 100000$

#输出描述

对于每组数据，输出一个整数表示答案。

#样例

样例输入 #1

3
3
1 3 2
3
2 2 3
5
1 2 3 1 3

样例输出 #1

1
-1
3

#思路

这道题可以用前缀和做。

$$\begin{aligned} a & = \{1, 2, 3, 1, 3\} \\ sum & = \{1, 3, 6, 7, 10\} \end{aligned}$$

$a_i$ 为序列元素， $sum_i$ 为前缀和元素。

不难发现，当 $a_i+1, a_{i+1}-1$ 时，$sum_i=sum_i+1$ ，而 $sum_i+1$ 不变。 同理，当 $a_i-1, a_{i+1}+1$ 时，$sum_i=sum_i-1$ ，而 $sum_i+1$ 仍不变。

当 $a$ 中所有元素相等时，$sum$ 一定是一个等差数列。

举个例子：

$$\begin{aligned} a & = \{2, 2, 2, 2, 2\} \\ sum & = \{2, 4, 6, 8, 10\} \end{aligned}$$

所以可以得到结论：当 $f_n \bmod n \ne 0$ 时， $sum$ 中的元素不可能成等差数列，因此 $a$ 中的元素不可能相等，无解。 反之则有解。

由上方发现的规律可知：在变换过程中，$sum_n$ 总是不变的，因此可以自后向前逆推：设公差为$g$，则 $f_i = f_{i+1}-g (0<i<n)$，所以将 $f_i$ 变成 $f_{i+1}-g$ 所需的步数为 $abs(i*g-f_i)$。

提示：此题必须开 long long！

#代码

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

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        long long n, a[100005], f[100005], ans = 0;
        f[0] = 0;
        cin >> n;
        for(long long i = 1 ; i <= n ; i++) {
            cin >> a[i];
            f[i] = f[i-1] + a[i];
        }
        if(f[n]%n != 0) {
            cout << -1 << endl;
        }
        else {
            long long g = f[n]/n;
            for (long long i = n; i > 0; i--) {
                ans += abs(i * g - f[i]);
            }
            cout << ans << endl;
        }
    }
    return 0;
}

#D-飞行棋

#题面

#题目描述

牛牛在玩飞行棋。

有无限个格子排成一行，从左到右，标号为 $0,1,....,n, ......, \infty$ 终点为 $0$ ，有一架飞机一开始在 $n$ 号位置。

排骨龙每回合可以先投掷一次 $d$ 面的骰子，1 到 $d$ 等概率出现。

投出点数 $x$ 后，飞机会移动 $x$ 步，每步移动一格，方向初始向左移动，若到达终点，会向右移动。 若投出的点数为 $d$ 点，可以继续投掷，直到投出的点数不是 $d$ 点。 求让这架飞机停在终点回合数的期望。

#输入描述

第一行一个数字 $T$ 表示 $T$ ($T \leq 100$) 组数据。

接下来每行两个正整数 $n,d (2\leq d,n \leq 100000)$

#输出描述

输出 T 行，每行保留两位小数输出答案。

#样例

样例输入 #1

6
1 6
2 6
3 6
4 6
5 6
6 6

样例输出 #1

5.00
5.00
5.00
5.00
5.00
5.17

#思路

设 $f_x$ 为从 $x$ 走到 $1$ 的 步数。

• 当 $x \geq d$ 时，$f_x = \sum_{i=1}^{d} \frac{dp_{x-i}}{d}$
• 当 $x < d$ 时， 期望为 $d-1$ 。

来源：2020 牛客 NOIP 赛前集训营-普及组（第五场）题解

#代码

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

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, d;
        cin >> n >> d;
        if(d == 1) {
            cout << "1.00" << endl;
        }
        else if(n < d) {
            cout << fixed << setprecision(2) << d-1.00 << endl;
        }
        else {
            double f[100005], sum[100005];
            memset(f, 0x00, sizeof(f));
            memset(sum, 0x00, sizeof(sum));
            f[0] = sum[0] = 1;
            for(int i = 1 ; i < d, i <= n ; i++) {
                f[i] = d - 1.00;
                sum[i] = sum[i-1] + f[i];
            }
            for(int i = d ; i <= n ; i++) {
                    f[i]   = (sum[i-1] + f[i] - f[i-d-1])/d;
                    sum[i] = sum[i-1] + f[i] - f[i-d-1];
            }
            cout << fixed << setprecision(2) << f[n] << endl;
        }
    }
    return 0;
}