洛谷-算法2-3-分治与倍增1

故事和你91

465人浏览 · 2026-04-27 20:56:41

故事和你91 · 2026-04-27 20:56:41 发布

P1177 【模板】排序

题目描述

将读入的 N 个数从小到大排序后输出。

输入格式

第一行为一个正整数 N。

第二行包含 N 个空格隔开的正整数 ai，为你需要进行排序的数。

输出格式

将给定的 N 个数从小到大输出，数之间空格隔开。

输入输出样例

输入 #1复制

5
4 2 4 5 1

输出 #1复制

1 2 4 4 5

说明/提示

对于 20% 的数据，有 1≤N≤103；

对于 100% 的数据，有 1≤N≤105，1≤ai≤109。

实现代码：

#include<bits/stdc++.h>
using namespace std;
int a[2000010];
int n,m;

int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+m);
	for(int i=1;i<=m;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

P1908 逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai>aj 且 i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update：数据已加强。

输入格式

第一行，一个数 n，表示序列中有 n 个数。

第二行 n 个数，表示给定的序列。序列中每个数字不超过 109。

输出格式

输出序列中逆序对的数目。

输入输出样例

输入 #1复制

6
5 4 2 6 3 1

输出 #1复制

说明/提示

对于 25% 的数据，n≤2500。

对于 50% 的数据，n≤4×104。

对于所有数据，1≤n≤5×105。

应该不会有人 O(n2) 过 50 万吧 —— 2018.8 chen_zhe。

实现代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n,a[500010],c[500010];
long long ans;

void msort(int b,int e)
{
    if(b==e)  
		return;
    int mid=(b+e)/2,i=b,j=mid+1,k=b;
    msort(b,mid),msort(mid+1,e);
    while(i<=mid&&j<=e)
    	if(a[i]<=a[j])
    		c[k++]=a[i++];
    	else
    		c[k++]=a[j++],ans+=mid-i+1;
    while(i<=mid)
    	c[k++]=a[i++];
    while(j<=e)
    	c[k++]=a[j++];
    for(int l=b;l<=e;l++)
    	a[l]=c[l];
} 

int main()
{
    scanf("%d",&n); 
    for(int i=1;i<=n;i++)
    	scanf("%d",&a[i]);
    msort(1,n);
    printf("%lld",ans);
    return 0;
}

P1966 [NOIP 2013 提高组] 火柴排队

题目背景

NOIP2013 提高组 D1T2

题目描述

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：∑(ai−bi)2。

其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 108−3 取模的结果。

输入格式

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。

第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式

一个整数，表示最少交换次数对 108−3 取模的结果。

输入输出样例

输入 #1复制

4
2 3 1 4
3 2 1 4

输出 #1复制

输入 #2复制

4
1 3 4 2
1 7 2 4

输出 #2复制

说明/提示

输入输出样例说明一

最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

输入输出样例说明二

最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。

数据范围

对于 10% 的数据， 1≤n≤10；

对于 30% 的数据，1≤n≤100；

对于 60% 的数据，1≤n≤103；

对于 100% 的数据，1≤n≤105，0≤ai,bi<231 且对于任意 1≤i<j≤n，ai=aj，bi=bj。

实现代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=99999997;
long long n,x[10000005],p[1000005],ans=0;
struct fire{
    int hi,bh;
}l1[1000005],l2[1000005];
bool cmp1(fire a,fire b)
{
    return a.hi<b.hi;
}
void msort(int s,int t)
{
    if(s==t)return ;
    int mid=(s+t)/2;
    msort(s,mid);msort(mid+1,t);
    int i=s,k=s,j=mid+1;
    while(i<=mid && j<=t)
    {
        if(x[i]<=x[j])
        {
            p[k]=x[i];
            ++k;++i;
            
        }
        else
        {
            p[k]=x[j];
            ++k;++j;
            ans=(ans+mid-i+1)%mod;
        }
    }
    while(i<=mid)
    {
        p[k]=x[i];
        ++k;++i;
    }
    while(j<=t)
    {
        p[k]=x[j];
        ++k;++j;
    }
    for(int i=s;i<=t;i++)
    {
        x[i]=p[i];
    }
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&l1[i].hi),l1[i].bh=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&l2[i].hi),l2[i].bh=i;
    sort(l1+1,l1+n+1,cmp1);
    sort(l2+1,l2+n+1,cmp1);
    for(int i=1;i<=n;i++)
        x[l2[i].bh]=l1[i].bh; 
    msort(1,n);
    printf("%lld",ans);
    return 0;
}

