选数

题目

链接：[NOIP2002]选数 - 题库 - 计蒜客 (jisuanke.com)

样例输入

4 3
3 7 12 19

样例输出

1

数据范围

解题思路

枚举子集问题, 先来回顾一下如何去枚举数组中的数。

如果用循环来枚举
枚举一遍：一层for循环
固定一个数后枚举其他数：两层for循环
固定两个数后枚举其他数：三层for循环
显然固定k个数得有k+1层循环, 该题没法用这种方法解决。

如果用DFS来枚举
枚举一遍：

void dfs(int i)
{
	if(i == n) return;
	cout << a[i] << endl;
	dfs(i +1);
}

固定一个数后枚举其他数：

int res[2];
void dfs(int i, int u)
{
	if(u == 2) 
	{
		cout << res[0] << " " << res[1] << endl;
		return;
	}
	for(i; i < n; i++)
	{
		res[u] = i;
		dfs(i + 1, u + 1);
	}
}

固定两个数后枚举其他数：

int res[3];
void dfs(int i, int u)
{
	if(u == 3) 
	{
		cout << res[0] << " " << res[1] << " " << res[2] << endl;
		return;
	}
	for(i; i < n; i++)
	{
		res[u] = i;
		dfs(i + 1, u + 1);
	}
}

显然固定k个数只需要改变 u == k 即可

回到该题, 已经确定了枚举方法, 接下来需要做的就是从枚举的子集中筛选出符合要求的答案

