程序员进阶之算法练习(七十一)
题目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;