P1226 【模板】快速幂

题目描述

给你三个整数 a,b,p，求 abmodp。

输入格式

输入只有一行三个整数，分别代表 a,b,p。

输出格式

输出一行一个字符串 a^b mod p=s，其中 a,b,p 分别为题目给定的值， s 为运算结果。

输入输出样例

输入 #1复制

2 10 9

输出 #1复制

2^10 mod 9=7

说明/提示

样例解释

210=1024，1024mod9=7。

数据规模与约定

对于 100% 的数据，保证 0≤a,b<231，a+b>0，2≤p<231。

实现代码：

#include<cstdio>
long long B,P,K;
long long qpow(int base,int p){
	long long ans=1,tmp=base;
	while(p!=0){
		if(p&1){
			ans=(ans%K*tmp%K)%K;
		} 
		tmp=(tmp%K*tmp%K)%K;
		p=p>>1;
	} 
	ans=ans%K;
	return ans;
} 
int main(){
	scanf("%lld%lld%lld",&B,&P,&K);
	long long ans=qpow(B,P);
	ans=ans%K;
	printf("%lld^%lld mod %lld=%lld",B,P,K,ans);
	return 0;
}

P1045 [NOIP 2003 普及组] 麦森数

题目描述

形如 2P−1 的素数称为麦森数，这时 P 一定也是个素数。但反过来不一定，即如果 P 是个素数，2P−1 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 P=3021377，它有 909526 位。麦森数有许多重要应用，它与完全数密切相关。

任务：输入 P(1000<P<3100000)，计算 2P−1 的位数和最后 500 位数字（用十进制高精度数表示）

输入格式

文件中只包含一个整数 P(1000<P<3100000)

输出格式

第一行：十进制高精度数 2P−1 的位数。

第 2∼11 行：十进制高精度数 2P−1 的最后 500 位数字。（每行输出 50 位，共输出 10 行，不足 500 位时高位补 0）

不必验证 2P−1 与 P 是否为素数。

输入输出样例

输入 #1复制

输出 #1复制

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

说明/提示

【题目来源】

NOIP 2003 普及组第四题

实现代码：

#include<bits/stdc++.h>
int n,a[1010],res[1010],cnt;
void multiply1(){
    int tmp[1010]={0};
    for(int i=0;i<500;i++){
        for(int j=0;j<500;j++) tmp[i+j]+=res[i]*a[j];
    }
    int t=0;
    for(int i=0;i<500;i++){
        tmp[i]+=t;
        res[i]=tmp[i]%10;
        t=tmp[i]/10;
    }
}
void multiply2(){
    int tmp[1010]={0};
    for(int i=0;i<500;i++){
        for(int j=0;j<500;j++) tmp[i+j]+=a[i]*a[j];
    }
    int t=0;
    for(int i=0;i<500;i++){
        tmp[i]+=t;
        a[i]=tmp[i]%10;
        t=tmp[i]/10;
    }
}
void quick_pow(int p){
    res[0]=1,a[0]=2;
    while(p){
        if(p&1) multiply1();
        multiply2();
        p>>=1;
    }
}
int main(){
    scanf("%d",&n);
    int length=n*log10(2)+1;
    printf("%d\n",length);
    quick_pow(n);
    res[0]-=1; 
    for(int i=499;i>=0;i--){
        if(cnt==50) printf("\n"),cnt=0;
        printf("%d",res[i]);
        cnt++;
    }
    return 0;
}