A. Min Or Sum
对于每一次OR操作,如果两个数的每一位都是1,那么就可以选择删除其中的一个一,例如1001和110(都为二进制),那么就可以选择变为1111与000,也就是说,对于给予的所有数,只要是二进制的每一位都保留一个一,那么得到的和就是最小值。而保留一个一这种操作,正好可以通过|做到,所以只需要对所有数进行一次|运算就可以得到答案了。0|任何一个数x,结果都是x,就不需要再拿出第一个数了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
long long ans = 0, tmp;
cin >> n;
while (n--)
{
cin >> tmp;
ans |= tmp;
}
cout << ans << endl;
}
return 0;
}
B. Avoid Local Maximums
题目要求去掉所有的局部最大值,根据样例的分析,可以得到消除局部在最大值的一种方法是:对局部最大值a[i]的右边一个值a[i+1]进行操作,将其赋值为其左右两个值(a[i]与a[i+2])的最大值即可。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 200010;
int a[N];
int maxone[N];
bool check(int x)
{
if (a[x] > a[x - 1] && a[x] > a[x + 1])
return true;
else
return false;
}
int main()
{
int t, tmp;
scanf("%d", &t);
while (t--)
{
int n, k = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 1; i < n - 1; i++)
{
if (a[i] > a[i - 1] && a[i] > a[i + 1])
maxone[k++] = i;
}
int ans = 0;
for (int i = 0; i < k; i++)
{
int tmp = maxone[i];
if (check(tmp))
{
a[tmp + 1] = max(a[tmp], a[tmp + 2]);
ans++;
}
else
continue;
}
printf("%d\n", ans);
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
return 0;
}
C. Differential Sorting
首先进行一个简单的判断,因为x < y < z < n ,所以无论如何,也无法对最后两个数进行操作,所以如果a[n-1]< a[n],那么这个数组一定无法组成非递减序列,输出-1。(1)
然后再从n-2开始向前遍历整个数组,如果a[i]满足a[i]>=a[i+1],就继续遍历,同时更新y,否则就进行替换。(2)
替换前仍需要进行一次判断,判断a[y]-a[z]是否小于等于a[i+1],这样才能满足递增序列。如果不满足,就可以输出-1,跳出循环了。(3)
替换完毕后,将当前坐标i,y,z存入,有递增可知,当前的a[i]一定是目前替换完毕后的最小值,所以需要将y替换为i。(4)
最后将记录操作次数的ans与存储每次操作下标的I、Y、Z输出即可。(5)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 200010;
long long a[N];
vector<int> I, Y, Z;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
int y = n - 1, z = n, ans = 0, condition = 0;
if (a[y] <= a[z])//(1)
{
for (int i = n - 2; i >= 1; i--)//(2)
{
if (a[i] > a[i + 1])
{
if (a[i + 1] < a[y] - a[z])//(3)
{
cout << "-1" << endl;
condition = 1;
break;
}
else//(4)
{
I.push_back(i);
Y.push_back(y);
Z.push_back(z);
a[i] = a[y] - a[z];
y = i;
ans++;
}
}
else
y = i;
}
if (condition == 0)//(5)
{
cout << ans << endl;
for (int i = 0; i < I.size(); i++)
cout << I[i] << " " << Y[i] << " " << Z[i] << endl;
}
I.clear();
Y.clear();
Z.clear();
}
else
cout << "-1" << endl;
}
return 0;
}