Day2讲课习题题解

[NOIP2003 普及组] 麦森数 - 洛谷

P1045 [NOIP2003 普及组] 麦森数

思路：没啥好新意，直接高精度乘法（后500位可以暴力求），但是考虑到时间复杂度的问题，得用快速幂优化

#include 
#include 
#include 
#include 
using namespace std;
const int N=1010;
int p;
int f[N],res[N],sav[N];
void mul(int a[],int b[],int c[]){
	memset(sav,0,sizeof sav);
	for(int i=1;i<=500;i++)
		for(int j=1;j<=500;j++)
			sav[i+j-1]+=a[i]*b[j];
	for(int i=1;i<=500;i++){
		sav[i+1]+=sav[i]/10;
		sav[i]%=10;
	}
	memcpy(c,sav,sizeof sav);
}
int main()
{
	cin>>p;
	cout<<(int)(log10(2)*p+1)<
	f[1]=2;
	res[1]=1;
	while(p){
		if(p&1)	mul(res,f,res);
		p>>=1;
		mul(f,f,f);
	}
	res[1]-=1;
	for(int i=500;i>=1;i--){
		if(i!=500&&i%50==0)	puts("");
		cout<
	}
	return 0;
}

P1850 [NOIP2016 提高组] 换教室

[NOIP2016 提高组] 换教室 - 洛谷

思路：一个期望dp

除法的话（取模and 答案 是 分数情况下，可以利用快速幂+费马小定理）

#include 
#include 
#include 
using namespace std;
const int N=2e3+10;
const double INF=1e17;
int n,m,v,e;
int c[N][2],g[N][N];
double k[N],f[N][N][2];
int main()
{
	memset(g,0x3f,sizeof g);
	cin>>n>>m>>v>>e;
	for(int i=1;i<=n;i++)	cin>>c[i][0];
	for(int i=1;i<=n;i++)	cin>>c[i][1];
	for(int i=1;i<=n;i++)	cin>>k[i];
	for(int i=1;i<=e;i++){
		int a,b,x;
		cin>>a>>b>>x;
		g[a][b]=g[b][a]=min(x,g[a][b]);
	}
	for(int k=1;k<=v;k++)
		for(int i=1;i<=v;i++)
			for(int j=1;j<=v;j++)	g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
	for(int i=1;i<=v;i++)	g[i][i]=g[i][0]=g[0][i]=0;
    for (int i=0; i <= 2000; i++)
        for (int j = 0; j <= 2000; j++)f[i][j][0] = f[i][j][1] = INF;
    f[1][0][0] = f[1][1][1] = 0;
	for(int i=2;i<=n;i++){
		f[i][0][0]=f[i-1][0][0]+g[c[i-1][0]][c[i][0]];
		for(int j=1;j<=min(i,m);j++){
			int c1=c[i-1][0],c2=c[i-1][1],c3=c[i][0],c4=c[i][1];
			f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0]+g[c1][c3],f[i-1][j][1]+g[c2][c3]*k[i-1]+g[c1][c3]*(1-k[i-1])));
			f[i][j][1]=min(f[i][j][1],min(f[i-1][j-1][0]+g[c1][c3]*(1-k[i])+g[c1][c4]*k[i],f[i-1][j-1][1]+g[c1][c3]*(1-k[i-1])*(1-k[i])+g[c1][c4]*(1-k[i-1])*k[i]+g[c2][c3]*k[i-1]*(1-k[i])+g[c2][c4]*k[i-1]*k[i]));
		}
	}
	double ans=INF;
	for(int i=0;i<=m;i++){
		ans=min(ans,min(f[n][i][0],f[n][i][1]));
	}	
	printf("%.2lf",ans);
	return 0;
}

 P4071 [SDOI2016]排列计数

 [SDOI2016]排列计数 - 洛谷

思路：取模嘛，直接快速幂+费马小定理

#include 
#include 
#include 
using namespace std;
const int N=1e6+10,mod=1e9+7;
typedef long long ll;
int t;
int n,m;
ll f[N],inv[N],d[N];
ll qmi(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)	res=(ll)(res*a)%mod;
		a=(ll)a*a%mod;
		b>>=1;
	}
	return res;
}
void init(){
	f[0]=1;
	for(int i=1;i<=1e6;i++){
		f[i]=i*f[i-1]%mod;
		inv[i]=qmi(f[i],mod-2)%mod;
	}
	d[1]=0,d[2]=1,d[3]=2;
	for(int i=4;i<=1e6;i++)	d[i]=(i-1)*(d[i-1]+d[i-2])%mod;
}
int main()
{
	init();
	cin>>t;
	while(t--){
		cin>>n>>m;
		if(n-m==1)	cout<<0;
		else if(n==m)	cout<<1;
		else if(m==0)	cout<
		else{
			cout<
		}
		puts("");
	}
	return 0;
}

P1966 [NOIP2013 提高组] 火柴排队 

 [NOIP2013 提高组] 火柴排队 - 洛谷

思路：有式子对吧，我们首先把式子化简，平方和公式一套即可得出一个贪心经典问题

然后有一个结论就是：交换相邻两个数，只会让序列逆序对个数+1/-1,直到逆序对减到0的时候，整个过程直接over！

#include 
#include 
#include 
using namespace std;
const int N=1e5+10,mod=1e8-3;
typedef long long ll;
ll ans=0;
int n;
struct Node{
	int x,id;
	bool operator <(const Node &t)	const {
		return x
	}
}a[N],b[N];
int q[N],tmp[N];
void merge(int l,int r){
    if(l>=r) return ;
    int mid=l+r>>1;
    merge(l,mid),merge(mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(q[i]>q[j]){
            ans=(ans+mid-i+1)%mod;
            tmp[k++]=q[j++];
        }else   tmp[k++]=q[i++];
    }
    while(i<=mid)   tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    for(int i=l,j=0;j
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i].x,a[i].id=i;
	for(int i=1;i<=n;i++)	cin>>b[i].x,b[i].id=i;
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)	q[a[i].id]=b[i].id;
	merge(1,n);
	cout<
	return 0;
}