暑假训练打卡——Day 1

今天学习了分治算法，学习了很多前辈的解题思路方法，做了几道洛谷的练习题，发个博客

分治算法 解决问题的思路是：先将整个问题拆分成多个相互独立且数据量更少的小问题，通过逐一解决这些简单的小问题，最终找到解决整个问题的方案。具体请查看：link。

今日题解

• 题一： link 思路：其实这是一道快速幂的题，主要运用了分治思想，我们做这道题时由于给的范围最大在2^31,如果直接暴力写的话无疑会超出数据范围，所以我们将运用分而治之的思想，例如：将2的10次方写成4的5次方，然后变成16的2次方乘以4，这样一来原本要运算十次变成了四次，缩短了计算次数。结合同余定理中：(a×b)mod n=((amod n)×(bmod n))mod n，在每次计算中两个乘数都先取余再计算再同时取余就可以减小很多数据量，不说过多，附上代码：

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll a,b,c;
ll ksm(ll base,ll power,ll x) {
	ll result = 1;
	while (power > 0) {
		if (power % 2 == 1) {
			result = result * base % x;
		}
		power = power / 2;
			base = (base * base) % x;
	}
	return result;
}
int main()
{
	scanf("%lld %lld %lld",&a,&b,&c);
	cout<<a<<'^'<<b<<' '<<"mod "<<c<<"="<<ksm(a,b,c)<<endl;
	return 0;
}

• 题二 link 思路：本题即是最大子段和问题，要解决这个问题首先要将输入的数据以中间数据为界分为左右两部分，分别由中间向着两边进行累加，不断更新累加过程中的最大值，再用一点递归思想，最后将左右两边的最大值与整个数据之和作比较，求得最大子段和，代码如下：

 #include <iostream>
using namespace std;
typedef long long ll;
const int N=1e8+7;
int a[N];
int f(int l,int r)
{
	int m=(l+r)/2;
	int sumL=0,ansL=a[m];
	int sumR=0,ansR=a[m+1];
	for(int i=m;i>=l;i--){
		sumL+=a[i];
		ansL=max(sumL,ansL);
	}
	for(int i=m+1;i<=r;i++){
		sumR+=a[i];
		ansR=max(ansR,sumR);
	}
	return ansL+ansR;
}
int sumMAx(int l,int r)
{
	int m=(l+r)/2;
	if(l==r) 
		return a[m]; 
	else{
	int L=sumMAx(l,m);
	int R=sumMAx(m+1,r);
	int A=f(l,r);
	int x=max(L,max(R,A));
	return x;
	}
}
int main()
{
	ll n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cout<<sumMAx(0,n-1)<<endl;
	return 0;
}

• 题三 link 思路：这是一个逆序对的问题，逆序对的意思就是序列中相邻的两个数，前一个数序号较小但数据比后面的数大，这就是一个逆序对。本题用归并排序的思想，由于在归并排序中会进行排序，将小的往前移动，使逆序对变为有序对，所以在归并排序中逆序对的个数即是排序过程中交换位置的次数，由此我们可写代码如下：

#include <iostream>
#include<algorithm>
using namespace std;
const int N=1e6+7;
typedef long long ll;
int a[N],b[N];
int n;
ll merge_sort(int l,int r)
{
	if(r-l<1) return 0;
	int mid=(l+r)>>1;
	ll ans=merge_sort(l,mid);
	ans+=merge_sort(mid+1,r);
	int i=l,j=mid+1,k=0;
	while(i<=mid&&j<=r) 
	{
		if(a[i]<=a[j])
		{
			b[k++]=a[i++];
		}
		else{
			b[k++]=a[j++];
			ans+=mid-i+1;
		}
	}
	while(i<=mid){
		b[k++]=a[i++];
	}
	while(j<=r)
	{
		b[k++]=a[j++];
	}
	for(i=l,j=0;i<=r;)
	{
		a[i++]=b[j++];
	}
	return ans;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	cout<<merge_sort(0,n-1)<<endl;
	return 0;
}

今天的打卡结束啦！