算法练习专栏——牛客练习——牛客小白月赛94

A:小苯的九宫格

原题

题目描述

在一些安全性要求较高的APP中，通常我们输入密码时，系统弹出的输入框都是乱序的。这样一来就能防止想通过观察手指点击位置来推测密码的坏人。

​ 现在小苯有一个可能乱序的九宫格按键，但他没注意到九宫格是乱序，因此他还是按照正常九宫格顺序点击的按键。

​ （正常九宫格：也就是按照 1 到 9 分为三行三列，从上到下，从左到右都是递增的，下方备注有图）

请你告诉他，在他点击完按键后，屏幕上显示的数字都应该是什么？

输入描述:

1
2
3
输入包含四行。
第一到三行，每行三个正整数以空格分割，表示题目所述的“九宫格”按键。（保证输入是一个合法的九宫格，即 1 到 9 每个数字都恰好出现一次。）
第四行一个数字串 s (1≤∣s∣≤100,1≤si≤9)，表示小苯会按照正常九宫格顺序输入的数字串。（其中 ∣s∣ 表示 s 的长度。）

输出描述:

1
2
输出一行一个数字串，表示小苯输入后，屏幕上的结果字符串。
（输出仅包含数字，数字间无需用空格间隔）

示例1

输入

复制

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

输出

复制

1
294357816

说明

1
如下为样例的九宫格按键，在正常九宫格按键下按照“123456987”的顺序键入，显然结果应该是“294357816”。

备注:

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
#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;
int a[3][3];

void solve() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) cin >> a[i][j];
    }
    
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        int k = s[i] - '0';
        int x = k / 3, y = k % 3 - 1;
        cout << a[x][y]; 
    }
}
int main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

C:小苯的好数组

链接

题目描述

大白熊给了小苯一个长度为 n 的数组 a，这次他希望小苯从数组中选择一个子序列（下方备注有定义解释），满足这个子序列构成的数组是一个“好数组”。

​ 大白熊定义好数组是：如果一个数组按升序排序后和原来不完全相同，则其是一个好数组。例如 [3,2,2]升序排序后是 [2,2,3]，和原来不完全相同，因此是一个好数组，而 [1,2,2] 不是一个好数组。

​

​ 小苯想知道，如果想要使得选择的子序列构成一个“好数组”，最长可以选多长的子序列？

输入描述:

1
2
3
输入包含两行。
第一行一个正整数 n (1≤n≤2×105)，表示数组 a 的长度。
第二行 n 的正整数 ai(1≤ai≤109)，表示数组 a 的元素。

输出描述:

1
输出包含一行一个整数，表示可以构成“好数组”的最长子序列的长度。

示例1

输入

复制

1
2
1
1

输出

复制

1
0

说明

1
只能选择 1，但 [1] 这个数组满足单调不降，因此无法选择数字，答案为 0。

备注:

1
2
3
子序列：一个数组删除一些数字后（也可以不删），剩余的数字按其原来的顺序构成的序列。
例如：[2,3] 是 [1,2,4,3] 的一个子序列，同时 [1,2,4,3] 也是自己的子序列，但 [3,2]并不是 [1,2,4,3]的子序列。
空数组是任何数组的子序列。

思路

​

代码

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 = 2e5 + 10;
int a[N];

void solve() {
    int n;
    bool flag = false;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < a[i - 1]) {
            cout << n;
            flag = true;
            return;
        }
    }
    
    if (!flag) cout << "0";
}
int main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    
    while(_--) {
        solve();
    }
    
//     1 2 3 6 6 6 6 5 7 6
    re;
}

C:小苯的数字合并

原题

题目描述

​ 大白熊给了小苯一个长度为 n 的数组 a，小苯想要最大化 a 的极差。

具体的，小苯可以做如下操作任意次（前提是数组至少有两个数字）：

​

​ ∙\bullet∙ 选择一个正整数 i (1≤i<n)i \ (1 \leq i <n)i (1≤i<n)，接着将 ai 与 ai+1 合并为一个数字，结果为二者的和。

​ （即：将 ai 变为 ai+ai+1，然后删去 ai+1，当然操作完后 a 的长度也会减一。）

小苯想知道他最大能将数组极差变为多少呢，请你帮帮他吧。

输入描述:

1
2
3
输入包含两行。
第一行一个正整数 n (1≤n≤2×105)，表示数组 a 的长度。
第二行 nnn 个正整数 ai (1≤ai≤109)，表示初始时数组 a 的元素。

输出描述:

1
输出包含一行一个整数，表示小苯操作完后，数组 a 的最大极差。

示例1

输入

复制

1
2
4
3 2 2 3

输出

复制

1
4

说明

1
2
3
4
一种可能的操作方式是：

选择将 a2,a3 合并，数组此时变为[3,4,3]。
然后再选择 a2,a3 合并，数组此时变为 [3,7]，极差为 4。可以证明不存在比 4 更大的极差。

备注:

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
#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;
LL a[N], s[N];
LL maxn = 0;

void solve() {
    int n;
    cin >> n;
    fore (i, 1, n) cin >> a[i];
    fore (i, 1, n) s[i] = s[i - 1] + a[i];
    fore (i, 1, n) {
        LL max1 = s[i - 1], max2 = a[i],max3 = s[n] - s[i];
        if (max1 == 0) maxn = max(maxn, abs(max2 - max3));
        else if (max3 == 0) maxn = max(maxn, abs(max1 - max2));
        else {
            maxn = max(maxn, abs(max({max1, max2, max3}) - min({max1, max2, max3})));
        }
    }
    
    cout << maxn;
} 
int main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

