算法练习专栏——牛客练习——牛客练习赛125

A.美味饼干

链接

题目描述

​ 小蓝获得了 5 块饼干，其中第 i 块饼干的大小是 ki。

小灰灰想知道至少需要再给小蓝几块饼干才能使小蓝手中第 5 小的饼干大小恰好是 k1（即对小蓝已有饼干按从小到大排序后的第 5 块饼干大小为 k1）。

输入描述:

1
2
3
4
5
6
7
输入第一行一个整数 T 代表案例组数。

每组案例仅由一行输入组成：

    一行 5 个空格分隔的整数分别代表：k1,k2,k3,k4,k5。
保证：
1≤T,ki≤1000

输出描述:

1
输出共 T 行，第 i 行输出一个整数代表第 i 组案例的答案。

示例1

输入

复制

1
2
3
4
5
4
1 2 3 4 5
5 4 3 2 1
1 1 1 1 2
2 3 1 8 1

输出

复制

1
2
3
4
4
0
1
2

说明

1
2
3
4
5
6
7
第一组案例中，只需要再给小蓝 4 块大小为 1 的饼干，其手中第 5 小的饼干大小就是 1 了。

第二组案例中，不需要给小蓝任何额外的饼干，其手中第 5 小的饼干大小就是 5 了。

第三组案例中，只需要再给小蓝 1 块大小为 1 的饼干，其手中第 5 小的饼干大小就是 1 了。

第四组案例中，一种可能的方式是只需要再给小蓝 1 块大小为 1 的饼干和 1 块大小为 2 的饼干，其手中第 5 小的饼干大小就是 2 了。

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 1e5 + 10;

void solve() {
    int a[10];
    fore (i, 1, 5) cin >> a[i];
    int k = a[1];
    sort(a + 1, a + 5 + 1);
    
    for(int i = 5; i >= 1; i--) {
        if (a[i] == k) {
            cout << 5 - i << ed;
            break;
        }
    }
}
int main()## 思路

> ​	

## 
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

B.选择游戏

链接

题目描述

黑板上有 n 个数字。

小灰灰和小蓝依次操作（小灰灰先操作），每次操作他们会选择一个质数，将其擦去，然后将其减一后的值再写在黑板上。当轮到某人操作，而其无法操作时则宣布其输掉比赛，另一人获胜。

为了获胜，小灰灰决定先擦去黑板上的一些数字，请你帮小灰灰计算若要使得其获胜，其最少需要擦去多少个数字。

输入描述:

1
2
3
4
5
6
7
8
9
10
11
12
第一行一个整数 T 代表案例总数。

接下来每两行代表一个测试案例：

    第一行一个整数 n 代表黑板上的数字总数。
    第二行 n 个空格分隔的整数代表黑板上初始的数字。

保证：

所有输入的数字都是正整数且不超过 105。

单个测试点所有案例中 n 的和不超过 2×105。

输出描述:

1
共 T 行，第 i 行一个整数代表第 i 个案例的答案，特别的，若小灰灰无论如何都无法获胜请输出 −1。

示例1

输入

复制

1
2
3
4
5
6
7
3
5
7 9 8 7 2
1
8
2
5 11

输出

复制

1
2
3
0
-1
1

思路

​ 这道题目最主要的是需要处理1,3这两个特殊情况,3变化的话会变成2还是质数,而1的话需要注意其不是质数.

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;
int ans;
// 2 7 7 8 9
// 2 7 7 8 9

