素数环

　

素数环

素数环NOJ1104

回溯法应用，显然解空间是一个排列集，n最大为16，最大解空间为16！= 2*10^13（阶乘）。用next_permutation生成每排列，然后判断是否为素数环，肯定会超时（大于每秒百万次计算了）。可以用回溯法，适当减枝。参考《算法竞赛入门经典》 by myorange 2017-4-28 19:20:22

#include <iOStream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath> 
using namespace std;
const int maxn = 307;
int n, ary[20];
bool isp[maxn], vis[maxn];
void getPrime(int n) {
	memset(isp, 1, sizeof(isp));
	int m= sqrt(n + 0.5);
	for (int i = 2; i <= m; ++i)
		if(isp[i])
			for(int j = i * i; j <= n; j += i)
				isp[j] = false;
	isp[0] = isp[1] = false;
}
void dfs(int cur) { //回溯法，排列集 
	if (cur == n && isp[ary[0] + ary[n - 1]]) {
		cout << ary[0];
		for (int i= 1; i < n; ++i)
			cout << ' ' << ary[i];
		cout << endl;
	}
	else {
		for (int i = 2; i <= n; ++i)
			if (!vis[i] && isp[i+ary[cur - 1]]) {
				ary[cur] = i;
				vis[i] = true;
				dfs(cur + 1);
				vis[i] = false;
			}
	}
}
int main()
{
	//freopen("data.in", "r", stdin);
	//freopen("data.out", "w", stdout); 
	ios::sync_with_stdio(false);
	getPrime(maxn - 7);
	while(cin >> n) {
		memset(ary, 0, sizeof ary);
		ary[0] = 1;
		memset(vis, false, sizeof vis);
		dfs(1);
	}
	
	return 0;
}

Description

输入正整数n，把整数1，2，3，…，n组成一个环，使得相邻两个整数之和为素数。输出时从整数1开始逆时针排列。同一个环应恰好输出一次。1<n≤16。

Input

输入正整数n，1<n≤16。

Output

输出素数环序列，从整数1开始逆时针排列。

Sample Input

6

Sample Output

1 4 3 2 5 6

1 6 5 2 3 4

Source

刘汝佳《算法竞赛入门经典》

郑大OJ10401物资调度

#include <cstdio> 
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int ary[112], ans;
bool vis[112];
//回溯法，排列树
void dfs(int s, int sum) {
	if (sum == m) {
		ans++;
		return;
	}
	if(sum > m)
		return;
	for (int i = s; i < n; ++i) {
		if (!vis[i] && sum + ary[i] <= m) {
			vis[i] = true;
			dfs(i + 1, sum + ary[i]);
			vis[i] = 0;
		}
	}
}
int main()
{
	int K;
	scanf("%d", &K);
	while(K--) {
		scanf("%d%d", &n, &m);
		for (int i= 0;i < n; ++i)
			scanf("%d", ary + i);
		memset(vis, 0, sizeof(vis));
		ans = 0;
		dfs(0, 0);
		printf("%d\n", ans); 
	}
	
	return 0;
}

10401: A.物资调度

Description

某地区发生了地震，灾区已经非常困难，灾民急需一些帐篷、衣物、食品和血浆等物资。可通往灾区的道路到处都是塌方，70%以上的路面损坏，桥梁全部被毁。国家立即启动应急预案，展开史上最大强度非作战空运行动，准备向灾区空投急需物资。

一方有难，八方支援。现在已知有N个地方分别有A1，A2,….,An个物资可供调配。目前灾区需要物资数量为M。

现在，请你帮忙算一算，总共有多少种物质调度方案。

假设某地方一旦被选择调配，则其物资数全部运走。

Input

第一行： K     表示有多少组测试数据。

接下来对每组测试数据有2行，第1行:  N  M

               第2行：A1  A2 ……  An

2≤K≤8     1<N≤100   1<M≤1000     1≤ Ai≤1000 

所有数据都是正整数。输入数据之间有一个空格。

假设给定的数据至少有一种调度方案。

Output

对于每组测试数据，输出一行：物资调度的总方案数

Sample Input

2

4 4

1 1 2 2

4 61

 1 2 2

Sample Output

31

相关阅读