D.小苯的排列构造

链接

题目描述

格格有一个长度为 n 的排列 p，但她不记得 p 具体的样子，她只记得数组 a。
其中：ai=gcd(p1,p2,…,pi)，也就是说，ai​ 表示排列 p 中前 i 个数字的最大公约数。

​ 现在，她希望小苯将排列 p 复原出来，请你帮帮他吧。

​ （但有可能无解，这意味着格格给出的 a 数组可能是不正确的，此时输出 −1-1−1 即可。）

输入描述:

1
2
3
输入包含两行。
第一行一个正整数 n (1≤n≤2×105)，表示数组 a 的长度。
第二行 n 个正整数 ai (1≤ai≤n)，表示数组 a 的元素。

输出描述:

1
2
3
4
输出包含一行 n 个正整数，表示符合条件的排列 p。

如果有多个解，输出任意方案即可。
如果无解，请输出一个数字：−1。

示例1

输入

复制

1
2
4
4 2 1 1

输出

复制

1
4 2 1 3

说明

1
2
3
4
5
首先输出是一个排列，且满足格格的要求：
a1=gcd(p1)=4
a2=gcd(p1,p2)=2
a3=gcd(p1,p2,p3)=1
a4=gcd(p1,p2,p3,p4)=1

备注:

1
排列：长度为 n 的排列是一个数组，满足其中 1到 n 的每个正整数恰好出现一次。

思路

​ 这道题目的基本思路其实还是一种模拟类型的题目,基本思路说实话都是猜出来的,按照这套思路走下去,只要没有走入死胡同就一定有结果输出,反之则是死胡同,直接输出**-1**即可.

​ 这道题目本人的主要思路是:首先判断一下前一个数a[i - 1]是否可以被a[i]除尽,如果不可以就可以直接输出-1了.紧接着我们只需要接着**a[i]上一次判断过的list[a[i]]**的位置继续往后即可,这段话可能有点难理解,可以看下面例子知之.

​ 例子: 4 2 2 2 2,我们在list[2]的时候,第一次我们会到2,然后遍历后面的2的时候就可以直接到4,6,8,一旦不符合条件了,就直接输出-1即可,比如这里的6就不符合条件了,这里的list的作用就是存放之前list[a[i]] 位置而不是又从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
76
77
78
79
80
81
82
83
84
85
86
87
88
#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 2<< 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 a[N], b[N], list[N];
bool st[N];

int gcd(int x, int y) {
    return (y == 0 ? x : gcd(y, x % y));
}

void solve() {
    int n;
    cin >> n;
    fore (i, 1, n) cin >> a[i];
    
    st[0] = true;
    fore (i, 1, n) {
        if (a[i - 1] % a[i]) {
            cout << "-1" << ed;
            return;
        }
        while (st[list[a[i]]]) {
            list[a[i]] += a[i];
        }
        if (list[a[i]] > n) {
            cout << list[a[i]] << ed;
            return;
        }
        st[list[a[i]]] = true;
        b[i] = list[a[i]];
    }
    fore (i, 1, n) cout << b[i] << " ";
}
int main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

E/F:小苯的01背包（hard）

链接

题目描述

注：此版本为本题的hard（困难版），与easy（简单版）唯一的不同之处只有数据范围。

​ 小苯有一个容量为 k 的背包，现在有 n 个物品，每个物品有一个体积 v 和价值 w，他想知道在体积不超过 k 的前提下，他最多能装价值为多少的物品。

​ 本问题中，物品的总体积定义为所装物品的体积的 &（按位与），总价值也定义为所装物品的价值的 &（按位与）。

​ （如果不选物品，则价值为 0，所占体积也为 0。）

输入描述:

1
2
3
输入包含 n+1 行。
第一行两个正整数 n,k (1≤n≤2×105,0≤k≤109)，分别表示物品个数和背包容量。
加下来 nnn 行，每行两个正整数 vi,wi (0≤vi,wi≤109)，表示每个物品的体积和价值。

输出描述:

1
输出包含一行一个整数，表示能装的最大价值。

示例1

输入

复制

1
2
3
4
3 1
7 3
10 7
9 6

输出

复制

1
2

说明

1
2
3
选择第一个和第三个物品。
体积为：7 & 9=1。
价值为：3 & 6=2。可以证明不存在比 2 更大的价值。

示例2

输入

复制

1
2
3
4
3 2
7 3
10 7
9 6

输出

复制

1
3

说明

1
选第一个和第二个物品。

思路

与运算, 选的越多, 价值越低, 但总体积也越小越可行
现在需要找到最大价值, 设其为ans
∴ value[1] & value[2] & … = ans
∴ ans & value[i] = ans (ans在任意一位的1, 每个value在对应位上都有)

假设ans = 10110
那么只要第1位、第3位、第4位都为1, 那么这个物品对于这个答案来说就是可选的
而体积是选的越多越可行, 所以可以枚举答案
然后按**”ans & value[i] = ans”这个条件,选出所有物品
计算出这些物品的总体积, 如果满足容量k**限制, 则找到一个可行解

代码

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>k
#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 refore(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 << sektprecision(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;
LL v[N], w[N];

void solve() {
    int n, m, ans = 0;
    cin >> n >> m;
    
    fore (i, 1, n) cin >> v[i] >> w[i];
    
    refore (bit, 30, 0) {
        LL guess = ans | (1 << bit);
        LL weight = (1 << 30) - 1;
        fore (i, 1, n) {
            if ((guess & w[i]) == guess) {
                weight &= v[i];
            }
        }
        if (weight <= m) ans = guess;
    }
    cout << ans;
}
int main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}