XCPC Notes

Appearance

发布时间：2024-04-25

双端队列 ​

应用：涉及到只有0和1的最短路问题
如果是0则放队头
如果是1则放队尾

DFS ​

迭代加深 ​

  • 适用于问题递归的深度很深，但是答案深度可能很浅的情况，可以有效减少无效的搜索
  • 每次设置一个深度，超过深度则不搜
  • 与宽搜区别：假设递归为多叉树，最小为二叉树，宽搜的空间复杂度会到达O(2n)O(2^n),而迭代加深为O(h)O(h)
  • 每次加深重新搜不影响复杂度原因：20+21+22+2h−1=2h−12^0+2^1+2^2+2^{h-1}=2^h-1 ，而第 hh 层有 2h2^h 个节点，因此不影响

UVA529 Addition Chains ​

题意 ​

img

思路 ​

迭代加深，并剪枝

  1. 去重，从大到小搜，后一个数要比前一个数大
  2. 假设后面都比前面一个数大1但是结果还是比n大，直接返回
  3. 当前数一定不会超过最大数的两倍，假设每次都取最大数的两倍，仍到达不了n，返回(最重要的一点)
cpp
int path[N],n;
bool dfs(int u,int dep){
	if(u>dep){
		if(path[u-1]==n)return true;
		return false;
	}
	if(path[u-1]+dep-u+1>n)return false;
	if(path[u-1]*(1ll<<dep-u+1)<n)return false;
	vector<bool> st(N);
	for(int i=u-1;i>=1;i--){
		for(int j=i;j>=1;j--){
			int x=path[i]+path[j];
			if(x>n||path[u-1]>=x||st[x])continue;
			st[x]=1;
			path[u]=x;
			if(dfs(u+1,dep))return true;
		}
	}
	return false;
}
void solve(){
	path[1]=1;
	while(cin>>n,n){
		int depth=1;
		while(!dfs(2,depth))depth++;
		for(int i=1;i<=depth;i++)cout<<path[i]<<" \n"[i==depth];
	}
}

双向DFS ​

预处理出前半部分，后半部分优化

CH2401 送礼物 ​

题意 ​

n个礼物，有重量g[i]，求最多拿起的不超过w的重量
1≤n≤461 \leq n \leq 46
1≤gi,w≤231−11 \leq g_i,w \leq 2^{31}-1

思路 ​

  • 本题很明显是个背包问题，时间复杂度为O(nw)O(nw) ，这里w很大，会超时
  • 如果采用爆搜，则为O(2n)O(2^n)，也会超时
  • 此时可以将数据分成两部分k,n-k
    • 对于前半部分,2k预处理出全部的能组成的数，然后排序去重，时间复杂度O(2klog2k)=O(k⋅2k)2^k 预处理出全部的能组成的数，然后排序去重 ，时间复杂度O(2^klog2^k)=O(k \cdot 2^k)
    • 后半部分，O(2n−k)处理出后半部分，然后二分查找小于等于w−sum的前半部分的最大值，时间复杂度O(k⋅2k)后半部分，O(2^{n-k})处理出后半部分，然后二分查找小于等于w-sum的前半部分的最大值，时间复杂度O(k \cdot 2^k)
    • 均衡二者复杂度，k=n2k=\frac{n}{2}
  • 注意：本题卡STL
cpp
int n,k;
int pre[1<<25];
int a[50],w,ans,cnt;
void dfs1(int u,LL sum){
	if(u==k+1){
        pre[cnt++]=sum;
		return;
	}
	dfs1(u+1,sum);
	if(sum+a[u]<=w)dfs1(u+1,sum+a[u]);
}
void dfs2(int u,int sum){
	if(u==n+1){
        int l=0,r=cnt-1;
        while(l<r){
            int mid=l+r+1>>1;
            if(pre[mid]<=w-sum)l=mid;
            else r=mid-1;
        }
		ans=max(ans,sum+pre[l]);
		return;
	}
	dfs2(u+1,sum);
	if(sum+a[u]<=w)dfs2(u+1,sum+a[u]);
}
void solve(){
	cin>>w>>n;
	k=n/2;
	for(int i=1;i<=n;i++)cin>>a[i];
	dfs1(1,0);
	sort(pre,pre+cnt);
	cnt=unique(pre,pre+cnt)-pre;
	dfs2(k+1,0);
	cout<<ans<<"\n";
}

IDA* ​

配合迭代加深，如果当前估价步数已经大于max_length，则直接剪掉

排书 ​

题意 ​

给定一个序列，每次可以将序列的某一部分拿出来，插到另一个位置，求排好序的最小次数
1≤n≤151 \leq n \leq 15

思路 ​

  • 首先考虑有多少种移动方案
    • 假设枚举长度为i，则有n−i+1中假设枚举长度为i，则有n-i+1中
    • 剩余n−i个元素，有n−i种插法，(n−i+1)∗(n−i)剩余n-i个元素，有n-i种插法，(n-i+1)*(n-i)
    • 前往后和后往前会有重复，因此除以2
    • 因此总方案数为∑i=1N(n−i+1)∗(n−i)2因此总方案数为\frac{\sum_{i=1}^N(n-i+1)*(n-i)}{2}
    • 通项公式为n∗(n+1)∗(n+2)3\frac{n*(n+1)*(n+2)}{3}
    • 14∗15∗162∗3=560种\frac{14*15*16}{2*3}=560种
  • 因此爆搜复杂度为O(5604)O(560^4)
  • 双向深搜和广搜可以优化到O(5602)O(560^2)
  • 本题采用IDA*，估价函数即为后继错误的数量，每次移动会改变3个后继，如果当前最小操作数大于预期，直接退出
