博客详情 - BCOI

gf24240 的博客
《梦溪笔谈·C++》卷十七：内阁会议
gf24240 LV 10 @ 2025-5-11 12:50:36

背景

D老师让我们做的

题目

Description

内阁大臣非常沮丧，他收到了安全部长的消息：他们都需要改变办公室的四位房间号码。

安全部长：经常换换房间号码是出于安全方面的考虑，可以让敌人陷入迷惑。

内阁大臣：但是我选择1033作为我的房间号是出于我个人的偏爱。我可是内阁大臣。

安全部长：你不就是喜欢素数吗？我们给你安排了8179 这个号码，你只需要贴四个新数字覆盖住以前的四个老数字就可以了。

内阁大臣：不行，没有那么容易。当我把 1033的 1用8 盖住的时候，8033可不是个素数！

安全部长：我知道，你不能允许你的门上出现非素数。

内阁大臣：正确！所以我必须找到一个方法从1033 修改到8179，使得过程中门上出现的永远是素数，而且每次只能够修改当前数字的一位。

这个时候，在旁边偷听的财政大臣忍不住来插嘴。

财政大臣：千万不要为了这个事情增加不必要的开支！我知道换一个数字就是要花一磅！

内阁大臣：那我需要一个懂计算机的人来帮我规划一下。

信息大臣：我能够帮助你！

信息大臣现在把这个任务就交给你了。你要从一个四位数的素数出发，每次修改其中的一位，并且要保证修改的结果还是一个素数，还不能出现前导零。你要找到一个修改次数最少的方案，得到我们所需要的素数。

关于 1033 怎么变到 8179，这里是一个最短的方策： 1033 1733 3733 3739 3779 8779 8179 修改了 6次，所以要花6 磅。

Format

Input

第一行给出一个正整数：测试用例的数目（最多100）。每个测试用例一行，两个用空格分开的数字，这两个数字都是4位素数（不以0作为首位）。

Output

对于每个测试用例，输出一行，或者是最小花费的数目，或者输出Impossible。

Samples

Sample Input 1

Sample Output 1

6
7
0

Limitation

1s, 1024KiB for each test case.

题解

~~（以下C++代码均用memset函数填充数组，并不是不想打for循环，只是memset更快）~~

DFS+记忆化+普通求素数，超时

#include <cstring>
#include <iostream>
using namespace std;
int n, a, b, ans = 0xfffffff, cnt, f[10005];
bool vis[10005];
bool isp(int n)
{
	if (n < 2)return 0;
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0)return 0;
	return 1;
}
void dfs(int k)
{
	if (k == b)
	{
  		ans = min(ans, cnt);
		return ;
	}
	if (f[k] <= cnt)return ;
	f[k] = cnt;
	int one = k / 1000, two = k / 100 % 10, thr = k / 10 % 10, fou = k % 10;
	cnt++;
	for (int i = 1; i <= 9; i++)
	{
		if (i == one)continue;
		int nk = i * 1000 + two * 100 + thr * 10 + fou;
		if (isp(nk) && !vis[nk])
		{
			vis[nk] = 1;
			dfs(nk);
			vis[nk] = 0;
		}
	}
	for (int i = 0; i <= 9; i++)
	{
		if (i == two)continue;
		int nk = one * 1000 + i * 100 + thr * 10 + fou;
		if (isp(nk) && !vis[nk])
		{
			vis[nk] = 1;
			dfs(nk);
			vis[nk] = 0;
		}
	}
	for (int i = 0; i <= 9; i++)
	{
		if (i == thr)continue;
		int nk = one * 1000 + two * 100 + i * 10 + fou;
		if (isp(nk) && !vis[nk])
		{
			vis[nk] = 1;
			dfs(nk);
			vis[nk] = 0;
		}
	}
	for (int i = 0; i <= 9; i++)
	{
		if (i == fou)continue;
		int nk = one * 1000 + two * 100 + thr * 10 + i;
		if (isp(nk) && !vis[nk])
		{
			vis[nk] = 1;
			dfs(nk);
			vis[nk] = 0;
		}
	}
	cnt--;
}
int main()
{
	cin >> n;
	while (n--)
	{
		for (int i = 1; i <= 10004; i++)f[i] = 0xfffffff;
 		cin >> a >> b;
		dfs(a);
		if (ans != 0xfffffff)cout << ans << "\n";
		else cout << "Impossible\n";
	}
	return 0;
}

