游游的排列统计题目描述 游游想知道,有多少个长度为n的排列满足任意两个相邻元素之和都不是素数。你能帮帮她吗?
我们定义,长度为n的排列值一个长度为n的数组,其中1到n每个元素恰好出现了一次。
输入描述:12一个正整数n。2≤n≤10
输出描述:1满足条件的排列数量。
示例1
输入15
输出14
说明12345共有以下 4 种合法排列:[1,3,5,4,2][3,1,5,4,2][2,4,5,1,3][2,4,5,3,1]
链接:https://ac.nowcoder.com/acm/contest/68346/B来源:牛客网
很小,,计算量最多为 ,况且其中有回溯现象,所以计算量大约不超过 。
代码12345678910111213141516171819202122232425262728293031#include <bits/stdc++.h>#define int long longusing namespace std;int n, ans, a[1001], d[1001];bool check ...
题目描述游游拿到了一个正整数x,她希望把这个整数的前k位进行翻转。你能帮帮她吗?
输入描述:123两个正整数x和k,用空格隔开。1≤x≤1e9;kkk保证不超过xxx的位数。
输出描述:1翻转后的正整数。请注意不要带前导零。
输入1123 2
输出1213
说明1将前两位反转后,12变成了21。正整数变成了213。
输入180407 4
输出14087
说明1将前4位翻转,变成0408,连起来后去除前导零为4087。
链接:https://ac.nowcoder.com/acm/contest/68346/A来源:牛客网
代码12345678910111213141516171819#include<iostream>#include<bits/stdc++.h>using namespace std;int main(){ int ans=0,n=0; string s; cin>>s>>n; s=' ...
最长连续不重复子数列题目描述给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式第一行包含整数 n。
第二行包含 n个整数(均在 0∼1050∼105 范围内),表示整数序列。
输出格式共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围1≤n≤1e5
输入样例:1251 2 2 3 5
输出样例:13
代码12345678910111213141516171819202122232425262728#include<iostream>using namespace std;const int N=100010;int n;int a[N],s[N]; int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; int res=0; for(int i=0,j=0;i<n;i++){ s[a[i]]++; while (s[a[i]]>1) { s[a[i]]--; j++; ...
题目给定一个按照升序排列的长度为 n的整数数组,以及 q个查询。
对于每个查询,返回一个元素 k的起始位置和终止位置(位置从 0开始计数)。
如果数组中不存在该元素,则返回 -1 -1。
输入格式第一行包含整数 n和 q,表示数组长度和询问个数。
第二行包含 n个整数(均在 1∼10000范围内),表示完整数组。
接下来 q行,每行包含一个整数 k,表示一个询问元素。
输出格式共 q行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1。
数据范围1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例:123456 31 2 2 3 3 4345
输出样例:1233 45 5-1 -1
模板1234567891011121314151617181920212223//二分法的两个不同模板 bool check(int x){.....}//检查是否满足某种性质 //区间[l,r]被划分为[l,mid]和[mid+1,r]时使用 int bsearch_1(int l,int r){ whil ...
核心代码解析1.函数定义:void quick_sort(int q[], int l, int r) q 是要进行排序的数组。 l 和 r 分别是要排序的数组的起始和结束索引。 函数没有返回值,但会直接修改传入的数组。2.如果 l 大于等于 r ,则直接返回,因为这意味着数组已经被排序了或者只包含一个元素。
3.选择数组的第一个元素 x=q[l] 作为基准元素。
4.使用两个指针 i 和 j 来搜索应该放在基准元素左侧和右侧的元素。开始时,i 指向 l 的前一个元素,j 指向 i 的下一个元素。
5.使用两个 while 循环来找到应该放在基准元素左侧和右侧的元素。 do i++; while(q[i]<x);:找到一个大于等于基准元素的元素。 do j++; while(q[j]>x);:找到一个小于等于基准元素的元素。6.如果 i 小于 j ,则交换 q[i] 和 q[j] 。这样可以确保所有大于等于基准元素的元素都在其左侧,所有小于等于基准元素的元素都在其右侧。
7.对基准元素的左侧和右侧的子数组递归地调用快速排序。
8.最 ...
题目描述猫猫计划和咪咪来一场浪漫的约会,通过投硬币的游戏来为自己赚取金钱。猫猫会掷硬币N次。 他还有一个计数器,最初显示:0.根据第 i 次抛硬币的结果,会发生以下情况:
如果硬币正面向上:猫猫计数器的价值+1,并接收Xi元。
如果硬币反面向上:他将计数器的价值重置为0,而收不到钱。此外,猫猫还有M种连胜奖金。第 i 种连胜奖金奖励 Yi 元当每次计数器显示 Ci 时。你的任务是找到猫猫可以收到的最大金额,让猫猫可以和心动的咪咪约会。
输入描述N MX1 X2 … XNC1 Y1C2 Y2...CM YM
输出描述打印猫猫收到的最大的金额。
用例输入 1123456 32 7 1 8 2 82 103 15 5
用例输出 1148
提示1≤M≤N≤50001≤Xi≤1091≤Ci≤N1≤Yi≤109C1,C2,C3,都是不同的所有的输入都是整数
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<iostream>#incl ...
题目描述有 N件物品和一个容量是 V的背包。每件物品只能使用一次。第 i件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。
输入格式第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N行,每行两个整数 vi,wi,用空格隔开,分别表示第 i件物品的体积和价值。
输出格式输出一个整数,表示最大价值。
数据范围0<N,V≤10000<vi,wi≤1000
输入样例4 51 22 43 44 5
输出样例:8
思路f[i][j] 表示只看前i个物品,总体积是j的情况下,总价值最大是多少
result=max{f[n][0~v]}
f[i][j]1.不选第i个物品,f[i][j]=f[i-1][j]; 2.选第i个物品,f[i][j]=f[i-1][j-v[i]]+w[i];
f[i][j]=max{1.2.} f[0][0]=0;
基本代码12345678910111213141516171819202122232425262 ...
题目农民约翰的 N头奶牛(编号为 1..N)计划逃跑并加入马戏团,为此它们决定练习表演杂技。奶牛们不是非常有创意,只提出了一个杂技表演:叠罗汉,表演时,奶牛们站在彼此的身上,形成一个高高的垂直堆叠。奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。这 N头奶牛中的每一头都有着自己的重量 Wi以及自己的强壮程度 Si。一头牛支撑不住的可能性取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值,现在称该数值为风险值,风险值越大,这只牛撑不住的可能性越高。您的任务是确定奶牛的排序,使得所有奶牛的风险值中的最大值尽可能的小。
输入格式第一行输入整数 N,表示奶牛数量。接下来 N行,每行输入两个整数,表示牛的重量和强壮程度,第 i行表示第 i头牛的重量 Wi以及它的强壮程度 Si。
输出格式输出一个整数,表示最大风险值的最小可能值。
数据范围1≤N≤50000,1≤Wi≤10,000,1≤Si≤1,000,000,000
输入样例:1234310 32 53 3
输出样例:12
思路我不会
代码123456789101112131415161718192021222324252 ...
题目在一条数轴上有 N家商店,它们的坐标分别为 A1∼AN。现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
输入格式第一行输入整数 N。第二行 N个整数 A1∼AN。
输出格式输出一个整数,表示距离之和的最小值。
数据范围1≤N≤1000000≤Ai≤40000
输入样例:46 2 9 1
输出样例:12
思路仓库的选址一定是这些数的中位数
代码12345678910111213141516171819202122232425262728#include<iostream>#include<bits/stdc++.h>using namespace std;const int N=100010;//定义n家商店 int n;//定义n家商店的坐标 int a[N];int main(){ //输入商家的总数 scanf("%d",&n); //循环输入商家的坐标 for(int i=0;i<n;i++) scanf(&q ...