题目链接：http://poj.org/problem?id=3489/**//*题意：给定n( n <= 1000 )个大小为Vi的物品，每个物品都可以拆分成k次，拆分好的物品可以继续拆分，Vi是整数，但是拆分好的物品的大小可以是任意实数，例如本来Vi为7的物品拆分成5份，那么每份大小就是1.4，问最后能不能通过拆分和组合组出大小为x的物品（每个物品的供应量是无穷多的）。题解：数学推导思路：问题求得就是以下方程有没有整数解：x1*V1/(k^y1) + x2*V2/(k^y2) ++ xn*Vn/(k^yn) = x其中x1，y1是未知量。首先要明确的一点是，一个物品可以拆分的无限小，也就是k^yi可以很大很大，因为当k^yi取得越大时，我们总可以找到k^yi个这类物品把它还原成原来的大小，所以不影响解题；相反，如果取得比较小的话可能找不到可行解，因为还没有达到要拆分的次数，然后我们这样考虑，令G = gcd(V1, V2)，并且Ti = Vi / G。那么原方程就可以表示成如下形式：G * ( x1*T1/(k^y1) + x2*T2/(k^y2) ++ xn*Tn/(k^yn) ) = x然后令M = k^j，你可以假设这个M足够大。再将上面的方程变形：S = x1*T1*(k^(j-y1)) + x2*T2*(k^(j-y2)) ++ xn*Tn/(k^( ...继续阅读 (32)

摘要: 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3758 /**//*题意： 给定N个和M个不大于10000的数(N,M <= 1000)，N个数各自的阶乘的乘积除上M个数各自阶乘的乘积是一个很大的数，现在要求将这个数表示成如下形式：  ...;阅读全文英雄哪里出来2011-04-15 09:11发表评论 ...继续阅读 (60)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3756/**//*题意：在一个三维空间中，给定一些点，这些点的z坐标都是大于0的。要求求出一个圆锥（底面是圆形），使得这个圆锥的底面在z = 0的平面上，它能够包含所有给定的点并且圆锥的体积要求最小。题解：数学推导 + 三分思路：这是一个很有意思的题，虽然是三维的，但是可以很容易的转化到二维去。来看X-Z这个平面，我们将所有的点进行圆周映射，然后将所有的点都投影到X-Z平面的的第一象限去，然后问题就转化成了在X-Z平面上找到一条斜率为负的直线L，L和X正方向、Z正方向围成的三角形包含所有点，如果假设L和X轴的交点为R，和Z轴焦点为H，要求pi*H*R^2的值最小。然后我们来看看H和R之间有什么千丝万缕的关系。首先L这条线必定和某一个给定的点擦边，也就是经过那个点，我们假设它经过P(a, b)， 并且L的斜率为K(K < 0)，那么L的方程就可以表示为 L: y = K * (x - a) + b，则H和R就可以利用这个方程表示出来：H = -a * K + b;R = -b / K + a;那么所求的圆锥的体积就是：V = pi*H*R^2 = pi * (-a * K + b) * (-b / K + a) ^ 2容易得到V(K)这个函数的导数：V'(K) = - pi * (aK^ ...继续阅读 (37)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2688/**//*题意：给定一串长度为N的序列(N <= 3000000)，然后是M(M<=10000)个操作，每个操作有两种形式：1. Q 询问当前序列的顺序数2. R S E (abs(E-S) <= 1000)将下标S到E的数列向左循环旋转一次题解：树状数组思路：经典问题，首先将N个数的顺序数用树状数组求出来，这个操作是nlogn的，然后对于每次R操作，统计在[S+1，E]区间中比v[S]大的数和小的数的个数，将之前的顺序数 - 比它大的数 + 比它小的数，更新这个值。然后顺序赋值即可。Q操作只需要直接输出当前顺序数的值即可。*/#includeusingnamespacestd;#definemaxn 10001intans[3000001];intn, m;#definell __int64ll c[maxn];intlowbit(intx){returnx&(-x);}voidadd(intpos){while(pos0){s+=c[pos];pos-=lowbit(pos);}returns;}intmain(){inti;while(scanf("%d",&n;)!=EOF){for(i=1; i<=10000; i++)c[i]=0;ll val=0;for(i=0; ...继续阅读 (33)

