算法练习专栏——牛客练习——牛客round39

A:小红不想做炸鸡块粉丝粉丝题

链接

题目描述

小红作为炸鸡块哥哥的粉丝智乃的粉丝，做了一场炸鸡块哥哥的粉丝智乃的比赛后得出一个结论，那就是千万不要根据第一题的难度判断一场比赛的难度。
现在给定一场比赛6道题的难度，请你判断这场比赛是不是智乃style。
所谓智乃style，指第一题难度小于6道题难度之和的1/30。

输入描述:

1
六个正整数，用空格隔开。分别代表每道题的难度。

输出描述:

1
如果是智乃style，则输出"Yes"。否则输出"No"。

示例1

输入

复制

1
200 1600 2200 2500 2800 3200

输出

复制

1
Yes

说明

1

示例2

输入

复制

1
300 800 1000 1200 1800 2000

输出

复制

1
No

B:小红不想做鸽巢原理

链接

题目描述

小红有n种不同颜色的小球，第iii种颜色的小球有ai个，放在同一个盒子中。

小红每次任意取出k个小球并丢弃，直到盒子中剩余的球数小于k个为止。

小红希望最终盒子里的小球颜色种类尽可能少，你能帮小红求出颜色的种类数量吗？

输入描述:

1
2
3
4
第一行输入两个正整数n,k，代表初始的颜色种类和小红每次丢弃的小球数量。
第二行输入n个正整数ai，代表每种颜色的小球数量。
1≤n≤105
1≤k,ai≤109

输出描述

1
一个整数，代表最终剩余的颜色种类。

示例1

输入

复制

1
2
4 2
1 2 2 4

输出

复制

1
1

说明

1
小红可以操作4次，将第2、3、4三种小球全部丢弃。

代码

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
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;
long long a[N], s[N];
int n;


int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    long long res = 0;
    int n, k, kk = 0, nn;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        res += a[i];
    }
    sort(a + 1, a + n + 1);
    if (res % k == 0) cout << 0;
    else {
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
        long long aa = 0, bb = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = (a[i] + a[i - 1]) % k;
            if (res - s[i] + a[i] == 0) {
                cout << 0;
                break;
            }
            else if (res - s[i] + a[i] < k) {
                cout << n - i + 1;
                break;
            }
        }
    }
//     for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
//     for (int i = 1; i <= n; i++) {
//         long long ans = res - s[i] - (k - s[i - 1] % k);
//         cout << ans << '\n';
//         if (ans < k) {
//             cout << n - i + 1;
//             break;
//         } else if (ans == k) {
//             cout << 0;
//             break;
//         }
//     }
    
    
    
    return 0;
}

C:小红不想做完全背包（easy）

链接

题目描述

本题和hard版本的唯一区别是：p保证等于3。

完全背包是一个经典问题，但小红完全不会完全背包，因此她不想做完全背包。

现在小红拿到了一个长的很像完全背包的题，她希望你帮她解决一下。

给定一个背包，有n种物品，每种物品的价值为ai，有无穷多个。小红有一个无穷大的背包，

​ 她希望往里面放若干个物品，使得最终所有物品的价值之和为p的倍数。

​ 小红想知道最终至少要放多少物品？

​ （注意：不能不放物品）

输入描述:

1
2
3
4
5
第一行输入两个正整数n,p，用空格隔开。
第二行输入n个正整数ai。
1≤n≤2000
p=3p=3p=3
1≤ai≤109

输出描述:

1
一个整数，代表小红最终要放的物品数量的最小值。

示例1

输入

复制

1
2
4 3
1 2 3 4

输出

复制

1
1

说明

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
#include <iostream>
#include <algorithm>

using namespace std;
const int N=  2010;
int n;
int a[N];
int b[3];

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n, p;
    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        b[x % p]++;
    }
    if (b[0] > 0) cout << 1;
    else if (b[1] > 0 && b[2] == 0) cout << 2;
    else if (b[1] == 0 && b[2] > 0) cout << 3;
    else {
        cout << 2;
    }
    return 0;
}

D:小红不想做完全背包 （hard）

链接

题目描述

本题和easy版本的唯一区别是：p没有必须等于3的限制。

完全背包是一个经典问题，但小红完全不会完全背包，因此她不想做完全背包。

现在小红拿到了一个长的很像完全背包的题，她希望你帮她解决一下。

​ 给定一个背包，有n种物品，每种物品的价值为ai，有无穷多个。小红有一个无穷大的背包，她希望往里面放若干个物品，使得最终所有物品的价值之和为p的倍数。小红想知道最终至少要放多少物品？

​ （注意：不能不放物品）

输入描述:

