比赛链接:https://codeforc.es/contest/1708

就A了A题,还用了40分钟。B题的题意理解上有些问题,我以为对于每一个l<=i<=r,a[i]只能使用一次。所以就一直WA,直到比赛结束。

A题:大意就是给出一个数组,你可以在任意时刻执行一个操作,对于 2<=i<=n,可以使得a[i] = a[i] - a[i-1],求是否能将对于2<=i<=n,使得所有a[i] = 0。

这个题我当时考虑到了很多种方法,最开始的方法是判断它是否是一个等差数列,对于一个等差数列,令a[i] = a[i] - a[i-1] =d,同样可以使得a[i-1]=d。在a[i]和a[i-1]都等于d的时候,我们可以使得a[i] = d。这个猜想在样例当中是成立的。看似没有任何问题。
提交了一次WA了,原因是对于i=2时,公差d如果不等于a[1] ,则无法使得a[2]=0。

解决方法:我们可以得出的一个思路是,当前这个数能否变为0,取决于它的前一个数,它的前一个数又取决于前一个数的前一个数。这么我们可以感觉到能否成立可能和a[1]有关。而a[2]要想变成0,一定是a[1]的倍数。而a[2]在执行操作时,变换的数也一定是a[1]的倍数,它之后的数要想通过它来置变也需要是它的倍数,所以题的关键的就是对于所有的对于 2<=i<=n都有a[i]%a[1]=0

code:

#include<bits/stdc++.h>
using namespace std;
const int nn = 110;
int a[nn];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int flag = 1;
		scanf("%d",&a[1]);
		for(int i=2;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]%a[1]!=0)
				flag = 0;
		}
		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
 } 


 B题:大意就是给出一个数n,求a[1] -  a[n],在区间l和r中找到一个数,对于l<=a[i]<=r使得gcd(a[i],i)互不相同。如果可以,找到任意一种情况

这里需要注意的是对于l<=a[i]<=r ,a[i]我们可以使用多次,我做这道题的时候考虑的就有点多了,想着如果一个数被其他a[i]所使用那么就不能再用了,所以需要先遍历大数i进行判断。//
通过观察我们易得  要想使得这些数互不相同,需要令他们的gcd等于i。这么我们可以去找刚好大于l和最小i倍数这一个数。也就是((l-1)/i +1)*i  看看这个数是否<=r。这个数一定大于l。

code:

#include<bits/stdc++.h>
using namespace std;
const int lr = 1e8;
vector<int>ve;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ve.clear(); 
		int n,l,r;
		scanf("%d%d%d",&n,&l,&r);
		for(int i=1;i<=n;i++)
		{
			if(((l-1)/i+1)*i<=r)
				ve.push_back(((l-1)/i+1)*i);
			else
			{
				printf("NO\n");
				goto endt;
			}
		}
		printf("YES\n");
		for(int i=0;i<ve.size();i++)
			 printf("%d ",ve[i]);
		printf("\n");
		endt:;
	}
 }