cpp
int n;
int w[5][20];
int a[20];
int f(){
	int cnt=0;
	for(int i=1;i<n;i++)cnt+=(a[i]+1!=a[i+1]);
	return (cnt+2)/3;
}
bool dfs(int dep,int max_dep){
	int x=f();
	if(dep+x>max_dep)return false;
	if(x==0)return true;
	for(int len=1;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			for(int k=r+1;k<=n;k++){
				int p=l;
				memcpy(w[dep],a,sizeof a);
				for(int x=r+1;x<=k;x++,p++)a[p]=w[dep][x];
				for(int x=l;x<=r;x++,p++)a[p]=w[dep][x];
				if(dfs(dep+1,max_dep))return true;
				memcpy(a,w[dep],sizeof a);
			}
		}
	}
	return false;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int dep=0;
	while(dep<5&&!dfs(0,dep))dep++;
	if(dep<5)cout<<dep<<"\n";
	else cout<<"5 or more\n";
}

UVA1343 旋转游戏 ​

题意 ​

旋转游戏

思路 ​

  • 先对每一个操作打表标号
  • 此题的估价函数为8-中间八个数的最大出现次数
cpp
/*
       0     1
	   2     3
 4  5  6  7  8  9 10
      11    12
13 14 15 16 17 18 19
      20    21
	  22    23
*/
int op[8][7]={
	{0,2,6,11,15,20,22},
	{1,3,8,12,17,21,23},
	{10,9,8,7,6,5,4},
	{19,18,17,16,15,14,13},
	{23,21,17,12,8,3,1},
	{22,20,15,11,6,2,0},
	{13,14,15,16,17,18,19},
	{4,5,6,7,8,9,10}
};
int opposite[8]={5,4,7,6,1,0,3,2};
int center[8]={6,7,8,11,12,15,16,17};
int q[30];
int path[110];
int sum[4];
int f(){
	memset(sum,0,sizeof sum);
	for(int i=0;i<8;i++)sum[q[center[i]]]++;
	int s=0;
	for(int i=1;i<=3;i++)s=max(s,sum[i]);
	return 8-s;
}
void operate(int x){
	int tmp=q[op[x][0]];
	for(int i=0;i<6;i++)q[op[x][i]]=q[op[x][i+1]];
	q[op[x][6]]=tmp;
}
bool dfs(int dep,int max_dep,int last){
	if(dep+f()>max_dep)return false;
	if(f()==0)return true;
	for(int i=0;i<8;i++){
		if(opposite[i]==last)continue;
		operate(i);
		path[dep]=i;
		if(dfs(dep+1,max_dep,i))return true;
		operate(opposite[i]);
	}
	return false;
};
void solve(){
	while(cin>>q[0],q[0]){
		for(int i=1;i<24;i++)cin>>q[i];
		int dep=0;
		while(!dfs(0,dep,-1))dep++;
		if(dep==0){
			cout<<"No moves needed\n";
		}
		else{
			for(int i=0;i<dep;i++)cout<<(char)(path[i]+'A');
			cout<<"\n";
		}
		cout<<q[6]<<"\n";
	}
}

BFS ​

双向广搜 ​

A* ​

dijkstra是一种特殊的A*算法，估价距离必须小于等于实际距离

八数码问题 ​

题意 ​

目标状态已知，给定初始状态，求最小步数

思路 ​

  • 把八数码写成序列，左右移动不会改变逆序对，上下移动则会变化两次或不变
  • 因此有解的条件为初始和最终状态奇偶性相同(洛谷的版本保证有解，因此不需要判断)
  • 估价函数为每个数字到最终位置的曼哈顿距离之和+所需的步数
cpp
string start,ed="123804765";
typedef pair<int,string> PIS;
unordered_map<string,int> dis;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int f(string s){
	int ans=0;
	for(int i=0;i<9;i++){
		if(s[i]=='0')continue;
		int x=i/3,y=i%3;
		for(int j=0;j<9;j++){
			if(ed[j]==s[i]){
				int xx=j/3,yy=j%3;
				ans+=abs(xx-x)+abs(yy-y);
				break;
			}
		}
	}
	return ans;
}
void bfs(){
	priority_queue<PIS,vector<PIS>,greater<PIS>> q;
	q.push({f(start),start});
	dis[start]=0;
	while(!q.empty()){
		auto [val,u]=q.top();
		q.pop();
		if(u==ed)break;
		int x,y;
		for(int i=0;i<9;i++){
			if(u[i]=='0'){
				x=i/3,y=i%3;
				break;
			}
		}
		for(int i=0;i<4;i++){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>=0&&tx<3&&ty>=0&&ty<3){
				string v=u;
				swap(v[tx*3+ty],v[x*3+y]);
				if(dis.count(v)==0||dis[v]>dis[u]+1){
					dis[v]=dis[u]+1;
					q.push({dis[v]+f(v),v});
				}
			}
		}
	}
}
void solve(){
	cin>>start;
	bfs();
	cout<<dis[ed]<<"\n";
}

K短路 ​

题意 ​

求起点到终点的第k短路

思路 ​

  • 可以证明，终点弹出第k次则为第k小值
  • 估价函数为到终点的最短路，可以用dijkstra跑出来
  • 时间复杂度O(nklogn)时间复杂度O(nklogn)

Wenwei Lin · 2022 — 2025