ACM

BZOJ 1293 生日礼物(尺取)

BZOJ 1293 生日礼物(尺取)
录入信息,按照位置排个序,然后尺取法进行标记统计处理即可。代码:tatusAcceptedTime1804msMemory13012kBLength913LangC++#include <iostream> #include <cstdio> #include <algorithm> #include <mem... 继续阅读 »
ACM

BZOJ 1202 狡猾的商人(乱搞||带权并查集)

BZOJ 1202 狡猾的商人(乱搞||带权并查集)
这个题嘛,说是用带权并查集,额,可是还没想通,所以先把乱搞的方法写下。乱搞的方法就是,知道x-y,y-z,x-z的值,我们只要先排序,然后把x-z的值减去x-y的值,就可以得到y-z的值,然后验证与原来的值是否相等即可。代码:StatusAcceptedTime524msMemory1388kBLength1878LangC++#include <iostream> #in... 继续阅读 »
ACM

POJ 1845 Sumdiv(唯一分解+递归二分+快速幂+大数模)

POJ 1845 	Sumdiv(唯一分解+递归二分+快速幂+大数模)
题目意思是,给出一个底数和他的幂,请计算这个数的所有因素之和。下面对四个知识点进行梳理:1、唯一分解定理:定义:任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积A=p1^a1 * p2^a2 * p3^a3 *...* pn^an,这里p1<p2<p3......<pn均为质数,其中指数ai是正整数。这样的分解称为N的标准分解式。由于 A... 继续阅读 »
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了,但是对接下来理解“马拉车”算法却容易了。首先,为了处理偶数问题,我们在字符串中插入一些特殊字符,比如”#“,注意第一个字符给另外一个比如”@“来特判边... 继续阅读 »