1
2
3
4
第一行输入两个正整数n,p，用空格隔开。
第二行输入n个正整数ai。
1≤n,p≤2000
1≤ai≤109

输出描述:

1
一个整数，代表小红最终要放的物品数量的最小值。

示例1

输入

复制

1
2
4 3
1 2 3 4

输出

复制

1
1

说明

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
/*   /\_/\
*   (= ._.)
*   / >  \>
*/
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
 
int a[2010];
 
int dp[2010]; 
// dp[i]表示，选择的数字对p取余等于i的最少选择数字个数
// answer = dp[0];
 
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, p;
    cin >> n >> p;
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        a[i] = x % p;
        dp[a[i]] = 1; //初始化，对p取余的最小选择个数
        for (int j = 0; j < p; j ++)
        {
            //从j转移到哪?
            // (a[i] + j) % p;
            int nex = (a[i] + j) % p;
            dp[nex] = min(dp[nex], dp[j] + 1);
        }
    }
 
    cout << dp[0] << "\n";
 
    return 0;
}

E：小红不想做莫比乌斯反演杜教筛求因子和的前缀和

链接

题目描述

小红来到了一家蛋糕店，蛋糕店中售卖了若干种不同的长方体蛋糕，具体来讲，蛋糕店中售卖若干种形状为横向长度不大于n，纵向长度不大于m，高度不大于p个单位的蛋糕。每个蛋糕的表面要裹上奶油，也就是说，除了底面以外，其余5个面都需要裹奶油。我们不妨定义：奶油消耗量为暴露在空气中的5个面的面积之和。

我们定义两种蛋糕是不同的，当且仅当两个蛋糕的横向或者纵向长度或高度不同。即分别定义蛋糕横向的长度为i，纵向的长度为j，高度为k，则可以用三元组(i,j,k)表示蛋糕种类的唯一性。

现在小红希望你求出，共有多少种不同的奶油消耗量为xxx的蛋糕？

输入描述:

1
2
3
第一行输入四个正整数n,m,p,x，用空格隔开。
1≤n,m,p≤3000
1≤x≤107

输出描述:

1
消耗量为x的蛋糕的种类数。

示例1

输入

复制

1
2 2 2 8

输出

复制

1
2

说明

1
如下图，共有以下两种蛋糕的奶油消耗量为8。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N = 3010;
int n;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    long long n, m, p, x, kk = 0;
    cin >> n >> m >> p >> x;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            double k = (1.0 * (x - i * j) / (2 * (i + j)));
            if (k > 0 && k <= p && (k - int(k) == 0)) {
                kk++;
            }
        }
    }
    
    cout << kk;
    return 0;
}

F：小红不想写模拟题

链接

题目描述

给你两个长度大小为n的01串 A,B（指字符串的字符都为’0’和’1’）。
现在小红有若干次操作，每次选择一个01串的一个区间，将区间内所有字符都变成全1。
每次操作后，小红希望你求出两个字符串有多少个位置的对应字符都是1。用数学语言来说，即求∑i=1n(ai & bi)\sum_{i=1}^n(a_i\ & \ b_i)∑i=1n​(ai​ & bi​)。你能帮帮她吗？

输入描述:

1
2
3
4
5
6
7
8
第一行输入一个正整数 n，代表字符串的长度。 
第二行和第三行分别输入一个长度为 n 的01串，分别代表A串和B串。
第四行输入一个正整数 q，代表操作次数。

接下来的 q 行，每行输入一个字符 ccc 和三个整数 l,r，代表将对应字符串的第 l 个字符到第 r 个字符修改为 1。
1≤n,q≤105
1≤l≤r≤n
c∈′A′,′B′

输出描述:

1
输出 q 行，每行输出操作后，两个字符串有多少个位置的对应字符都是1。

示例1

输入

复制

1
2
3
4
5
6
4
0101
0110
2
A 2 3
B 1 4

输出

复制

1
2
2
3

说明

1
2
第一次操作后，A字符串变成"0111"，有2个位置满足对应字符都是1。
第二次操作后，B字符串变成"1111"，有3个位置满足对应字符都是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
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
bitset <N> a,b;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n,t,l,r;
	char c;
	cin>>n;
	//string s1,s2;
	cin>>a>>b;
	cin>>t;
	while(t--)
	{
		cin>>c>>l>>r;
        l--;
        r--;
        l=n-l;
        r=n-r;
		if(c=='A')
			for(int i=r-1;i<l;i++)
				a[i]=1;
		if(c=='B')
			for(int i=r-1;i<l;i++)
				b[i]=1;
		auto f=a&b;
		cout<<f.count()<<endl;
	}
	return 0;
}