比赛链接:https://codeforces.ml/contest/1736/

A题:水题

B题:gcd构造题。大意是给出一个长度为n的数组,求是否存在一个长度为n+1的数组b,使得ai = gcd(bi,bi+1)。
这个题WA了好几发。最开始的几个猜想思路都错了。
思路:对bi进行构造,我们总能使得bi为ai和ai-1的最小公倍数。这样在固定a1之后,我们总能顾全ai和ai-1.

最后扫一遍1-n-1,对an和bn,我们只需要特判,bn%an是否等于0,如果等于0,我们总能通过另一个bn+1 来构造出,因为bn+1不需要顾及an+1。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn = 1e5+10;
ll a[nn]; 
ll b[nn];
void solve()
{
	memset(a,0,sizeof a);
	memset(b,0,sizeof b);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	bool flag = true;
	b[1] = a[1];
	for(int i=2;i<=n;i++){
		b[i] = a[i]*a[i-1]/__gcd(a[i-1],a[i]);
	}
	b[n+1] = a[n];
	for(int i=1;i<n;i++){
		if(__gcd(b[i],b[i+1])!=a[i]){
			flag = false;
			break;
		}
	}
	if(b[n]%a[n]!=0) {
		flag = false;
	}
/*	for(int i=1;i<=n+1;i++)
		cout<<b[i]<<' ';
	cout<<endl; */
/*	for(int i=3;i<=n;i++){
		if(a[i-2]>a[i-1]&&a[i]>a[i-1]&&a[i-2]%a[i-1]==0&&a[i]%a[i-1]==0)
			flag = false;
	}*/
	printf("%s\n",flag==true?"YES":"NO");
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

 

C题:子数组问题。给出一个长度为n的数组a,求出存在多少个子数组,当子数组成为全新的数组后,在下标i 从 1-j-i+1 的每一项都存在ai>i。

这个题当时题意理解的并不是很好,导致全程在面向样例编程。

思路:我们可以通过l和r 或 i和j,记录起始和终止的左右端点,本质上也就是个双指针问题。在我们找到一段满足题意的子数组后,我们总能够通过r-i,
(这里r已经指向了满足之后的下标)来获得从i开始的子数组满足数量,然后更新i,直到可以再次更新j。直接过一遍。

从头到尾都没有想这个思路,因为看见复杂度后就很恐惧n^2,但实际上这么走一遍,复杂度只有2n而已。本质上是i过了一遍,然后j过了一遍。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void solve()
{
	int n;
	cin>>n;
	vector<int> a(n+1); 
	for(int i=1;i<=n;i++)
		cin>>a[i];
	ll ans = 0;
	for(int i=1,j=1;i<=n;i++){
		while(j<=n&&a[j]-(j-i+1)>=0) j++;//i - j 永远是一个符合条件的,可以直接一次次更新ans。 
		ans+=(j-i);
	}
	cout<<ans<<endl;
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}