ACM

CodeForces - 626C - Block Towers(二分)

CodeForces - 626C - Block Towers(二分)
题意:给出n、m,请计算一个只有n个2的倍数和m个3的倍数构成并且没有重复的序列中最小的max(n*2, m*3)。为了接下来学习01规划找到的这个题。这个题有两种解法,一种是贪心,一种是二分。我们先来看看贪心解法:一、贪心:首先,我们考虑到2的倍数和3的倍数是有他们的最小公倍数6的倍数的重复的。所以我们只需要先假定n就是n*2,m就是m*3,这时候可能有6的重复,所以我们从6开始不断增长6的倍数... 继续阅读 »
ACM

HDU - 6069 Counting Divisors(素数筛法+技巧质因数分解)

HDU - 6069 Counting Divisors(素数筛法+技巧质因数分解)
题目的意思是:给出l,r, k,求l到r区间内每个数的k次方的约数个数的和,再对998244353取余。这题用到的技巧还真是多啊,乱搞暴力肯定GG。首先我们来看看怎么求解约数的个数。一个数可以分解成多个质数的的乘积。假设p为质数(1不是质数啊,怎么每次都讲不听呢),所以有:n = p1^c1*p2^c2*p3^c3*......*pm^cm根据乘法原理:n的约数的个数就是(c1+1)(c2+1)(... 继续阅读 »
ACM

CDOJ - 1401 谭爷的黑暗沙拉 (隔板法)

CDOJ - 1401 谭爷的黑暗沙拉 (隔板法)
题目意思就是说,给你n种食材,食材供应无限,然后要你选择k种食材做成一个沙拉,两份沙拉不同,当且仅当k重量食材的种类或配比不同。普通的隔板法不允许有空组出现,而且容易理解,但是这里用到了分组为空的情况,所以我们先来举个例子介绍下允许分组为空隔板法:> 假设我们有10个小球,将其放入3个盒子,盒子可以为空,请问共有多少种放法?利用隔板法,我们只能在10个小球中间的9个位置插入隔板来分组,但是这... 继续阅读 »
ACM

Gym - 101149B No Time for Dragons(贪心)

Gym - 101149B No Time for Dragons(贪心)
题目意思是派遣一些军队去杀n条龙,杀死一条龙需要派遣ai个人,会死掉bi个人,问你最少派遣多少人可以杀死所有龙。贪心题,比赛的时候没想出来排序的数,一直想的是按派遣人排还是按死的人排,后来freeloop说是按存活最多的排。然后,,,我想如果派我去打战估计损失惨重啊。。。地址:http://codeforces.com/gym/101149/problem/B代码:StatusAcceptedTi... 继续阅读 »
ACM

HDU 6040 Hints of sd0061(快排思想)

HDU 6040 Hints of sd0061(快排思想)
题目的意思是,一共有N个人,给出一个函数,再通过给出a、b、c变量可以计算出第N个人的分数,然后接下来有M场比赛,每场比赛由产生的n个数中从小到大排序,排到第n-1大的人来进行,问这第个人的分数是多少?排序好题,由于n高达10e7,所以直接排序铁定超时,可以利用快排思想来解决,先选定一个基准数,然后排序,排完后这个数的位置就确定了,然后根据查询的数是否大于还是小于这个数可以选择一边排序而没有必要全... 继续阅读 »
ACM

Gym - 101149H Streets of Working Lanterns(贪心、前缀和)

Gym - 101149H Streets of Working Lanterns(贪心、前缀和)
题目的意思是一个人记录罪犯进出的过程,"("代表进去,")"代表出去,“?”代表没记录到。问你是否存在这么一种可能,把问号变为"("或")",保证开始和结束后房间里面都没有人。贪心即可,记录前缀和,然后判断,之后不断修改"?"再进行判断,保证“)”不能多。地址:http://codeforces.c... 继续阅读 »
ACM

Gym - 101149J Panoramic Photography(思维水题)

Gym - 101149J Panoramic Photography(思维水题)
题目意思就是说一些学生拍照片,每个人拍的照片都是连续的建筑,现给出每栋楼上照片中建筑的数目,求最少的拍照人数。开始怎么看怎么复杂,后来在草稿纸上画了一下图想了想,如果把照片平摊在平面上,那不就相当于跳格子吗,跳到比当前高的就加,矮的就更新,这样就OK了。地址:http://codeforces.com/gym/101149/problem/J代码:StatusAcceptedTime46msMem... 继续阅读 »
ACM

CDOJ - 1334 郭大侠与Rabi-Ribi(stl、贪心)

CDOJ - 1334 郭大侠与Rabi-Ribi(stl、贪心)
开始一直想的是直接安时间-价值排序,然后从时间最少的开始for循环一遍找兔子,如果时间不够用则进入下一个时间段找兔子,然后就wa啊,后来想想有点不对,万一时间少的地方有比时间大的地方的兔子呢,所以这个地方要用一个优先队列来维护,和bzoj上面建筑抢修那个题一毛一样啊。地址:http://acm.uestc.edu.cn/#/problem/show/1334代码:StatusAcceptedTim... 继续阅读 »
ACM

CDOJ - 1339 郭大侠与线上游戏 (STL)

CDOJ - 1339 郭大侠与线上游戏 (STL)
很有意思啊,把set分成l、r两部分来用,由于中位数是k/2+1的位置,保证中位数始终在r这边就可以,在而且set还有rbegin的函数。平衡l、r两个set集合就行,辅以一个队列用来删除数用。地址:http://acm.uestc.edu.cn/#/problem/show/1339代码:StatusAcceptedTime917msMemory12004kBLength1831LangC++#... 继续阅读 »
ACM

CDOJ 1325 卿学姐与基本法(线段树+离散化+lazy)

CDOJ 1325 卿学姐与基本法(线段树+离散化+lazy)
题目的意思已经很明显了,就是要用线段树来做,只不过是区间查询,所以要用到lazy思想,这个在之前的(http://woodcoding.com/?id=23)已经了解过,但是那个lazy是通过加上inc值来达到下放的目的,而这个题我用的下放是直接把值下放更新来达到lazy的目的。而且这个题还用到了离散化,按照我们平常的线段树都是每个点都建到的,但是这个题从给出的数据范围来看就知道是不能每个点都建到... 继续阅读 »