【暑假集训个人赛】哈利波特的传奇一生(上)题解bulid by 高居鹏 at 2015-08-25 22:38
Rating:1314
  A:bnuoj 33535
贪心算法的综合运用,关键看怎么贪心,求重叠部分最多的,这个题不同于一般的贪心。我的做法是首先定义一个结构体里面包括课程序号、开始区间S、结束区间t,以及安排天数;第一个排序就是按照开始区间由小到大(如果开始区间相同就是结束区间由小到大);接下来注意啦!!!!!!就是天数的计算了,首先第一个天数是一,接下来判断下一个科目的开始区间是否小于上一科目的结束区间,若果是这两个科目就在同一天(这个时候不要以为就完事了,还要把这上下科目开始区间的大的跟结束区间小的赋值给下一个区间,不然就会输出错误,我第一次提交这点就错了);如果不小于的话,下一科目的天数就要比上一科目的天数加一;这个时候你的代码算是完成的差不多了;接下来就要再次排一次序了,按照天数由小到大排(如果天数相同就按科目由小到大排);这一步完了就是输了,这就是你看题目输出要求就可以了!

B:hdu4002
由欧拉函数为积性函数,即:如果gcd(m , n) == 1,则有φ(m * n) == φ(m) * φ(n);且由φ(p^k) == (p - 1) * p^(k - 1),可得
φ(n) == φ(p1^k1 * p2^k2 * p3^k3 * … * pt^kt)
      == φ(p1^k1) * φ(p2^k2) * φ(p3^k3) * … * φ(pt^kt)
      == (p1 - 1) * p1^(k1 - 1) * (p2 - 1) * p2^(k2 - 1) * (p3 - 1) * p3^(k3 - 1) * … * (pt - 1) * pt^(kt - 1)
      == p1^k1 * (1 - 1/p1) * p2^k2 * (1 - 1/p2) * p3^k3 * (1 - 1/p3) * … * pt^kt * (1 - 1/pt)
      == n * (1 - 1/p1) * (1 - 1/p2) * (1 - 1/p3) * … * (1 - 1/pt)
于是有
f(n) == n/φ(n) == 1 / [ (1 - 1/p1) * (1 - 1/p2) * (1 - 1/p3) * … * (1 - 1/pt) ]   (1)
由 (1)式 可知:要使f(x)最大,须使x含尽量多的不同素数因子。
样例,n=10,结果是6=2*3,n=100时,结果为 30=2*3*5;
分析可知,先把从2开始的连续素数的乘积存在数组cc[][] 中。然后找到一个不超过n的最大的cc[][]就是答案了

C:hdu 1258
简单的dfs,对于每个DFS过程所在的数字而言,应该枚举其在加式中的出现次数(把不出现当做作为0次处理)。而为了符合输出规则:DFS应当从大数开始(好在题目给出的已经是一个非降序排列的数组了),枚举某个数字在加式中出现的次数也应该从多到少。

D:hdu 2647
简单的拓扑排序,反向建图, 然后top排序分层次; 第一次的工资为888(最低), 第二层的工资 + 1, 后面一样

E hdu1071
水题,解题思路:
//抛物线 yp=a*(x-b)^2+c;
//直线 yz=k*x+s;
//二重积分公式: f(x0,x1)(yp-yz)*dx;
回复
要回复,请先登录

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: