51nod-1629 B君的圆锥

发表于 数论 分类,标签:
 B君要用一个表面积为S的圆锥将白山云包起来。B君希望包住的白山云体积尽量大,B君想知道体积最大可以是多少。注意圆锥的表面积包括底面和侧面。Input一行一个整数,表示表面积S。(1 <= S <= 10^9)Output一行一个实数,表示体积。Input示例8Output示例1.504506思路:首先要知道圆锥表面积公司和体积公式;        面积公式:(r是底面圆半径,l是母线长度,,h为圆锥体的高)体积公式:求最大体积,首先要有S,求的h=,然后带入到V中。         可见当t=b/(-2*a)时达到抛物线的最大值,...

51nod-1521 一维战舰

发表于 动态规划 分类,标签:
 爱丽丝和鲍博喜欢玩一维战舰的游戏。他们在一行有n个方格的纸上玩这个游戏(也就是1×n的表格)。在游戏开始的时候,爱丽丝放k个战舰在这个表格中,并不把具体位置告诉鲍博。每一只战舰的形状是 1×a 的长方形(也就是说,战舰会占据a个连续的方格)。这些战舰不能相互重叠,也不能相接触。然后鲍博会做一系列的点名。当他点到某个格子的时候,爱丽丝会告诉他那个格子是否被某只战舰占据。如果是,就说hit,否则就说miss。但是这儿有一个问题!爱丽丝喜欢撒谎。他每次都会告诉鲍博miss。请你帮助鲍博证明爱丽丝撒谎了,请找出哪一步之后爱丽丝肯定撒谎了。Input单组测试数据。第一行有三个整数n,k和a(1≤n,k,a≤2*10^5),表示表格的大小,战舰的数目,还有战舰的大小。输入的n,k,a保证是能够在1×n的表格中放入k只大小为a的战舰,并且他们之间不重叠也不接触。第...

51nod-1596 搬货物

发表于 动态规划 分类,标签:
 现在有n个货物,第i个货物的重量是 2wi 。每次搬的时候要求货物重量的总和是一个2的幂。问最少要搬几次能把所有的货物搬完。样例解释:1,1,2作为一组。3,3作为一组。Input单组测试数据。 第一行有一个整数n (1≤n≤10^6),表示有几个货物。 第二行有n个整数 w1,w2,...,wn,(0≤wi≤10^6)。Output输出最少的运货次数。Input示例样例输入1 5 1 1 2 3 3Output示例样例输出1 2思路:题目要求最小的运货次数,那么就要尽可能的使每一次的运货数量最多,用一个数组s[i]记录货物的重量为i^2有s[i]个货,从题目可知两个1,可以得到一个2,两个2可以得到一个三,那么如此一直下去,最后剩下的就是要运的次数...

51nod-1266 蚂蚁

发表于 模拟 分类,标签:
 n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。当蚂蚁爬到竿子的端点时就会掉落。由于竿子太细,两只蚂蚁相遇时,它们不能交错通过,只能各自反向爬回去。对于每只蚂蚁,我们知道它距离竿子左端的距离xi,但不知道它当前的朝向。请计算各种情况当中,所有蚂蚁落下竿子所需的最短时间和最长时间。  例如:竿子长10cm,3只蚂蚁位置为267,最短需要4秒(左、右、右),最长需要8秒(右、右、右)。Input第1行:2个整数N和L,N为蚂蚁的数量,L为杆子的长度(1 <= L <= 10^9, 1 <= N <= 50000)第2 - N + 1行:每行一个整数A[i],表示蚂蚁的位置(0 <&n...

51nod-1010 只包含因子2 3 5的数

发表于 打表 分类,标签:
 https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1010K的因子中只包含235。满足条件的前10个数是:2,3,4,5,6,8,9,10,12,15。所有这样的K组成了一个序列S,现在给出一个数n,求S中>=给定数的最小的数。例如:n=13,S中>=13的最小的数是15,所以输出15。Input第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)第2 - T + 1行:每行1个数N(1 <= N <= 10^18)Output共T行,每行1个数,输出>= n的最小的只包含因子2&n...

51nod-1138 连续整数的和

发表于 动态规划 分类,标签:
 给出一个正整数N,将N写为若干个连续数字和的形式(长度>=2)。例如N=15,可以写为1+2+3+4+5,也可以写为4+5+6,或7+8。如果不能写为若干个连续整数的和,则输出NoSolution。Input输入1个数N(3 <= N <= 10^9)。Output输出连续整数中的第1个数,如果有多个按照递增序排列,如果不能分解为若干个连续整数的和,则输出No Solution。Input示例15Output示例147思路:通过观察,发现若n要分解成m个连续整数相加,那么需满足:当m为偶数时:n%m==m/2当n为素数时:n%m==0代码:#include <bits/stdc++.h>using namespace s...

51nod-1007 正整数分组

发表于 背包问题 分类,标签:
 题目来源:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1007将一堆正整数分为2组,要求2组的和相差最小。例如:12345,将124分为1组,35分为1组,两组和相差1,是所有方案中相差最少的。Input第1行:一个数N,N为正整数的数量。第2 - N+1行,N个正整数。(N <= 100, 所有正整数的和 <= 10000)Output输出这个最小差Input示例512345Output示例1思路:若要两组和相差最小,那么要使两组中和小的那一组的和接近所有整数和的一半。然后用简单的01背包求出较小的那一组和。代码:#include <bits/stdc++....

扩展欧几里德实现

发表于 算法模板 分类,标签:
 对于不完全为0的非负整数a,b.  gcd(a,b)表示a,b 的最大公约数。那么存在整数x, y使得 gcd(a,b)=a*x+b*y;不妨设a>b① ,当b=0 时,gcd(a,b)=a, 此时 x=1,y=0;② ,当 a*b<>0 时, 设 a*x+b*y=gcd(a,b);   (1)    b*x0+(a%b)*y0=gcd(b,a%b);   (2)由朴素的欧几里德公式;gcd(a,b)=gcd(b...

欧拉函数及其应用

发表于 算法模板 分类,标签:
 一.互质的概念:1、定义    互质(relativelyprimeì)又叫互素。若N个整数的最大公因数是1,则称这N个整数互质。  例如8,10的最大公因数是2,不是1,因此不是整数互质。  7,10,13的最大公因数是1,因此这是整数互质。  5和5不互质,因为5和5的公因数有1、5。  1和任何数都成倍数关系,但和任何数都互质。因为1的因数只有1,而互质数的原则是:只要两数的公因数只有1时,就说两数是互质数。1只有一个因数(所以1既不是质数(素数),也不是合数),无法再找到1和其他数的别的公因数了,所以1和任何数都互质(除0外)。  互质数的写法:如c与m互质,则写作(c,m)=1。  小学数学教材对互质数是这样定义的:“公约数只有1的两个数,叫做互质数。”  这里所说的“两个数”是指自然数。  “公约数只有1”,不能误说成“没...

1013 3的幂的和

发表于 数论 分类,标签:
 基准时间限制:1 秒空间限制:131072 KB分值: 20 难度:3级算法题 收藏 关注求:3^0+3^1+...+3^(N)mod1000000007Input输入一个数N(0 <= N <= 10^9)Output输出:计算结果Input示例3Output示例40https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1013代码:#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define eps ...