摘要: 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1066 /**//*题意： 给定一个数N(N <= 10^200)，求出N的阶乘的最后一位非零数字。题解： 找规律 + 大数模拟思路： &nb...;阅读全文英雄哪里出来2011-04-11 12:11发表评论 ...继续阅读 (31)

摘要: 题目链接：http://poj.org/problem?id=3145 /**//*题意： 对于一个集合S，一共两种操作：1. B X: 添加一个数X到S. 第K个B操作发生在第K个时间点，并且每个之前S集合中没有X。2. A Y: 在S集合中所有数中, 被Y除后余数最小...阅读全文英雄哪里出来2011-04-10 11:12发表评论 ...继续阅读 (32)

摘要: 题目链接：http://poj.org/problem?id=1186 /**//*题意： 已知一个n元高次方程： 其中：x1, x2,,xn是未知数，k1,k2,,kn是系数，p1,p2,pn是指数。且方程中的所有数均为整数。 假设未知数1 <= xi <= M,&n...;阅读全文英雄哪里出来2011-04-09 23:55发表评论 ...继续阅读 (34)

题目链接：http://poj.org/problem?id=1990/**//*题意：约翰农夫有N(N <= 20000)头牛，每头牛有一个权值Vi，他将它们排成一排，牛i和牛j的阈值是 两者的距离差*max(Vi, Vj)，现在给出每头牛的权值和它的位置，求所有两头牛之间的阈值之和。题解：树状数组思路：我们准备两个树状数组，以每头牛的位置作为树状数组的下标，其中一个用来表示当前位置的牛的位置的值，另一个则记录当前位置牛的个数，然后对所有牛以Vi为关键字进行递增排序。接下来对每头牛进行一次线扫，首先统计比当前这头牛的位置小的和大的牛的数目和位置和，然后做差求出以当前牛的权值为最大值的阈值总和。之后将这头牛的数量和位置插入到树状数组中进行更新。*/#include#includeusingnamespacestd;#definemaxn 20010#definell __int64structpoint{intV;intpos;}pt[maxn];ll c[2][maxn];intn, Max;ll ABS(ll v){returnv<0?-v : v;}intcmp(point a, point b){returna.V<=Max){c[idx][pos]+=v;pos+=lowbit(pos);}}ll sum(intidx,intpos){ll s=0;while(pos> ...继续阅读 (81)

题目链接：http://poj.org/problem?id=2828/**//*题意：给定N(1 <= N <= 200000)个整数对(A,B)，表示在A右边的位置插入一个B，经过N次操作后问最后的B序列的排列情况。题解：树状数组 或者 线段树思路：这题的数据量比较大，一开始可以模拟一下过程，但是直接暴力肯定是超时的，因为每次插入过程，这个位置的后面的元素必然是要顺序往后移动的。所以总的复杂度高达O(n^2)。但是这个问题可以转化，我们这样考虑，对于任意两个整数对(A1,B1)和(A2,B2)保证(A1,B1)在(A2,B2)之前出现，如果A1小于A2，后面的整数对是不影响前面整数对的位置关系的，否则B1的位置必然要受到B2的影响而向后移动一位。于是A1和A2之间就存在一个逆序关系，我们可以联想到树状数组求逆序数时候的做法，从后往前，对于最后一个数，它的位置就是An，因为之后没有插入数了，它已经稳定下来了，然后将这个位置插入到树状数组的相应位置去，每次扫描到当前数的时候二分枚举当前数前面有多少“空位”，空位的统计可以采用树状数组的成段求和，找到后将这个数插入，N次操作后答案就保存下来了。*/#includeusingnamespacestd;#definemaxn 200010intn;intc[maxn];structpoint{intA, B;}pt ...继续阅读 (46)

摘要: 题目链接：http://poj.org/problem?id=2637 /**//*题意： 给定N(N <= 50000)条信息，表示第yi年的降水量是ri，然后给出M(M <= 10000)条询问，每条询问的格式是Y X，表示自从第Y年以来X这一年是最大的降水量，问这句话正确与否。&nb...;阅读全文英雄哪里出来2011-04-09 14:00发表评论 ...继续阅读 (36)

题目链接：http://poj.org/problem?id=3067/**//*题意：左边N个点，右边M个点，分别南北方向排列，1对应1，2对应2，给出K条记录，每条记录表示左边的A点和右边的B点相连，两条相连的先会有一个交点，现在保证任意三个线不会交与一点，问一共多少个交点。题解：树状数组思路：题目求的是交点的数目，仔细观察就可以发现，如果有以下四个点，A1，B1属于左边，A2，B2属于右边，当且仅当 A1和A2的大小关系 和 B1与B2的大小关系 相反，于是可以联想到求一个数列的逆序数的时候用到的树状数组的成段求和。我们只要将读入的整数对按左边的点递增排序，如果左边点大小相同则按右边点递增排序，每次在树状数组中统计比当前右边的点大的数的数目，然后再将这个点插入树状数组，这就实现了一个逆序统计。这里需要注意的是，统计的时候需要采用__int64，因为总的交点数可能会超过int。最大的情况是左右两边都是1000个点，并且两两有边，那么最大的交点数量就是：1 * (1 + 2 ++ 999)+2 * (1 + 2 ++ 998)+998 * (1 + 2)+999 * 1+1000 * 0可以写个程序统计一下，发现这个数字是超过int的。ll ans = 0;for(i = 1; i <= 1000; i++) {ans += i * (1001 - i) * (1000 - i) ...继续阅读 (26)

摘要: 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2871 /**//*题意： 现在有1到N(N <= 50000)个连续内存块，然后给出四种操作：1. Reset 释放所有内存块，并且输出“Reset Now”。2...阅读全文英雄哪里出来2011-04-08 15:26发表评论 ...继续阅读 (25)

摘要: 题目链接：http://poj.org/problem?id=2720 /**//*题意： 给定三个整数 b, n, 和 i, 定义函数 f(x) = b^f(x-1) 如果 x > 0, 并且 f(0)=...阅读全文英雄哪里出来2011-04-07 20:02发表评论 ...继续阅读 (18)