XP04-02 DAY02

F,IW

2025-08-03 20:17:42

发布于：上海

25阅读

0回复

0点赞

今日复习了普及组算法：DFS&BFS，学习了初赛内容归并排序，拓扑排序，快速排序，复赛内容状态压缩DP。
DFS和BFS的题目都很基础，以前也做了好几篇笔记了，就不在此过多赘述。
一.归并排序
是一种有分治思想的算法。
时间复杂度为 $O(nlogn)$ 。
主要用于求逆序对，初赛的程序阅读等题目可能会考。
模板（排序）：

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int b[100005];
void p(int ll,int mm,int rr){
	int i=ll;
	int j=mm+1;
	int t=0;
	while(i<=mm&&j<=rr){
		if(a[i]>a[j]){
			b[t++]=a[j++];
		}else if(a[i]<a[j]){
			b[t++]=a[i++];
		}else if(a[i]==a[j]){
			b[t++]=a[i++];
			b[t++]=a[j++];
		}
	}
	while(i<=mm)b[t++]=a[i++];
	while(j<=rr)b[t++]=a[j++];
	for(int i=0;i<t;i++){
		a[ll+i]=b[i];
	}
}
void c(int l,int r){
	if(l<r){
		int mid=l+r>>1;
		c(l,mid);
		c(mid+1,r);
		p(l,mid,r);
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	c(1,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

模板（逆序对）：

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int b[100005];
void p(int ll,int mm,int rr){
	int i=ll;
	int j=mm+1;
	int t=0;
	while(i<=mm&&j<=rr){
		if(a[i]>a[j]){
			b[t++]=a[j++];
		}else if(a[i]<a[j]){
			b[t++]=a[i++];
		}else if(a[i]==a[j]){
			b[t++]=a[i++];
			b[t++]=a[j++];
		}
	}
	while(i<=mm)b[t++]=a[i++];
	while(j<=rr)b[t++]=a[j++];
	for(int i=0;i<t;i++){
		a[ll+i]=b[i];
	}
}
void c(int l,int r){
	if(l<r){
		int mid=l+r>>1;
		c(l,mid);
		c(mid+1,r);
		p(l,mid,r);
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	c(1,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

*中午记得重新默写逆序对代码。
*中午已默写，用时4min.
并且升级了代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int b[500005];
long long cnt;
void p(int ll,int mm,int rr){
	int i=ll;
	int j=mm+1;
	int t=0;
	while(i<=mm&&j<=rr){
		if(a[i]>a[j]){
			cnt+=mm-i+1;
			b[t++]=a[j++];
		}else b[t++]=a[i++];
	}
	while(i<=mm)b[t++]=a[i++];
	while(j<=rr)b[t++]=a[j++];
	for(int i=0;i<t;i++){
		a[i+ll]=b[i];
	}
}
void c(int l,int r){
	if(l<r){
		int mid=l+r>>1;
		c(l,mid);
		c(mid+1,r);
		p(l,mid,r);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	c(1,n);
	cout<<cnt;
	return 0;
}

一定要注意：cnt要开long long。
二.状态压缩DP
所谓状态压缩，就是将一串很长的状态（或数字什么的）压缩成很小的一部分。
其实随着算法难度提升至此，可以发现一个很奇妙的事实：
很多算法或多或少是跟二进制，二次方有关的。
也是一种返璞归真吧。
这种算法要从一道01DFS的题目说起。
题目：链接描述
以样例为例：

4
1 2 2 4

此时有四个同学。
DFS枚举的就是每位同学是否来上厕所。
代码长这样：

b[x]=0;
dfs(x+1);
b[x]=1;
dfs(x+1);

那么重新举例，如果有三位同学，枚举出来的结果大概是怎样的？

重新排一下：

将这些二进制转换成十进制，你就会得到：0 1 2 3 4 5 6 7
然后需要注意的是：在使用二进制压缩的时候，一般 $i$ 都从0开始。
代码：

#include<bits/stdc++.h>
using namespace std;
int a[15];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int ans=0;
	for(int i=0;i<1<<n;i++){
		//1<<n:在n为4的时候为10000 ,这里使用<，所以最后只到 1111 
		//从0000到1111，就是二进制的枚举。
		//接下来，判断第j个人是否上厕所 
		int sum=0;
		for(int j=0;j<n;j++){
			if(i>>j&1){
				//第i个人在厕所中.
				 sum+=a[j];
			}
		}
		//判读sum是否为质数.
		if(sum<=1)continue;
		bool p=0;
		for(int i=2;i<sum;i++){
			if(sum%i==0){
				p=1;
				break;
			}
		}
		if(!p)ans++;
	}
	cout<<ans;
	return 0;
}

然后是状态压缩DP经典题目：链接描述
作为一道DP题目（只是这里使用，这道题目的正解应该是DFS），首先要考虑状态表示。
一般都会想到定义dp[i]表示吃掉第1-i块奶酪的最短时间。
但是考虑一个问题：在吃掉第1-i块奶酪的时候，或许小老鼠也吃了第i块奶酪后的奶酪。
顺序也是一个问题：可能我吃1，3，2会更快，但是我只能考虑到1，2，3的可能性。
实际上应该这样定义：double dp[15][1<<15]
注：这里存在 $n\le15$ 。
后面的[1<<15]和上面的DFS那题有同曲同工之妙。
代表了小老鼠吃过的奶酪。
比如小老鼠吃了1，3，4块奶酪，其二进制大概是这样的：1101。
换算一下，就变成了13。
至于状态转移方程，就着代码理解一下吧。

#include<bits/stdc++.h>
using namespace std;
int x[15];
int y[15];
double dp[15][1<<15];
double dis(int i,int j){
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
	}
	//初始化1。 
	for(int i=0;i<1<<n;i++){
		for(int j=0;j<n;j++){
			dp[j][i]=1e9;
		}
	}
	//初始化2。 
	for(int i=0;i<n;i++)dp[i][1<<i]=sqrt(x[i]*x[i]+y[i]*y[i]);
	//最难的部分:
	for(int sta=1;sta<1<<n;sta++){
		//sta表示dp[i][j]的j。 
		//sta不从0开始，因为没有意义。 
		for(int i=0;i<n;i++){
		    //i的含义：到达了i,当前已经走过的合集是sta
			//所以sta要包含i
			if(sta>>i&1){
				for(int j=0;j<n;j++){
					//要去吃的奶酪,且曾经没有吃过 
					if(sta>>j&1)continue;
					dp[j][sta|(1<<j)]=min(dp[j][sta|(1<<j)],dp[i][sta]+dis(i,j));
				}
			} 
		}
	} 
	//计算答案，也因为小老鼠最后可能停在任意位置，所以使用for循环。
	double minx=1e9;
	for(int i=0;i<n;i++){
		minx=min(minx,dp[i][(1<<n)-1]);
	}
	cout<<fixed<<setprecision(2)<<minx;
	return 0;
}

注：明天学习树状数组，今天要预习。
三.快速排序
模板：

#include<bits/stdc++.h>
using namespace std;
int a[100005];
void c(int l,int r){
	if(l>=r)return;
	int pivot=a[l];//pivot是基准数
	int i=l;
	int j=r;
	while(i<j){
		while(i<j&&a[j]>=pivot)j--;
		while(i<j&&a[i]<=pivot)i++;
		swap(a[i],a[j]);
	} 
	swap(a[l],a[i]);
	c(l,i-1);
	c(i+1,r);
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	c(1,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

五.考试
T4:链接描述只提 $40pts$ 的做法。
观察发现：测试点1-4有特殊性质： $x=0$
那么问题就明了很多：如何将y转化为0？
先注意转化的方式：选择一个正整数 $k$ ，然后将 $y$ 除以 $2^k$ 并向下取整。
如何将 $y$ 通过除以 $2^k$
六.昨日复习

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论