DFS+输入输出优化+强力剪枝+埃氏筛求素数，AC（2340ms）

#include <cstring>
#include <iostream>
using namespace std;
struct stu{int num, step;};
int n, a, b, ans, cnt, f[10005];
bool isp[10005], vis[10005];
void makep()
{
    memset(isp, 1, sizeof(isp));
    isp[0] = isp[1] = 0;
    for (int i = 2; i <= 9999; i++)
	{
        if (isp[i])
		{
            for (int j = i * i; j <= 9999; j += i)
			{
                isp[j] = false;
            }
        }
    }
}
void dfs(int k)
{
	if (cnt > ans)return ;
	if (k == b)
	{
  		ans = min(ans, cnt);
		return ;
	}
	if (f[k] <= cnt)return ;
	f[k] = cnt;
	int one = k / 1000, two = k / 100 % 10, thr = k / 10 % 10, fou = k % 10;
	cnt++;
	for (int i = 1; i <= 9; i++)
	{
		if (i == one)continue;
		int nk = i * 1000 + two * 100 + thr * 10 + fou;
		if (isp[nk])
		{
			dfs(nk);
		}
	}
	for (int i = 0; i <= 9; i++)
	{
		if (i == two)continue;
		int nk = one * 1000 + i * 100 + thr * 10 + fou;
		if (isp[nk])
		{
			vis[nk] = 1;
			dfs(nk);
			vis[nk] = 0;
		}
	}
	for (int i = 0; i <= 9; i++)
	{
		if (i == thr)continue;
		int nk = one * 1000 + two * 100 + i * 10 + fou;
		if (isp[nk])
		{
			dfs(nk);
		}
	}
	for (int i = 0; i <= 9; i++)
	{
		if (i == fou)continue;
		int nk = one * 1000 + two * 100 + thr * 10 + i;
		if (isp[nk])
		{
			dfs(nk);
		}
	}
	cnt--;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	makep();
	cin >> n;
	while (n--)
	{
		cnt = 0, ans = 0x3f;
		memset(f, 0x3f, sizeof(f));
 		cin >> a >> b;
		dfs(a);
		if (ans != -1)cout << ans << "\n";
		else cout << "Impossible\n";
	}
	return 0;
}

无优化的BFS+普通求素数，超时

#include <queue>
#include <iostream>
using namespace std;
struct stu{int num, step;};
int n, a, b, ans;
bool isp(int n)
{
	if (n < 2)return 0;
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0)return 0;
	return 1;
}
int bfs()
{
	queue <stu> q;
	q.push(stu{a, 0});
	while (!q.empty())
	{
		stu f = q.front();
		q.pop();
		if (f.num == b)
		{
			return f.step;
		}
		int k = f.num;
		int one = k / 1000, two = k / 100 % 10, thr = k / 10 % 10, fou = k % 10;
		for (int i = 1; i <= 9; i++)
		{
			if (i == one)continue;
			int nk = i * 1000 + two * 100 + thr * 10 + fou;
			if (isp(nk))
			{
				q.push(stu{nk, f.step + 1});
			}
		}
		for (int i = 0; i <= 9; i++)
		{
			if (i == two)continue;
			int nk = one * 1000 + i * 100 + thr * 10 + fou;
			if (isp(nk))
			{
				q.push(stu{nk, f.step + 1});
			}
		}
		for (int i = 0; i <= 9; i++)
		{
			if (i == thr)continue;
			int nk = one * 1000 + two * 100 + i * 10 + fou;
			if (isp(nk))
			{
				q.push(stu{nk, f.step + 1});
			}
		}
		for (int i = 0; i <= 9; i++)
		{
			if (i == fou)continue;
			int nk = one * 1000 + two * 100 + thr * 10 + i;
			if (isp(nk))
			{
				q.push(stu{nk, f.step + 1});
			}
		}
	}
	return -1;
}
int main()
{
	cin >> n;
	while (n--)
	{
 		cin >> a >> b;
		ans = bfs();
		if (ans != -1)cout << ans << "\n";
		else cout << "Impossible\n";
	}
	return 0;
}

