记录第一篇博客codeforces round #641 div2

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;
}
上一篇:6572. lg


下一篇:GCD and LCM HDU - 4497