2017-03-22 634 0
题目都看得懂，我们先谈dp再谈容斥。dp的思想就是，先假设每个硬币都不限制数量（给出一个最大界限数量即可），然后统计他们能组成的付款方法有多少种。状态转移方程为：dp[j] = dp[j] + dp[j-c[i]]意思就是，组成当前j元付款方法的方式数是在j原有的方法上加上一个 不加当前硬币的方法数。（有点绕口，自己想想就明白了。）然后接下来理解容斥。这里的容斥方法是先假设每种硬币的数量都超出了给... 继续阅读 »
2017-03-22 637 0
很好的逆向思维题，我们如果正向去想的话，删除节点肯定比较麻烦复杂，但是如果从后往前，删除节点就变成了增加节点，所以我们从最后删除的一个节点开始往前倒着添加节点，也就是维护一个并查集的事。代码：StatusTimeMemoryLengthLangAccepted2136ms16452kB1210C++#include <iostream> #include <... 继续阅读 »
2017-03-16 815 5
题目意思是每行给你四个数，然后再每列选一个数，四列任取一组之和等于0，求有多少组这种组合？一开始想复杂了，以为是动态规划，后来比完才知道是二分，暴力也可以做（不知道为什么暴力时间还短一些）。暴力的话就是先a、b组合排序，然后c、d组合排序。从ab的开头开始找，从cd的末尾开始找，这样时间会快点。二分的话就是，排列的的时候将cd组合为-(c+d)，然后排序之后二分查找和ab相同的即可。代码：Stat... 继续阅读 »
2017-03-12 642 0
题目的意思就是给你一些字符串，然后从字符串里面找这样的字符串输出：1、这个字符串在给出的列表里面2、这个字符串由其中其他两个字符串组成。一看就是字典树，建树，然后拆分字符串遍历，搜索就行。然后，这个题map也可以做，代码量减少一倍，时间增加一倍。代码：自建字典树：StatusAcceptedTime62msMemory8240kBLength1167LangC++#include <... 继续阅读 »
2017-03-12 602 0
题目意思是找出一个数和给出的数异或最大，由于数值最大为2^32，异或用到的是二进制的0和1，所以我们只需要建立一个两分支的高度为最高33的字典树就好了。我们在每个分支终点标记这个二进制数的10进制数所在数组的位置。然后就是搜索就可以了。代码：StatusAcceptedTime655msMemory43476kBLength1655LangC++#include <iostream... 继续阅读 »
2017-03-09 720 0
开始直接暴力，TLE了，然后就去百度了这个马拉车算法。其实思想也很简单的，就是在我们普通的思想上进行了优化，减少了查询次数。按照我们普通的思路来做，肯定是找一个点然后往左右两边延伸找最长，当然这里面涉及到了偶数回文、边界判断等特殊处理，虽然TLE了，但是对接下来理解“马拉车”算法却容易了。首先，为了处理偶数问题，我们在字符串中插入一些特殊字符，比如”#“，注意第一个字符给另外一个比如”@“来特判边... 继续阅读 »
2017-03-06 692 0
周测时没做出来，后来看的题解。题目意思是再保证0,1,2三个位置的灯保持连接的情况下，最多可以关掉其他多少灯。我们可以从三个点出发，分别求这三个点到每个点的最小距离，然后能够找到多条连接这三个点的路线，取最小的那条路线，然后用总数减去这些边数，别忘了是边数，所以换成点数还要减去1。代码：StatusAcceptedTime639msMemory1920kBLength1645LangC++#inc... 继续阅读 »
2017-03-06 686 0
数学真的是太奇妙了。n个人分糖果，这里我们先计算平均数。得到平均数之后，我们用原来的糖果减去平均数，这样就是每个人需要支出的糖果数。我们把这些数看成是价值，然后排序，找到中位数，把每个人都变成中位数会产生一个价值，把这些价值加起来就是总共的价值啦。代码：StatusAcceptedTime2176msMemory9104kBLength572LangC++#include <ios... 继续阅读 »
