B. Orac and Models

题目链接：点击查看

做了不少div2了，没想到b就是dp了，可能div4出来了，div2，div3都要增加点难度。（我只是个小caiji）

题目描述：

就是从数组中找最长上升子序列，只不过加了限制，找出来的元素下标要成比例。

题目分析：

显然dp就可以解决，LIS平时dp做法就是O(N*N)，而这题刚好给你成比例，复杂度降为O(nlogn)，和埃式筛法复杂度一样吧！
转移方程：dp[j]=max(dp[j],dp[i]+1)。

代码：

#include<bits/stdc++.h> using namespace std; int t,n; int a[100005]; int dp[100005]; int main() {  cin >> t; while(t--){ int maxn = 1; scanf("%d",&n); for(int i = 1; i <= n; ++i){ scanf("%d",&a[i]);    dp[i]=1;//初始化  } for(int i = 1; i <= n/2; ++i){//只用枚举一半即可 for(int j = i*2; j <= n; j+=i){//按照倍数递增每次循环更新 if(a[j]>a[i]){      dp[j]=max(dp[j],dp[i]+1);      maxn=max(maxn,dp[j]); } } }   cout << maxn << endl; } return 0; } 

C. Orac and LCM

题目链接：点击查看

题目描述：

一个长度为 N 的数组，求 gcd {lcm({ai , aj}) | i < j}

题目分析：

对于 a1 ，它后面的lcm为 lcm(a1 , a2) , lcm(a1 , a3) … lcm(a1 , an)，则gcd1 为 gcd ( lcm(a1 , a2) , lcm(a1 , a3) … lcm(a1 , an) ) ，gcd( lcm(a1 , a2) , lcm(a1 , a3) … lcm(a1 , an) ) 可以化为 lcm (a1 , gcd (a2 , a3 , … an) )，此处证明参考大佬博客。那么最后答案就为 ans = gcd( gcd1 , gcd2 , … gcdn ) ， 我们维护一个后缀就可以搞定了。

代码：

#include<bits/stdc++.h> using namespace std; typedef long long ll; int n; //开long long ll a[100005]; ll sum[100005];  ll gcd(ll x,ll y){ return y==0?x:gcd(y,x%y); }  ll lcm(ll x, ll y){ return x*y/gcd(x,y); } int main() {  cin >> n; for(int i = 1; i <= n; ++i){   cin >> a[i]; } //记录后缀gcd  for(int i = n; i >= 1; --i){   sum[i]=gcd(sum[i+1],a[i]); }  ll ans=0; for(int i = 1; i <= n; ++i){   ans=gcd(ans,lcm(a[i],sum[i+1])); }  cout << ans; return 0; }