优化BFS+普通求素数，AC（162ms）

#include <queue>
#include <cstring>//memset的头文件
#include <iostream>
using namespace std;
struct stu{int num, step;};
int n, a, b, ans, df[10005];
bool isp(int n)
{
	if (n < 2)return 0;
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0)return 0;
	return 1;
}
int bfs()
{
	queue <stu> q;
	q.push(stu{a, 0});
	while (!q.empty())
	{
		stu f = q.front();
		q.pop();
		if (f.num == b) return f.step;
		int k = f.num;
		int wnum[7] = {0, k / 1000, k / 100 % 10, k / 10 % 10, k % 10};
		for (int i = 1; i <= 4; i++)
		{
			int inum = wnum[i];
			for (int j = 0; j <= 9; j++)
			{
				if (i == 1 && j == 0)continue;
				if (j == inum)continue;

				wnum[i] = j;
				int nk = wnum[1] * 1000 + wnum[2] * 100 + wnum[3] * 10 + wnum[4];
				if (isp(nk) && df[nk] > f.step + 1)
				{
					df[nk] = f.step + 1;
					q.push(stu{nk, f.step + 1});
					if (nk == b) return df[nk];
				}
			}
			wnum[i] = inum;
		}
	}
	return -1;
}
int main()
{
	cin >> n;
	while (n--)
	{
		memset(df, 0x3f, sizeof(df));
 		cin >> a >> b;
		ans = bfs();
		if (ans != -1)cout << ans << "\n";
		else cout << "Impossible\n";
	}
	return 0;
}

普通BSFS+埃氏筛求素数，AC（680ms）

#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
struct stu{int num, step;};
int n, a, b, ans;
bool isp[10005];
void makep()
{
    memset(isp, 1, sizeof(isp));
    isp[0] = isp[1] = 0;
    for (int i = 2; i <= 9999; i++)
	{
        if (isp[i])
		{
            for (int j = i * i; j <= 9999; j += i)
			{
                isp[j] = false;
            }
        }
    }
}
int bfs()
{
	queue <stu> q;
	q.push(stu{a, 0});
	while (!q.empty())
	{
		stu f = q.front();
		q.pop();
		if (f.num == b)
		{
			return f.step;
		}
		int k = f.num;
		int one = k / 1000, two = k / 100 % 10, thr = k / 10 % 10, fou = k % 10;
		for (int i = 1; i <= 9; i++)
		{
			if (i == one)continue;
			int nk = i * 1000 + two * 100 + thr * 10 + fou;
			if (isp[nk])
			{
				q.push(stu{nk, f.step + 1});
			}
		}
		for (int i = 0; i <= 9; i++)
		{
			if (i == two)continue;
			int nk = one * 1000 + i * 100 + thr * 10 + fou;
			if (isp[nk])
			{
				q.push(stu{nk, f.step + 1});
			}
		}
		for (int i = 0; i <= 9; i++)
		{
			if (i == thr)continue;
			int nk = one * 1000 + two * 100 + i * 10 + fou;
			if (isp[nk])
			{
				q.push(stu{nk, f.step + 1});
			}
		}
		for (int i = 0; i <= 9; i++)
		{
			if (i == fou)continue;
			int nk = one * 1000 + two * 100 + thr * 10 + i;
			if (isp[nk])
			{
				q.push(stu{nk, f.step + 1});
			}
		}
	}
	return -1;
}
int main()
{
	makep();
	cin >> n;
	while (n--)
	{
 		cin >> a >> b;
		ans = bfs();
		if (ans != -1)cout << ans << "\n";
		else cout << "Impossible\n";
	}
	return 0;
}

优化BFS+埃氏筛求素数，AC（27ms）

