比赛地址:https://codeforc.es/contest/1698/

这一场比赛是我没有参加的一场,忘记了是什么原因了,但是我还是回过头来补了一下题。

自己单独A了三道,感觉有点简单,后悔没做了┭┮﹏┭┮,804的直接打了12000多的rank,一个题没做出来,这波血亏。

这套题感觉前三道都挺简单的。

A题:异或运算的题,没错,又是这个。不过这次我A出来了。大意是从数组a中找到一个数,令其余所有数的异或等于这个数,数据很小,可以直接暴力。

code:


#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	vector<int> v;
	cin>>t;
	while(t--)
	{
		v.clear();
		int x,n;
		scanf("%d",&n);
		while(n--)
		{
			scanf("%d",&x);
			v.push_back(x);
		}
		int ans = 0;
		for(int i=0;i<v.size();i++)
		{
			ans = 0;
			for(int j=0;j<v.size();j++)
			{
				if(i!=j)
					ans = ans^v[j];
			}
			if(ans == v[i])
			{
				printf("%d\n",ans);
				break;
			}
		} 
	}
}
B题:大意就是输入一个k,在数组a中可以让连续k个数的值+1。让我们求出经过操作后(不限次数),我们可以得到多少a[i]>a[i-1]+a[i+1]。
这个题就是一个规律题。我们考虑k是1和不是1的情况,如果k是1,那么无疑我们可以得到一个最多数量的。我们可以将插空的数全部调整到很高的数。通过计算,我们得出奇数时ans = n/2偶数时 ans=n/2-1。然后就是k为>1的数,不难看出,我们无法增加任意一组符合条件的数,所以,其ans还是原来符合条件的那些数,可以n暴力。


code:

#include<bits/stdc++.h>
using namespace std;
const int maxt = 2*1e5+10;
int a[maxt];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(a,0,sizeof a);
		int n,k,ans=0;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		if(k==1)
		{
			if(n%2==1)
			 	ans = n/2;
			else
				ans = n/2-1;
			cout<<ans<<endl;
		}else
		{
			for(int i=2;i<n;i++)
			{
				if(a[i]>a[i-1]+a[i+1])
					ans++;
			}
			cout<<ans<<endl;
		}
	}
}

C题:有些难度,但是感觉还好。大意就是给我们一个数组a,让我们看看是否每个三元组相加的数都可以在这个数组中找到。这里我用了我以前最常用的分析问题的方法,就是先分析复杂度,在计算暴力的复杂度,如果相差不大,那么考虑简化,如果相加过大,考虑用逆向思维找技巧。这个方法感觉可以用在很多数论题中。

如果暴力,我们可以n^3logn 解决,即暴力三层,然后set查找。  比我们预计的nlogn要多n^2。于是,我们考虑直接去寻找不符合条件的情况,也就是说我们不应该列举那么多符合情况的。我们考虑到,如果存在三个正数,那么令最高的正数加上两个正数一定不存在,所以可以pass。同理可得三个负数也是一样的。想到这里,这个题就解决了一大半了。剩下就是考虑0,如果不存在0,那么我们只有枚举三个数来计算。如果存在1个0,那么我们需要多考虑到枚举两个数相加然后加上0,也就是两个数相加,如果存在三个0,我们还需要额外考虑一个数。当然,一个数一定存在。

因为先前3个正数3个负数的思路我们缩小了数据范围,所以可以直接暴力。这里需要拿出0来单独确定情况就是怕0太多,导致tle。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxt = 2*1e5+10;
int a[maxt];
set<int>se;
bool cmp(int a,int b)
{
	return a>b; 
};
int main()
{
	//限制  nlogn  或  n
	//暴力  n^3logn   需要简化  n^2
	//如果要获取所有的三元组,其复杂程度本身超过限制。考虑从另一个角度入手,想办法让一个三元组不符合条件。
	
	//过程性猜想:如果有三个整数,那么一定pass,因为最大的那个整数加上两个整数一定不存在
	//如果存在三个负数,情况也是如此,所以se.size()应该要小于等于5(含有0)
	//这个时候暴力,可以只暴力出5个不相同的数,这就非常nice 了 
	int t;
	cin>>t;
	while(t--)
	{
		memset(a,0,sizeof a);
		se.clear();
		int n,zheng=0,fu=0,ling=0;
		scanf("%d",&n);
		int j=1,x;;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x);
			if(x>0)	a[j++]=x,zheng++;
			if(x<0)	a[j++]=x,fu++;
			if(x==0)	ling++;
			se.insert(x);
		}
		if(zheng>=3||fu>=3)
			printf("NO\n");
		else
		{
			int sign = 0;
			for(int i=1;i<j;i++)
			for(int k=1;k<j;k++)
			for(int m=1;m<j;m++)
				if(i!=k&&i!=m&&k!=m&&se.count(a[i]+a[k]+a[m])==0)
				{
					sign = 1;
					goto xy;
				}
			if(ling>0)//如果存在零,那么我们考虑两个数相加和三个数相加的情况 
			{
				for(int i=1;i<j;i++)
				for(int k=1;k<j;k++)
					if(i!=k&&se.count(a[i]+a[k])==0)
					{
						sign = 1;
						goto xy;
					}		
			}			
			xy:	if(sign == 1) printf("NO\n"); else printf("YES\n");
		}
	} 
}