前言

比赛链接:https://ac.nowcoder.com/acm/contest/7612

A-购物

题面

题目描述

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

输入描述

第一行一个整数 T100T\leq 100,表示 TT 组数据。

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

输出描述

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

样例

  • 样例1
[input]
3
3 2 1
10 3 4
5 3 2
[output]
2
32
8

思路

签到题,模拟即可。

代码

#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-交换

题面

题目描述

给一个长度为 nn 的 01 序列 s1,s2,....,sns_1, s_2, ...., s_n,现在可以至多进行 1 次如下操作:
选择 1x<n1 \leq x < n,将 ss 序列变成 {sx+1,sx+2,.....,sn,s1,s2,....sx}\{s_{x+1},s_{x+2},....., s_n, s_1, s_2, ....s_x\}

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

输入描述

一个 01 字符串,表示序列 ss。(1s1000001\leq |s| \leq 100000)

输出描述

输出一个整数表示答案。

样例

  • 样例1
[input]
1001
[output]
2
  • 样例2
[input]
11111
[output]
5
  • 样例3
[input]
10111010
[output]
3

思路

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

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

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

代码

#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-最少移动

题面

题目描述

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

输入描述

第一行一个整数 T(T20)T(T \leq 20),表示 TT 组数据。

每组数据第一行一个整数 nn,第二行 nn 个数字表示 aa 序列,1ai1000001 \leq a_i \leq 100000

输出描述

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

样例

  • 样例1
[input]
3
3
1 3 2
3
2 2 3
5
1 2 3 1 3
[output]
1
-1
3

思路

这道题可以用前缀和做。

a={1,2,3,1,3}sum={1,3,6,7,10}a = \{1, 2, 3, 1, 3\}\\ sum = \{1, 3, 6, 7, 10\}

aia_i 为序列元素, sumisum_i 为前缀和元素。

不难发现,当 ai+1,ai+11a_i+1, a_{i+1}-1 时,sumi=sumi+1sum_i=sum_i+1 ,而 sumi+1sum_i+1 不变。
同理,当 ai1,ai+1+1a_i-1, a_{i+1}+1 时,sumi=sumi1sum_i=sum_i-1 ,而 sumi+1sum_i+1 仍不变。

aa 中所有元素相等时,sumsum 一定是一个等差数列

举个例子:

a={2,2,2,2,2}sum={2,4,6,8,10}a = \{2,2,2,2,2\}\\ sum = \{2,4,6,8,10\}

所以可以得到结论:当 fnmodn0f_n \bmod n \ne 0 时, sumsum 中的元素不可能成等差数列,因此 aa 中的元素不可能相等,无解。 反之则有解。

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

提示:此题必须开 long long

代码

#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,......,0,1,....,n, ......, \infty 终点为 00 ,有一架飞机一开始在 nn 号位置。

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

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

输入描述

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

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

输出描述

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

样例

  • 样例1
[input]
6
1 6
2 6
3 6
4 6
5 6
6 6
[output]
5.00
5.00
5.00
5.00
5.00
5.17

思路

fxf_x 为从 xx 走到 11 的 步数。

  • xdx \geq d 时,fx=i=1ddpxidf_x = \sum_{i=1}^{d} \frac{dp_{x-i}}{d}
  • x<dx < d 时, 期望为 d1d-1

来源:2020牛客NOIP赛前集训营-普及组(第五场)题解

代码

#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;
}