2.21 CodeForces 补题

A. Min Or Sum

题目链接

解题思路：

t组样例，每组给n个数据，对这n个数做或运算，输出。

代码如下：

#include<iostream>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,x,ans=0;
		cin>>n;
		while(n--)
		{
			cin>>x;
			ans=ans|x;
		}
		cout<<ans<<endl;
	}
	return 0;
}

B. Avoid Local Maximums

题目链接

大致题意：

t组样例，每组样例有n个数字，你可以将这些数字替换成任意数字，使这个数组中不含有峰值。题目要求输出最少的操作次数，及操作后的结果数组。

解题思路：

比较每个数字前面和后面的数，如果这个数（i）同时大于它前面的数（i-1）和它后面的数（i+1），则说明它是峰值，那么就将它后面的数字（i+1）进行替换。被替换数（i+1）的将被它前面那个数（i）与后面那个数（i+2）的最大值替换。
我写的有点绕，括号内的i表示第i个数。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,sum=0;
		cin>>n;
		int a[n];
		for(int i=0;i<n;i++) cin>>a[i];
		
		for(int i=1;i<n-1;i++)
		{
			if(a[i]>a[i-1] && a[i]>a[i+1])
			{
				sum++;
				a[i+1]=max(a[i],a[i+2]);
			}
		}
		cout<<sum<<endl;
		for(int i=0;i<n;i++) cout<<a[i]<<" ";
		cout<<endl;
	}
	return 0;
}

C. Differential Sorting

题目链接

题目大意：

t组样例，每组样例有n个数，你可以用第y个数减去第z个数的得数替换第x个数，但是必须要符合1≤x<y<z≤n。要求操作结束后这个数组没有任何递减的部分。输出操作次数m以及每一次的操作过程，m不用是最小值。如果不行的话输出-1。

解题思路：

由题意可知，最后两个数一定不能递减，不然直接输出-1。
在此基础上，我们要保证这个数组非递减，就得从后往前操作。如果前一个数比后一个数大，那么要从后面取两个数做差并赋给前一个数。那我们就要判断这个差值是否比后一个数小。由于我们知道减去一个正数一定会变小，减去一个负数一定会变大，所以我们需要找到一个非负数，每次操作都减去它。
思路大致是这样，细节内容我会写在代码注释里。

代码：

#include<iostream>
using namespace std;
long long a[200010];
struct ans{
	int x;
	int y;
	int z;
}ans[200010];

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,i,sum=0,v=0;
		int flag=0;
		cin>>n;
		for(i=0;i<n;i++) 
		{
			cin>>a[i];
			if(a[i]>=0) v=i;//找到位于最后的一个非负数
		}	
		
		i=n-1;
		if(a[i]<a[i-1]) 
		{
			cout<<"-1"<<endl;//如果最后两个数递减则直接输出-1
			continue;//因为操作只允许我们改变倒数第三个及以前的数
		}			//所以最后两个数如果递减，是无法改动的
		
		int k=0;
		for(i=i-2;i>=0;i--)
		{
			if(a[i]>a[i+1]){//判断是否比后一个小
				if(v<=i+1){//如果不是，则判断它后面第二位及以后有没有非负数
					flag=1;//如果没有，那么它无法变小，也就无法改变递减的情况了
					break;
				}else{
					a[i]=a[i+1]-a[v];//如果有，那么将它更新为更小的数
					sum++;//更新操作次数
					ans[k].x=i+1;//标记操作位置
					ans[k].y=i+2;
					ans[k].z=v+1;
					k++;
				}
			}
			if(flag==1)break;
		}
		if(sum>n)flag=1;
		
		if(flag==1)cout<<"-1"<<endl;
		else
		{
			cout<<sum<<endl;
			for(int j=0;j<k;j++) 
				cout<<ans[j].x<<" "<<ans[j].y<<" "<<ans[j].z<<endl;
		}
	}
	return 0;
 }