比赛链接: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(); } }