程序员进阶之算法练习（七十一）
题目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;腾讯云开发者
