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... 继续阅读 »
ACM

HDU 6012 - Lotus and Horticulture(贪心)

HDU 6012 - Lotus and Horticulture(贪心)
题目意思是一个人要做研究,现在要你计算植物在特定温度下的研究价值,给定一个区间,区间以上,区间内,区间以下三个段位是不同的价值。植物很多,而且每盆植物都有自己的区间价值,然后现在要你计算出研究价值最大的那个温度。一开始也不知道自己再想什么玩意儿,虽然想到了贪心但是却在乱做,后来看了题解~我们可以从最低的温度开始慢慢往上计算。在输入数据时就要把位置设置好了,然后赋值,所以肯定需要一个结构体来存咯。要... 继续阅读 »
ACM

HDU 6016 - Count the Sheep(小思维)

HDU 6016 - Count the Sheep(小思维)
给出一些成对的公羊与母羊,他们之间是朋友关系(给出的关系是双向的),请列出有多少种四只羊之间的关系(这个关系是单向的,也就是说顺时针转一圈和逆时针转一圈来数都算不同的关系)。一开始直接dfs暴力,然后无限RE(vector数组开小)和TLE,后来直接计算,以当前点的边减去1再乘以相邻点的边数减去1的值之后再乘以2就是他们的所有关系数就AC了。代码:StatusAcceptedTime670msMe... 继续阅读 »
ACM

HDU 6015 - Skip the Class(统计最大数)

HDU 6015 - Skip the Class(统计最大数)
新学期的训练开始了,先刷个热身题,(寒假荒废太久,都在刷些水题还写了些小东西,不好意思拿出来就不说了)。这个题读懂意思就很简单了,就是说luras开始了新学期的学习,现在他想逃课写代码,但是没门课最多只能逃课两次,每门课有自己的价值(其实理解为时间我觉得更好),那么问题来了,他用最好的方式逃课最多能逃多少价值的课程。这里我就很尴尬了,价值我开始想到的是学分,那我想学分肯定是逃分数最低的那些课,然后... 继续阅读 »
ACM

HDU 5969 扫雷(排列组合)

HDU 5969 扫雷(排列组合)
这题看似很难排列,但是递推一下就能发现规律(当然,我是看了题解,毕竟最近智商下线)。我们用一个数组dp[]模拟每列放置的地雷数,这样每列最多只能放置2个。枚举第一列的个数,然后通过第一个格子递推第二个格子,这样一直递推下去就行。题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=5965代码:StatusAcceptedTime218msMemory164... 继续阅读 »
ACM

HDU 5969 最大的位或(二进制)

HDU 5969 最大的位或(二进制)
“|”运算是1|1=1,1|0=0,0|1=0,0|0=0。不用想肯定是位运算,但是比赛时想了好久没想通。后来看题解发现是自己想多了。就是从最高位开始往下遍历,如果一个数是2的n次方,那么与他“|”最大的肯定是2^n-1,如果取不到那么肯定是往上取。就是这个往上取,开始想不通,后来看题解才明白。具体看代码吧。题目地址:http://acm.hdu.edu.cn/showproblem.php?pi... 继续阅读 »