[综合] 素数筛法 - O( N log ( N ) ) 和 O( N )

注：代码很长，不要害怕，不难的，核心代码只有几行，贴上完整代码是为了大家测试方便。 首先要明白的是素数的倍数一定不是素数。 筛法1 在0-n之间的数字筛法的基本思想： 首先假设0-n全部都是素数 然后从2开始遍历到sqrt(n)， 如果该数是素数，那么在区间[这个数的平方,n]上将是这个数字的倍数...

[综合] 全排列散列 - （康托展开 和 逆康托展开）

注：代码很长，不要害怕，不难的，核心代码只有几行，贴上完整代码是为了大家测试方便。 首先明确我们要求的是什么样的题目。 例如，给定数组a[10]={1,2,3,4,5,6,7,8,9,10}; 我们把排列{1,2,3,4,5,6,7,8,9,10}规定为0 我们把排列{1,2,3,4...

[综合] 蓝桥杯2017【模拟赛3】排列序数（康托展开式）

题目描述： X星系的某次考古活动发现了史前智能痕迹。这是一些用来计数的符号，经过分析它的计数规律如下：（为了表示方便，我们把这些奇怪的符号用a~q代替）abcdefghijklmnopq表示0abcdefghijklmnoqp表示1abcdefghijklmnpoq表示2abcdefghijklmn...

[综合] 洛谷OJ - P1347 排序（拓扑排序）

题目描述： 一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列A,B,C,D表示A<B,B<C,C<D。在这道题中，我们将给你一系列形如A<B的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。 输入输出格式 输入格式： 第一行有...

[综合] 归并排序的实现及利用其求逆序对数

归并排序，顾名思义：递归+合并 合并：是将两个数列合并，如164和253合并，为了方便，我们将其命名为数列1和数列2，合并数列1和数列2， 从两者的最左边的位置开始比较, 1<2，将1放入数列3中备用，数列1的指针后移。 6>2，将2放入数列3中备用，数列2的指针后移。 6>5，将...

[综合] 第八届蓝桥杯【省赛试题10】k倍区间

题目描述 给定一个长度为N的数列，A1,A2,...AN，如果其中一段连续的子序列Ai,Ai+1,...Aj(i<=j)之和是K的倍数，我们就称这个区间[i,j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗？ 输入 输入数据： 第一行包含两个整数N和K。(1<=N,K<...

[综合] NYOJ - 995 - 硬币找零（动态规划-完全背包）

题目描述 在现实生活中，我们经常遇到硬币找零的问题，例如，在发工资时，财务人员就需要计 算最少的找零硬币数，以便他们能从银行拿回最少的硬币数，并保证能用这些硬币发工资。 我们应该注意到，人民币的硬币系统是100，50，20，10，5，2，1，0.5，0.2，0.1，0.05， 0.0...

[综合] NYOJ - 1204 - 魔法少女（动态规划）

题目描述 前些时间虚渊玄的巨献小圆着实火了一把。在黑长直（小炎）往上爬楼去对抗魔女之夜时，她遇到了一个问题想请你帮忙。因为魔女之夜是悬浮在半空的，所以她必须要爬楼，而那座废墟一共有n层，而且每层高度不同，这造成小炎爬每层的时间也不同。不过当然，小炎会时间魔法，可以瞬间飞过一层或者两层[即不耗时]...

[综合] NYOJ - 1070 - 诡异的电梯【Ⅰ】（动态规划）

题目描述 新的宿舍楼有N(1≤N≤100000)层andM(1≤M≤100000)个学生.在新的宿舍楼里,为了节约学生的时间也为了鼓励学生锻炼身体,所以规定该宿舍楼里的电梯在相邻的两层之间是不会连续停下（即，如果在第2层停下就不能在第3层停下。）.所以，如果有学生在相邻的两层之间要停下,则其中的...

[综合] NYOJ - 311 - 完全背包（背包问题）

ProblemDescription 直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满...

[综合] HDU - 1203 - I NEED A OFFER!（01背包）

ProblemDescription Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当...

[综合] memset()初始化为1的那些事

点击查看更详细讲解 问题代码： 1#include<stdio.h> 2#include<string.h> 3intmain(){ 4intarray[5]; 5inta; 6while(~scanf("%d",&a)){ 7memset(array,a,s...

[综合] HDU - 1248 - 寒冰王座（完全背包）

ProblemDescription 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.死亡骑士:"我要买道具!"地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水...

[综合] HDU - 2191 - 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活（多重背包）

ProblemDescription 急！灾区的食物依然短缺！为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。请问：你用有限的资金最多能采购多少公斤粮食呢？后记：人生是一个充满了...

[综合] NUC - 1007 - H.包子铺（二维多重背包）

ProblemDescription 【HuJie】和【Mon-GeeGee】一推开门，又是一片迷雾森林，穿过森林，看到京城城墙，才反应过来，原来刚刚穿过的是镜像森林。从灵隐寺大路走回京城城墙大概需要走半天，镜像森林阻挡住了直行的道路。两人出来了有一会儿了，早饭寺里供给的不多，早就饿了。两人去四...

[综合] 第七届蓝桥杯【国赛试题1】一步之遥

题目描述 从昏迷中醒来，小明发现自己被关在X星球的废矿车里。 矿车停在平直的废弃的轨道上。 他的面前是两个按钮，分别写着“F”和“B”。 小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。 按F，会前进97米。按B会后退127米。 透过昏暗的灯光，小明看到自己前方1米远正好有个监控探头。...

[综合] 第七届蓝桥杯【国赛试题3】棋子换位

题目描述 有n个棋子A，n个棋子B，在棋盘上排成一行。 它们中间隔着一个空位，用“.”表示，比如： AAA.BBB 现在需要所有的A棋子和B棋子交换位置。 移动棋子的规则是： 1.A棋子只能往右边移动，B棋子只能往左边移动。 2.每个棋子可以移动到相邻的空位。 3.每个棋子可以跳过相异的一个...

[综合] 洛谷OJ - P2440 - 木材加工（二分答案）

题目描述 题目描述:木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段木头越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是...

[综合] 洛谷OJ - P1024 - 一元三次方程求解（二分答案）

题目描述 有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后...

[综合] 洛谷OJ - P2759 - 奇怪的函数（二分答案）

题目描述 使得x^x达到或超过n位数字的最小正整数x是多少？ 输入 一个正整数n 输出 使得x^x达到n位数字的最小正整数x 样例输入 11 样例输出 10 题目思路 将题目翻译成公式即为：x^x>=10^(n-1)对两边取对数得到x*log10(x)>=n-1那么我们只要...