ACM

POJ 1006 Biorhythms(同余定理)

POJ 1006 Biorhythms(同余定理)
题目的意思是,给定三个周期,23,28,33,然后给出这三个周期在一年内上次出现最高峰的日期,分别为:p,e,i。再给出一个当前日期d。请计算从当前d开始往后,下次三个周期重合的时间距离现在是多少天。注意,如果下次周期重合的时间小于等于d都是不可用的。代码:乱搞版本StatusAcceptedTime63msMemory644kBLength557LangG++#include <... 继续阅读 »
ACM

HYSBZ - 1042 硬币购物(dp+容斥)

HYSBZ - 1042 硬币购物(dp+容斥)
题目都看得懂,我们先谈dp再谈容斥。dp的思想就是,先假设每个硬币都不限制数量(给出一个最大界限数量即可),然后统计他们能组成的付款方法有多少种。状态转移方程为:dp[j] = dp[j] + dp[j-c[i]]意思就是,组成当前j元付款方法的方式数是在j原有的方法上加上一个 不加当前硬币的方法数。(有点绕口,自己想想就明白了。)然后接下来理解容斥。这里的容斥方法是先假设每种硬币的数量都超出了给... 继续阅读 »
ACM

HYSBZ 1015 星球大战(并查集)

HYSBZ 1015 星球大战(并查集)
很好的逆向思维题,我们如果正向去想的话,删除节点肯定比较麻烦复杂,但是如果从后往前,删除节点就变成了增加节点,所以我们从最后删除的一个节点开始往前倒着添加节点,也就是维护一个并查集的事。代码:StatusTimeMemoryLengthLangAccepted2136ms16452kB1210C++#include <iostream> #include <... 继续阅读 »
ACM

POJ 2785 - 4 Values whose Sum is 0

POJ 2785 - 4 Values whose Sum is 0
题目意思是每行给你四个数,然后再每列选一个数,四列任取一组之和等于0,求有多少组这种组合?一开始想复杂了,以为是动态规划,后来比完才知道是二分,暴力也可以做(不知道为什么暴力时间还短一些)。暴力的话就是先a、b组合排序,然后c、d组合排序。从ab的开头开始找,从cd的末尾开始找,这样时间会快点。二分的话就是,排列的的时候将cd组合为-(c+d),然后排序之后二分查找和ab相同的即可。代码:Stat... 继续阅读 »
ACM

HDU 1247 - Hat’s Words(字典树,map)

HDU 1247 - Hat’s Words(字典树,map)
题目的意思就是给你一些字符串,然后从字符串里面找这样的字符串输出:1、这个字符串在给出的列表里面2、这个字符串由其中其他两个字符串组成。一看就是字典树,建树,然后拆分字符串遍历,搜索就行。然后,这个题map也可以做,代码量减少一倍,时间增加一倍。代码:自建字典树:StatusAcceptedTime62msMemory8240kBLength1167LangC++#include <... 继续阅读 »
ACM

HDU 4825 - Xor Sum(字典树)

HDU 4825 - Xor Sum(字典树)
题目意思是找出一个数和给出的数异或最大,由于数值最大为2^32,异或用到的是二进制的0和1,所以我们只需要建立一个两分支的高度为最高33的字典树就好了。我们在每个分支终点标记这个二进制数的10进制数所在数组的位置。然后就是搜索就可以了。代码:StatusAcceptedTime655msMemory43476kBLength1655LangC++#include <iostream... 继续阅读 »
ACM

HDU 3068 - 最长回文(manacher)

HDU 3068 - 最长回文(manacher)
开始直接暴力,TLE了,然后就去百度了这个马拉车算法。其实思想也很简单的,就是在我们普通的思想上进行了优化,减少了查询次数。按照我们普通的思路来做,肯定是找一个点然后往左右两边延伸找最长,当然这里面涉及到了偶数回文、边界判断等特殊处理,虽然TLE了,但是对接下来理解“马拉车”算法却容易了。首先,为了处理偶数问题,我们在字符串中插入一些特殊字符,比如”#“,注意第一个字符给另外一个比如”@“来特判边... 继续阅读 »
ACM

HDU 3832 - 地球一小时(最短路)

HDU 3832 - 地球一小时(最短路)
周测时没做出来,后来看的题解。题目意思是再保证0,1,2三个位置的灯保持连接的情况下,最多可以关掉其他多少灯。我们可以从三个点出发,分别求这三个点到每个点的最小距离,然后能够找到多条连接这三个点的路线,取最小的那条路线,然后用总数减去这些边数,别忘了是边数,所以换成点数还要减去1。代码:StatusAcceptedTime639msMemory1920kBLength1645LangC++#inc... 继续阅读 »
ACM

HYSBZ 1045 - 糖果的传递(数学思维)

HYSBZ 1045 - 糖果的传递(数学思维)
数学真的是太奇妙了。n个人分糖果,这里我们先计算平均数。得到平均数之后,我们用原来的糖果减去平均数,这样就是每个人需要支出的糖果数。我们把这些数看成是价值,然后排序,找到中位数,把每个人都变成中位数会产生一个价值,把这些价值加起来就是总共的价值啦。代码:StatusAcceptedTime2176msMemory9104kBLength572LangC++#include <ios... 继续阅读 »
ACM

CodeForces 778A - String Game(二分)

CodeForces 778A - String Game(二分)
题目意思是给你一个字符串,然后接下来是一个字串,然后再给你一个原字符串每个字符位置打乱的序列,按照这个序列开始删除字符,直到删除到再删除会导致字串不存在为止,问你最多删除多少次。竟然是二分!!!虽然开始看到给出的字符串很长,想想也不可能是常规的解法,但是二分实在没想到啊,二分的题做的太少了。二分,把序列二分一下查找字串是否存在,嗯,就是这么个意思。代码:StatusAcceptedTime62ms... 继续阅读 »