描述
农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,...,xN (0 <= xi <= 1,000,000,000).
但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？输入
有多组测试数据，以EOF结束。
第...
阅读全文
poj 3111 K Best
有n个物品的重量和价值分别是wi和vi。从中选出k个物品使得单位重量的价值最大。
题解:
1、二分做法
2、牛顿迭代
效率比较：
二分做法：
转换成判断是否存在选取K个物品的集合S满足下面的条件：
sigma(vi) / sigma(wi) >= x {vi∈S, wi∈S}
--> simga(vi - x*wi) >= 0
这样我们对 yi= vi - x*wi {1<=i<=n}从大到小排序，计算sum(yi) {1<=i<=k}
如果sum(yi){1<=i<=k}>=0...
阅读全文
题意：
求A^B的所有约数之和。
题解：
A = P1^a1 * P2^a2 * ... * Pn^an.
A^B的所有约数之和为：
sum = [1+p1+p1^2+...+p1^(a1*B)] * [1+p2+p2^2+...+p2^(a2*B)] *...* [1+pn+pn^2+...+pn^(an*B)].
用递归二分求等比数列1+pi+pi^2+pi^3+...+pi^n：
（1）若n为奇数,一共有偶数项，则：
1 + p + p^2 + p^3 +...+ p^n
= (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2) * (1+p^(n/2+1))
= (1 + p + p^2...
阅读全文
Sum It Up
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 4 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t=4, n=6, and the list is [4,3,...
阅读全文
Catch That Cow
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 37094
Accepted: 11466
Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number
line. Farmer John has two modes of transportatio...
阅读全文
题意：
制作一个体积为Nπ(N<=10000)的M(M<=20)层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数...
阅读全文
木棒
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 118943 Accepted: 27429Description
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。Input
输入包含多组数据，每组数据包括两行...
阅读全文
题意：
从左到右有n个积木，依次编号0~n-1，要求模拟以下4种操作。
1、move a onto b
a和b都是积木的编号，先将a和b上面所有的积木都放回原处，再将a放在b上。
2、move a over b
a和b都是积木的编号，先将a上面所有的积木放回原处，再将a放在b上。（b上原有积木不动）
3、pile a onto b
a和b都是积木的编号，将a和其上面所有的积极组成的一摞整体移动到b上。在移动前要先将b上面所有的积木都放回原处。移动的一摞积木要保持原...
阅读全文
点击打开链接
简单
模拟机器人的移动，发生碰撞时输出相应的信息。
code
#include <cstdio>
#include <cstring>
using namespace std;
struct node{
int k;
int s;
}
mtx[200][200];
struct node1{
int x, y;
}
rob[200];
int n, m;
int dir[4][2]= {{0,1},{1,0},{0,-1},{-1,0}}; //N, E, S, W
int D(char ch){
if(ch=='N') return 0;
if(ch=='E') return 1;
if(ch=='S') return 2;...
阅读全文
A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive
elements of the sequence, the sum of which is greater than or equal to S.
尺取法
设置两个指针s,t。
维护一个区间的信息，然后根据指针的移动，更新区间信息。
...
阅读全文