bool check(int x) {
    if (x < 2 || x == 3) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
void solve() {
    int n;
    cin >> n;
    ans = 0;
    fore (i, 1, n) {
        int x;
        cin >> x;
        if (check(x)) ans++;
    }
   
    
    if (!ans) cout << "-1" << ed;
    else if (ans % 2 == 0) cout << "1" << ed;
    else cout << "0" << ed;
}

int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

C.找到数字

链接

题目描述

记$f(x) = x\mod 10^{t-1}+\left \lfloor\frac{x}{10} \right \rfloor$ 其中 t 为 x 在十进制表示下的位数。

现在给定 y，小灰灰请你输出有多少种不同的正整数 x 可以使得 f(x)=y。

输入描述:

1
2
3
4
5
6
7
8
9
10
11
第一行一个整数 T 代表案例数。

每组案例仅由一行组成：

    一个整数 y。

保证：

1≤T≤105

1≤y<1017

输出描述:

1
输出共 T 行，第 i 行一个整数代表第 i 组案例的答案。

​ 示例1

输入

复制

1
2
3
2
5
21

输出

复制

1
2
5
2

说明

1
2
3
第一组案例中，x 共有 5 种选取方式：41，32，50，23，14。

第二组案例中，x 共有 2 种选取方式：201，110。

思路

​ 首先,第一步,我们需要理解题目所给公式是什么意思,这里还是蛮好看得出来:如果一个数的位数为n,那么就是需要求这个f(x) = 这个数的前 n - 1 位数的和 + 后 n - 1 位数的和,比如f(2211) = 221 + 211 = 432.

​ 紧接着就是分析如何快速找出这样的数了.我们可以这样思考:首先我们枚举第一个数和最后一位数字,而中间的 n - 2位数.而现在我们关键就是需要思考如何将中间的数求出来了.

​ 我们可以设第一位为A,中间位为B,最后一位为C,那么$y = AB + BC = A * pow(10, n - 2) + B + B * pow(10, 1) + C$.

​ 即:$11 * B = y - C - A * pow(10, n - 2)$,因此可知:

  • y - C - A * pow(10, n - 2) 为11的倍数
  • pow(10, n - 2) > B

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef unsigned long long LL;
typedef double db;

const LL INF = 1e17;
LL ans = 0;

void solve() {
    LL y;
    ans = 0;
    cin >> y;
    fore (A, 1, 9) {
        fore (C, 0, 9) {
            for (LL p = 1; p < INF; p *= 10) {
                LL B = y - p * A - C;
                if (B >= 0 && B % 11 == 0 && p > B / 11){
                    ++ans;
                }
            }
        }
    }
    
    cout << ans << ed;
 }
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

D.风车Ⅱ

链接

题目描述

小灰灰和小蓝住在一个 n 行 m 列的网格图中，每个网格上都有一个出售小风车的商店，第 i 行第 j 列的商店有 ci,j 个颜色为 ai,j 的风车。

小灰灰住在第 1 行第 1 列的网格，而小蓝住在第 n 行第 m 列的网格。

有一天小灰灰想去小蓝家，他并不想绕远路（所以每次只会向下或者向右走）。

小灰灰出门前会选择一个幸运颜色，当他沿途经过的格子上商店所出售的风车恰好为他选择的颜色时他会买走这个商店中所有的风车。

小蓝喜欢风车，所以小灰灰请你帮他计算，他走到小蓝家时手上最多有多少个风车。

输入描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
第一行一个整数 T 代表案例数。

每组案例由若干行组成：

    第一行两个空格分隔的整数分别代表 n 和 m。
    接下来 n 行，每行 m 个整数，第 i 行第 j 列的整数即为 ai,j。
    接下来 n 行，每行 m 个整数，第 i 行第 j 列的整数即为 ci,j。

保证：

0<n,m,T,ai,j≤105

0<n×m≤2×105

0<ci,j≤109

单个测试点中所有案例 n×m 的和不超过 3×105。

来源：牛客网输出描述:

1
输出共 T 行，第 i 行代表第 i 组案例的答案。

示例1

输入

复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3
2 3
3 4 2
4 3 2
1 1 1
1 1 1
3 5
9 8 6 4 2
6 4 2 1 4
4 6 4 6 2
1 2 3 4 5
5 4 3 2 1
2 3 6 1 8
1 1
100000
1000000000

输出

复制

1
2
3
2
13
1000000000

思路

​ 思路一:这道题目如果不是数据大小原因,其实是很简单就可以想出下面的解法,给出一个dp[n] [m] [c],dp[i] [j] [k] 表示对于前i行j列所有颜色为k的小风车的数量,最后我们在dp[n] [m]的位置取max即可,但是这道题目直接这样写会暴内存,n * m * c = 3e10 >> 1e8,因此这样写不可行.

​ 思路二:对于上面的思路优化处理(模拟离散化的一种不太一样的方式),具体解释请看代码.

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;
// 表示每种颜色的下标以及其数量
map<PII,LL> mp[N];

// 求出x, y位置前的对于x, y位置颜色的小风车的最大数量.
LL check(int x, int y, int k) {
    LL sum = 0;
    for (auto [cur, num] : mp[k]) {
        if (cur.fi <= x &&  cur.se <= y) {
            sum = max(sum, num);
        }
    }
    
    return sum;
}

void solve() {
    LL n, m, Max = 0;
    cin >> n >> m;
    
    vector<vector<LL>> a(n + 10,vector<LL> (m + 10));
    vector<vector<LL>> c(n + 10,vector<LL> (m + 10));
    // 表示前i行j列颜色为a[i][j]的最大小风车数量
    vector<vector<LL>> dp(n + 10,vector<LL> (m + 10));
    fore (i, 1, n) {
        fore (j, 1, m) cin >> a[i][j];
    }
    
    fore (i, 1, n) {
        fore (j, 1, m) {
            cin >> c[i][j];
            dp[i][j] = check(i, j, a[i][j]) + c[i][j];
            
            // 这里是将当前下标记录下来,表示颜色a[i][j]在下标i,j位置前的最大数量和
            mp[a[i][j]][{i, j}] = dp[i][j];
            Max = max(Max, dp[i][j]);
        }
    }
    
    cout << Max << ed;
    
    // 清空
    fore (i, 1, n) {
        fore (j, 1, m) {
            mp[a[i][j]].clear();
        }
    }
}

int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}