程序员进阶之算法练习（七十一）
题目1
题目链接
题目大意：
给出n个整数，每次可以选择其中两个整数a[i]和a[j]，令a[i]=x和a[j]=y，但是需要满足a[i] | a[j] = x | y；（|是或操作）
现在可以进行任意次操作，问n个整数的最小和是多少。
输入：
第一行样例数，𝑡(1≤𝑡≤1000)
每个样例两行，第一行是𝑛 (2≤𝑛≤100)
第二行是n个整数𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖<2^30)
输出：
每个样例一行，输出最小和。
Examples
input
4
3
1 3 2
5
1 2 4 8 16
2
6 6
3
3 5 6
output
3
31
6
7
题目解析：
1和3的或操作会得到3，那么相当于1被清0；
也就是说，两个整数中间相同的二进制位数可以消除其中一个；
那么题目转化为，对于(1<<k)，k从0到30，只要出现过一次就可消除其他整数；
于是题目变成对于(1<<k)，k从0到30，所有出现过的数字的和。
class Solution {
static const int N = 200010;
string str;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
bool vis[31] = {0};
int ans = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
for (int j = 0; j < 30; ++j) {
if (x & (1 << j) && !vis[j]) {
ans += (1 << j);
vis[j] = 1;
}
}
}
cout << ans << endl;
}
}
}
ac;
题目2
题目链接
题目大意：
给出n个整数的数组，每次可以选择数组其中一个元素修改为任意整数；
现在不希望数组中出现任何元素满足，𝑎[𝑖]>𝑎[𝑖−1] and 𝑎[𝑖]>𝑎[𝑖+1]；
问最少需要操作修改多少次元素，才能满足要求。
输入：
第一行样例数，(1≤𝑡≤10000)
每个样例两行，第一行是𝑛 (2≤𝑛≤2⋅1e5)
第二行是n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
输出：
每个样例两行，第一行输出最小修改次数；
第二行输出修改之后的n个整数；
Examples
input
5
3
2 1 2
4
1 2 3 1
5
1 2 1 2 1
9
1 2 1 3 2 3 1 2 1
9
2 1 3 1 3 1 3 1 3
output
0
2 1 2
1
1 3 3 1
1
1 2 2 2 1
2
1 2 3 3 2 3 3 2 1
2
2 1 3 3 3 1 1 1 3
题目解析：
先找到元素a[i]满足𝑎[𝑖]>𝑎[𝑖−1] and 𝑎[𝑖]>𝑎[𝑖+1]，要使得满足题目要求，只有三种可能：
1、修改a[i-1]；
2、修改a[i]；
3、修改a[i+1]；
为了方便决策，我们假设从左到右遍历数组，现在遇到了a[i]不符合要求，那么可以选择将a[i-1]或者a[i+1]变大，或者将a[i]变小；
容易知道这三者对于已经遍历到的元素a[1]到a[i+1]是没有区别的（因为都满足要求），但是考虑到后续还有a[i+2]的元素，那么将a[i+1]变大的选择会更优；
并且我们可以使得a[i+1]=max(a[i], a[i+2])，这样就可以最大程度利用这一次修改机会。
然后不断循环这个操作直到数组末尾。
class Solution {
static const int N = 200010;
string str;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0;
for (int i = 1; i + 1 < n; ++i) {
if ((a[i] > a[i - 1]) && (a[i] > a[i + 1])) {
a[i + 1] = max(a[i], a[i + 2]);
++ans;
}
}
cout << ans << endl;
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
}
cout << endl;
}
}
}
ac;
题目3
题目链接
题目大意：
给出长度为n的由0和1组成的字符串a，现在可以对字符串a执行下面的操作：
1、将a2=min(a1, a2)，然后移除a1；
2、将a2=max(a1, a2)，然后移除a1；
现在有长度为m的字符串b，想问字符串a是否能通过任意次操作1或者操作2，得到字符串b；
输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤2000)
每个样例第一行 整数 𝑛, 𝑚 (1≤𝑛,𝑚≤50, 𝑚≤𝑛)
第二行长度为n的字符串a
第三行长度为m的字符串b
输出：
每个样例一行，如果可以则输出YES；否则输出NO；
Examples
input
10
6 2
001001
11
6 2
110111
01
6 2
000001
11
6 2
111111
01
8 5
10000101
11010
7 4
1010001
1001
8 6
01010010
010010
8 4
01010101
1001
8 4
10101010
0110
7 5
1011100
11100
output
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES
题目解析：
不管是操作1、操作2，都无法影响后续字符串；
那么给出的字符串b，其实只有第一个字符的组成，a是有办法去选择；
也就是说对于字符串a来说，后面的m-1个字符，必须和b一样；然后前面的字符必须出现过1次b的第一个字符；
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
string a, b;
cin >> a >> b;
if (n == 1) {
cout << (a[0] == b[0] ? "YES" : "NO") << endl;
continue;;
}
if (m == 1) {
int find = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == b[0]) find = 1;
}
if (find) cout << "YES" << endl;
else cout << "NO" << endl;
continue;
}
int ok = 1;
for (int i = 1; i < m; ++i) {
if (b[i] != a[n - m + i]) ok = 0;
}
int find = 0;
for (int i = 0; i <= n - m; ++i) {
if (a[i] == b[0]) find = 1;
}
if (find && ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
}
ac;
题目4
题目链接
题目大意：
有2𝑛个人参加比赛，编号是1到2n；
比赛采用的是淘汰赛的机制，1和2比，3和4比，然后接着是胜者按照编号大小继续比赛；
已知编号x和y的人参加比赛，会有下面的结果：
1、x+y是奇数，则胜者是编号较小者；
2、x+y是偶数，则胜者是编号较大者；
输入：
第一行，整数𝑡 表示t个样例 (1≤𝑡≤1000)
每个样例一行，整数𝑛 (1≤𝑛≤30)
输出：
每个样例输出一行，输出最后的胜者编号。
Examples
input
2
3
1
output
7
1
题目解析：
仔细看图中的条件，发现这里面条件的x+y是奇数，只会出现在第一轮比赛；
从第二轮比赛开始，参赛全部是奇数，则一定是较大者获胜；
思考🤔：
假设参加比赛初始顺序是乱序的呢？那就手动算一遍，因为轮次是log级别递进，总体的复杂度可以控制在NlogN；
class Solution {
static const int N = 200010;
string str;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << (1 << n) - 1 << endl;
}
}
}
ac;
题目5
题目链接
题目大意：
给出n个整数的数组a，现在可以选择数组中三个元素a[x],a[y],a[z]（其中x<y<z），令a[x]=a[y]-a[z]；
现在可以执行不超过n次操作，要求数组变成非递减；
输入：
第一行样例数，(1≤𝑡≤10000)
每个样例两行，第一行是 𝑛 (3≤𝑛≤2⋅1e5)
第二行是n个整数𝑎1,𝑎2,…,𝑎𝑛 (−1e9≤𝑎𝑖≤1e9)
输出：
每个样例第一行输出操作次数k，如果无解则输出-1；
有解的情况，接下来k行，每一行包括整数x,y,z，表示每次操作的数组元素序号；（没有要求最少操作次数）
Examples
input
3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1
output
2
1 2 3
3 4 5
-1
0
题目解析：
题目有一个很重要的条件，没有要求最少操作次数。
那么对于数组中只有最后两个整数是有意义的，如果第n个元素>=0，那么必然有解：可以把前面的元素都替换成a[n-1]-a[n]；
先判断下数组是不是本身符合要求；
其他的情况根据a[n-1]和a[n] 的大小就可以判断。
思考🤔：
如果要求最小次数呢？
class Solution {
static const int N = 200010;
string str;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (a[n - 1] < a[n - 2]) {
cout << -1 << endl;
}
else {
int rightIndex = n - 3;
while (rightIndex >= 0) {
if (a[rightIndex] > a[rightIndex + 1]) {
break;
}
--rightIndex;
}
if (rightIndex < 0) {
cout << 0 << endl;
}
else {
if (a[n - 1] >= 0) {
cout << rightIndex + 1 << endl;
for (int i = 0; i < rightIndex + 1; ++i) {
cout << i + 1 << " " << rightIndex + 2 << " " << n << endl;
}
}
else {
cout << -1 << endl;
}
}
}
}
}
}
ac;