#include <queue>
#include <cstring>//memset的头文件
#include <iostream>
using namespace std;
struct stu{int num, step;};
int n, a, b, ans, df[10005];
bool isp[10005];
// 埃拉托斯特尼筛法预处理质数
void makep()
{
    memset(isp, 1, sizeof(isp));
    isp[0] = isp[1] = 0;
    for (int i = 2; i <= 9999; i++)
	{
        if (isp[i])
		{
            for (int j = i * i; j <= 9999; j += i)
			{
                isp[j] = false;
            }
        }
    }
}
int bfs()
{
	queue <stu> q;
	q.push(stu{a, 0});
	while (!q.empty())
	{
		stu f = q.front();
		q.pop();
		if (f.num == b) return f.step;
		int k = f.num;
		int wnum[7] = {0, k / 1000, k / 100 % 10, k / 10 % 10, k % 10};
		for (int i = 1; i <= 4; i++)
		{
			int inum = wnum[i];
			for (int j = 0; j <= 9; j++)
			{
				if (i == 1 && j == 0)continue;
				if (j == inum)continue;
				
				wnum[i] = j;
				int nk = wnum[1] * 1000 + wnum[2] * 100 + wnum[3] * 10 + wnum[4];
				if (isp[nk] && df[nk] > f.step + 1)
				{
					df[nk] = f.step + 1;
					q.push(stu{nk, f.step + 1});
					if (nk == b) return df[nk];
				}
			}
			wnum[i] = inum;
		}
	}
	return -1;
}
int main()
{
	makep();
	cin >> n;
	while (n--)
	{
		memset(df, 0x3f, sizeof(df));
 		cin >> a >> b;
		ans = bfs();
		if (ans != -1)cout << ans << "\n";
		else cout << "Impossible\n";
	}
	return 0;
}

简单总结：

搜索算法	普通求素数	埃氏筛求素数
DFS（优化）	TLE	AC（输入输出优化，2340ms）
BFS（普通）	TLE	AC（680ms）
BFS（优化）	AC（162ms）	AC（27ms）

可见埃氏筛的重要性

python版BFS优化+埃氏筛求素数，AC（2395ms）

import queue
class stu:
    def __init__(self, num = 0, step = 0):
        self.num = num
        self.step = step
n = a = b = ans = 0
df = isp = [0] * 10005
def makep():
    global isp
    isp = [1] * 10005
    isp[0] = isp[1] = 0
    for i in range(2, 10000):
        if (isp[i] == 1):
            for j in range(i * i, 10000, i):
                isp[j] = False

def bfs():
    global a, b, df, isp
    q = queue.Queue(maxsize = 100005)
    q.put(stu(a, 0))
    while (q.qsize() != 0):
        f = q.get()
        if (f.num == b):
            return f.step
        k = f.num
        wnum = [0, k // 1000, k // 100 % 10, k // 10 % 10, k % 10]
        for i in range(1, 5):
            inum = wnum[i]
            for j in range(10):
                if (i == 1 and j == 0):
                    continue
                if (j == inum):
                    continue   
                wnum[i] = j
                nk = int(wnum[1] * 1000 + wnum[2] * 100 + wnum[3] * 10 + wnum[4])
                if (isp[nk] == 1 and df[nk] > f.step + 1):
                    df[nk] = f.step + 1
                    q.put(stu(nk, f.step + 1))
                    if (nk == b):
                        return df[nk]
            wnum[i] = inum
    return -1
def main():
    global a, b, df
    makep()
    n = int(input())
    for i in range(n):
        df = [0x3f3f3f3f] * 10005
        a, b = map(int, input().split())
        ans = bfs()
        if (ans != -1):
            print(ans)
        elif (ans == -1):
            print("Impossible")

main()

python的BFS甚至比C++的DFS慢很多，可见C++这种编译型语言的重要性

《梦溪笔谈·C++》卷十七：内阁会议

背景

题目

Description

Format

Input

Output

Samples

Sample Input 1

Sample Output 1

Limitation

题解

状态

开发

支持

《梦溪笔谈·C++》卷十七：内阁会议

背景

题目

Description

Format

Input

Output

Samples

Sample Input 1

Sample Output 1

Limitation

题解

状态

开发

支持

还没有账户？

登录