第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-533 素数环
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-533 素数环
目录
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-533 素数环
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍,让大家方便去搜索,所有题目都会有几种语言的写法,帮助大家提供一个思路,当然,思路只是思路,千万别只看着答案就认为会了啊,这个方法基本上很难让你成长,成长是在思考的过程中找寻到自己的那个解题思路,并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练,如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢,这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来,所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式,说着听绕口,但是就是靠量来堆叠思维方式,刷题方案自主定义的话肯定就是从非常简单的开始,稍微对数据结构有一定的理解,暴力、二分法等等,一步步的成长,数据结构很多,一般也就几种啊,线性表、树、图、再就是其它了。顺序表与链表也就是线性表,当然栈,队列还有串都是属于线性表的,这个我就不在这里一一细分了,相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的,例如三分枚举、离散化,图,复杂数据结构还有统计都是不考的,我们找简单题刷个一两百,然后再进行中等题目的训练,当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠,慢慢的就会掌握各种规律,有了规律就能大胆的长一些难度比较高的题目了,再次说明,刷题一定要循序渐进,千万别想着直接就能解决难题,那只是对自己进行劝退处理。加油,平常心,一步步前进。
关于数学的疑问
蓝桥杯中涉及到的数学说多不多,说少也不少,这里罗列了一下能用到的,其中红色的是【大学C组】会使用到的
1、简单数学(基础运算)
2、位运算
3、线性代数
4、离散数学(组合数学)
5、初等数论(整数的性质)
6、概率论
7、几何
虽然看到了线性代数、离散数学、初等数论,但是对于C组来说不会考的太复杂,会基础就好。
算法训练 素数环
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
问题描述
有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻的两个数(包括首和尾)的和都为素数,称为素数环。为了简便起见,我们规定每个素数环都从1开始。例如,6的一个素数环:
1 4 3 2 5 6
请编写一个程序,给定一个输入n(0<n<20) ,如果存在满足要求的素数环,从小到大输出。否则,输出No Answer。
输入格式
输入整数n,0<n<20。
输出格式
如果存在满足要求的素数环,从小到大输出。否则,输出No Answer。
样例输入
8
样例输出
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
题解:
C语言
#include <stdio.h>
#define N 22
int vis[N];
int c[N]; //记录素数环
int n;
int ans=0; //统计素数环的个数
int is_prime(int x){
int i;
if(x==1) return 0;
for(i=2;i*i<=x;i++)
if(x%i==0) return 0;
return 1;
}
void dfs(int cur){
int i;
if(cur==n && is_prime(c[0]+c[n-1]) ){
ans++; //统计素数环的个数
for(i=0;i<n;i++) printf("%d ",c[i]); //输出一个全排列
printf("\n");
return;
}
for(i=2;i<=n;i++)
if(!vis[i] && is_prime(i+c[cur-1]) ){ //is_prime的作用是剪枝
c[cur]=i;
vis[i]=1;//打上使用过的标记
dfs(cur+1);
vis[i]=0;//消除标志,回溯的本质
}
}
int main(){
scanf("%d",&n);
c[0]=1; //第一个数固定为1
if(n&1)
printf("No Answer\n"); //奇数
else{
dfs(1); //特判n=1的情况
if(ans==0) printf("No Answer\n");
}
return 0;
}
C++语言
#include<bits/stdc++.h>
using namespace std;
const int N=22;
int vis[N];
int c[N]; //记录素数环
int n;
int ans=0; //统计素数环的个数
int is_prime(int x){
if(x==1) return 0;
for(int i=2;i*i<=x;i++)
if(x%i==0) return 0;
return 1;
}
void dfs(int cur){
if(cur==n && is_prime(c[0]+c[n-1]) ){
ans++; //统计素数环的个数
for(int i=0;i<n;i++) cout<<c[i]<<" "; //输出一个全排列
cout<<endl;
return;
}
for(int i=2;i<=n;i++)
if(!vis[i] && is_prime(i+c[cur-1]) ){ //is_prime的作用是剪枝
c[cur]=i;
vis[i]=1;//打上使用过的标记
dfs(cur+1);
vis[i]=0;//消除标志,回溯的本质
}
}
int main(){
cin>>n;
c[0]=1; //第一个数固定为1
if(n&1)
cout << "No Answer"<<endl; //奇数
else{
dfs(1); //特判n=1的情况
if(ans==0) cout << "No Answer"<<endl;
}
return 0;
}
Java语言
在扫描输入内容上会有不同的方法,但是与Scanner的用法是相同的。只是相对的录入速度快于Scanner这样在整体运算的过程中可以适当节约时间。
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static void f4(int[] arr, int n) {// 已用过的数字和现在的位置
if (n == arr.length && check1(arr, 1, arr[n - 1])) {// 再check1判断是否成环
for (int i = 0; i < n - 1; i++) {
sb.append(arr[i] + " ");
}
sb.append(arr[n - 1] + "\n");
return;
}
for (int i = 2; i <= arr.length; i++) {
if (check1(arr, n, i)) {
arr[n] = i;
f4(arr, n + 1);
}
}
}
private static boolean check1(int[] arr, int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return false;
}
}
if (!isPrime(arr[n - 1] + x)) {
return false;
}
return true;
}
private static boolean isPrime(int i) {
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = new int[sc.nextInt()];
arr[0] = 1;
if (arr.length == 17 || arr.length == 19) {// 16和18则不可举枚,因为内容太多
System.out.println("No Answer");// 暴力把结果举枚,尽量获得更多的用例分
return;
}
f4(arr, 1);
if (sb.length() == 0) {
System.out.println("No Answer");
} else {
System.out.println(sb.toString());
}
sc.close();
}
}
Python语言
相对简洁,但是需要对Python的一些语法很了解,特别是列表推导式的熟悉。
from math import *
def is_prime(x):
if x==1: return False
m = int(isqrt(x))+1
for i in range(2, m):
if x%i ==0: return False
return True
def dfs(cur):
global n,ans
if cur==n and is_prime(c[0]+c[n-1]):
ans += 1
for i in range(0,n):
print(c[i],end=' ')
print()
for i in range(2,n+1):
if vis[i] == 0 and is_prime(c[cur-1]+i) :
c[cur] = i
vis[i] = 1
dfs(cur+1)
vis[i] = 0
n = int(input())
ans = 0
vis = [0 for i in range(n+1)]
c = [0 for i in range(n+1)]
c[0] = 1
if n&1==1: print("No Answer")
else:
dfs(1)
if ans==0: print("No Answer")
总结
没有什么不付出就能拿到的结果,我们都是在负重前行,最终结果与自身先天的脑力有一定的关系,但是还是有很大一部分看自己后天的努力,其实从报名到比赛也就5个月左右,真正刷题的事件也就2个月,2个月回忆一下你真正的认真刷过题吗,如果你真的用尽所有的精力去努力了,那么我相信你最终的成绩一定会让你满意的,加油。
第六届——第十三届省赛题解
所有的题目都做了讲解,最难的有配套的视频,视频提供者是【2020级的弓家宜】先生。
第六届——第十二届国赛题解
所有题目均有题解,部分第10题非最优解,至少跑20%数据。
相关文章
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-dp练习2
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-基础练习 特殊的数字
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-95 2的次幂表示
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-201 大等于n的最小完全平方数
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-基础练习 数列特征
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-基础练习 01字串
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-439 算法训练 简单字符变换
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-446 递归输出数字
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-528 最大连续和
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-529 DOTA
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-562 线性运算
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-624 观星
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-655 栈的研究
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-667 多位数连接
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-681 最大公约数和最小公倍数问题
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-709 火星人乘法
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-914 计算器
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-934 序列
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-940 试题3971
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-966 自行车停放
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-969 N车
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-979 移动
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-982 最小距离
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-983 最大获利
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-995 24点
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
- 问题 1471: [蓝桥杯][基础练习VIP]矩形面积交