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的目的。而且这个题还用到了离散化,按照我们平常的线段树都是每个点都建到的,但是这个题从给出的数据范围来看就知道是不能每个点都建到... 继续阅读 »
ACM

CDOJ - 251 导弹拦截(nlogn的LIS)

CDOJ - 251 导弹拦截(nlogn的LIS)
一看就是lis,但是普通的lis是行不通的,而且这里要记录lis路径,可以使用nlogn的lis算法。nlogn的lis算法可以看这里最长上升子序列nlogn在nlogn的算法中得出标记最小结尾数的数组f后,从后面往前面扫一遍即可。题目地址:http://acm.uestc.edu.cn/#/problem/show/251代码:StatusAcceptedTime29msMemory1800kB... 继续阅读 »
ACM

UVALive - 5881 Unique Encryption Keys(思维、暴力、map)

UVALive - 5881 Unique Encryption Keys(思维、暴力、map)
题目的意思是给你从1-M区间的数值,接下来有m次询问,每次询问l、r区间,问个区间是否有相同的数,若没有,则输出OK、否则输出任意一个相同的数。这个题目有点坑。明明说了是any,但是却没有特判,只能找区间内最左边的那个相同的数。还有就是一个空行的问题,坑!但是这题非常有意思,本来我是记录离当前值最近的那个数的位置,但是却WA了,可能是TLE但是显示了WA。然后发现有更好的思维。可以从最右边开始循环... 继续阅读 »
ACM

CDOJ - 1134 男神的约会(状态压缩dp)

CDOJ - 1134 男神的约会(状态压缩dp)
状态压缩dp,利用2进制位数以及或运算保存获得的优惠券的张数。可知当前格子[i,j]只与格子[i-1, j]、格子[i, j-1]有关,所以得状态方程如下:状态方程:dp[i][j][k|1<<data[i][j]]=min(dp[i][j][k], min(dp[i][j-1][k], dp[i-1][j][k])+data[i][j]);题目地址:http://acm.uestc.... 继续阅读 »