// 判断是否为质数
bool check(int x)
{   // sqrt(x*1.0) 相比 i * i <= x 更安全一些
	// 可参考我之前写的素数专题
    for (int i = 2; i <= sqrt(x * 1.0); i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

我们也不必用数组存下子集, 题目只需要一个总和即可, 故可以直接在 dfs 参数上加一个 sum

dfs(int i, int u, int sum)
{
	....
	dfs(i + 1, u + 1, sum + a[i]);
	....
}

为啥不这么写呢：

sum += a[i];
dfs(i + 1, u + 1);
sum -= a[i];

因为缩进去效果一样还省事还清晰。

最终代码：

//------------------------------//
//          Made by Aze         //
//------------------------------//
/*
 *	problem: https://nanti.jisuanke.com/t/T2116
 *	date: 6/22/2022
 *
 */

#include <iomanip>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
//------- Coding Area ---------//
const int N = 30;
int a[N];
bool st[N];
int res;
int n, k;
bool check(int x)
{
    for (int i = 2; i <= sqrt(x * 1.0); i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

void dfs(int i, int u, int sum)
{
    if (u == k)
    {
        if (check(sum))
        {
            res++;
        }
        return;
    }

    for (i; i < n; i++)
    {
            dfs(i + 1, u + 1, sum + a[i]);
    }
}

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n;i ++)
        scanf("%d", &a[i]);
    dfs(0, 0, 0);
    cout << res << endl;
    return 0;
}

Prime Path

题目

链接：
Prime Path - POJ 3126 - Virtual Judge (csgrandeur.cn)

输入样例

3
1033 8179
1373 8017
1033 1033

输出样例

6
7
0

数据范围
T <= 100
a,b 都是四位数且无前导0（不会有0100这样的数）

解题思路

上一题是枚举数组, 这题便是枚举数字了

且要求是求出最短路径, 搜索算法中能求出最短路径的当然是我BFS广度优先搜索。

建议还是看英文题面, 字多显得更详细。

大意就是从质数a每次只变一位变成质数b, 求最短变化次数, 且每次变化后的数必须也是质数。

理解好题意之后马上就能发现, 该题需要很多次判断质数的操作, 不能沿用上一题的简单判断。
这里我使用欧拉筛来实现素数判断：
对这方面不太熟悉的去做下素数专题（二次安利）

const int N = 1e5 + 10; // 10010
int primes[N];
bool st[N], isprime[N];
void getprimes()
{
    int cnt = 0;
    for(int i = 2; i <= N; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            isprime[i] = true;
        }
        for (int j = 0; primes[j] * i <= N; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}

素数的问题解决了, 那怎么去枚举一个数到另一个数的所有路径呢？
参考图论的一些思想

先看怎么找到一个数能走的所有路径：
根据题意, 一次变换一位, 那我们就可以枚举每位上的变换
将个位从0变到9得到的10个数便是能变化到的10个数
同理, 十位从0变到9得到的10个数也是能走到的数
百位,千位都是这样, 且每一条路径都有可能走。

对于一串数字中每位的处理, 通常是用字符串来解决
也可以将每一位用十进制进制表示
比如 4396 就表示成 4*1000 + 3*100 + 9 * 10 + 6
只存入每一位上的数值, 转化成完整数时乘上进制即可：

int base[] = {1, 10, 100, 1000}; // 个十百千
int d[] = {个位, 十位, 百位, 千位};
最终数： 
for(int i = 0; i < 4; i++)
	res += d[i] * base[i];

这么表示有啥好处呢？
在枚举时很方便, 例如枚举十位时：

// t 是完整数, d[i] 是其第i位上的数, 这里就是十位
// 减去之后得到的便是 xx0x
int temp = t - d[i] * base[i]
for(int j = 0; j < 10; j++)
{// 这时候再加上去, 得到的num就是枚举出来的数
	int num = temp + d[j] * base[i];
	...判断...
}

百位千位都类似, 故枚举数t的所有能走路径的代码为：

int base[] = {1, 10, 100, 1000};
// 取某个数的个十百千位, 不加括号也可以, 这里为了方便看
int d[] = {t % 10, (t/10) % 10, (t/100) % 10, t/1000};
for(int i = 0; i < 4; i++)
{
	int temp = t - d[i] * base[i];
	for(int j = 0; j < 10; j++)
	{ // 不能出现 0xxx 的数
		if(i == 3 && j == 0) continue;
		int num = temp + d[j] * base[i];
		...
	}
}

枚举完了 num, 如何判断该数是否有效呢？
判断一下是否为质数isprime[num] == true
再判断一下之前是否走过dist[num] != -1

当BFS的队列头是最终结果时就退出搜索, 返回结果。

完整代码

//------------------------------//
//          Made by Aze         //
//------------------------------//
/* problem:https://vjudge.csgrandeur.cn/problem/POJ-3126#author=0
 *	date: 6/22/2022 8:26
 */
#include <iomanip>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;

int readInt()
{
	int t;
	scanf("%d", &t);
	return t;
}

//------- Coding Area ---------//

const int N = 1e5 + 10;
int dist[N];
int primes[N];
bool st[N], isprime[N];

void getprimes()
{
	int cnt = 0;
	for(int i = 2; i <= N; i++)
	{
		if (!st[i])
		{
			primes[cnt++] = i;
			isprime[i] = true;
		}
		for (int j = 0; primes[j] * i <= N; j++)
		{
			st[primes[j] * i] = true;
			if (i % primes[j] == 0)
				break;
		}
	}
}

int bfs(int a, int b)
{
	memset(dist, -1, sizeof dist);
	queue<int> q;
	q.push(a);
	dist[a] = 0;
	int base[] = {1, 10, 100, 1000};
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		if (t == b)
			return dist[t];
		int d[] = {t % 10, t / 10 % 10, t / 100 % 10, t / 1000};
		for(int i = 0; i < 4; i++)
		{
			int temp = t - d[i] * base[i];
			for(int j = 0; j < 10; j++)
			{
				if (i == 3 && j == 0)
					continue;
				int num = temp + j * base[i];
				if (isprime[num] && dist[num] == -1)
				{
					dist[num] = dist[t] + 1;
					q.push(num);
				}
			}
		}
	}
	return -1;
}

int main()
{
	getprimes();
	int n;
	scanf("%d", &n);
	while (n--)
	{
		int res = bfs(readInt(), readInt());
		if (res == -1)
			printf("impossible\n");
		else
			printf("%d\n", res);
	}
	return 0;
}

八皇后

建议看acwing y总的讲解, 视频详细很多。
在 搜索与图论（一）里面, 没买课的可私聊。